Bruno Théret

Thomas Coutrot

Tax-credit instruments as complementary currencies: a policy proposal for fighting the austerity while saving the euro zone

Summary

How should progressive governments respond to what seems an endless crisis of the eurozone? Most of the policy debate focuses on two equally bad options: either pursuing the current path in hope to "muddle through" or exiting the eurozone. This paper outlines an alternative strategy where the euro is preserved as the common currency used in everyday life but complemented by national means of payment, a type of quasi-money made up of low-denomination Treasury Bonds. Backed by future tax revenues, this means of payment would be called the eurofranc, euro-lire, euro-peseta, euro-escudo, etc. It would be kept at parity with the euro but its exchange into euros would be strictly limited and submitted to special conditions.

A Member State determined to implement this policy would probably face retaliatory measures from European institutions, but it cannot be expulsed from the eurozone nor from the EU. The outcome of such a confrontation will depend, among other things, on government's ability to win confidence of its population for the plan, to gain popular support in other European countries and to negotiate firmly with the EU institutions. Such a step is only one element of a broader economic policy package, including tax reform and debt restructuring. But it is the key element, as it will make it possible to resist creditors' blackmail and stay the course long enough to reconcile the two imperatives of any progressive strategy in Europe today: using national democratic spaces to build a European public space and redirect the European project towards more cooperation and solidarity.

Theory of money shows that a currency is much more than a store of value or a means of payment; it as a "social operator" of belonging to a political community 2 . The euro has, until now, failed in that respect. The new currency could have contributed to a stronger European political community through economic and monetary integration, but the way in which it was set up as a pure financial tool led to its failure. As a consequence, the European monetary union aggravates the very geographical imbalances and social inequalities it was supposed to attenuate, and weakens the European political identity it was thought to construct. This in turn undermines its legitimacy, especially in countries with structural deficits (Southern Europe and France) which became prisoners of permanent high unemployment. In result, the looming political or financial crisis threatens to shatter the whole project. The question is how to address that challenge.

The eurozone could of course be made more viable through radical, democratic reforms of the European treaties in a spirit of cooperation and solidarity, through strict regulation of finance, European taxation, budgets voted by a Eurozone Parliament and so on. However, for time being the dominant political forces in Europe have no intention of moving in that direction. As shown by Syriza's failure to challenge EU policies in the case of Greek debt, European political elites prefer to mobilize the power of finance and the straight-jacket of existing treaties, while pursuing the same path as before and opposing any national attempts to find an alternative to the status quo. Democratic political action is still played out, for the most part, at local and national levels with the European public space kept stunted and powerless, with little public scrutiny.

Europe's next financial or political crises will doubtless trigger, each country going at its own pace, new attempts to break free from the stranglehold of the treaties and the ECB. It is therefore vital to prepare now. We should avoid past mistakes and retain lessons from history proving the value of thinking "outside the box".

Clearly, hoping to somehow "muddle through" the crisis is not viable, as the flaws of the eurozone are structural. But neither is leaving the euro and going back to a devalued national currency a good option. Considering how deeply integrated European productive and financial systems are, this could further exacerbate the political instability favorable to authoritarian and xenophobic movements.

How should then progressive governments in Europe respond to this situation? As stated above, simply leaving the euro and opting for a competitive devaluation of the new national currency is in our view not viable. It would amount to a classic mercantilist policy for increasing the exports and reducing the domestic purchasing power by importing inflation; in other words, to an aggressive competitive policy which is unlikely to lead Southern Europe out of austerity.

In addition, solving the euro crisis is not possible without shifting towards a new model of development, which will necessarily have major distributional effects and imply internal political conflicts. Winning the domestic political struggle will require broad support from the population and solid popular back-up in other European countries, including among the middle classes, savers and entrepreneurs, who have -or think they have -something to lose if the eurozone were to collapse.

Most importantly, the construction of Europe as our common political arena is the requisite for going beyond national antagonisms and organizing the social-ecological transition towards a more sustainable society. This transition must be global, it cannot possibly work merely at a national or even regional level. We need a credible European project if we want to have some weight in global power relations with transnational companies, the US and the so-called "emerging" countries. Such a project should emerge from the euro crisis itself, which is a crisis of the neoliberal ideology underpinning the European monetary union in its current form. To say "first let's take refuge behind our national borders, then we'll see on how we can get out" would only pave the way for nationalist forces that would crush any prospect of a democratic European integration. For all these reasons, leaving the eurozone -which for some legal experts would mean leaving the European Union3 -cannot be a legitimate objective nor a prerequisite for change for progressive political movements. Choosing that option amounts to giving up the fight to impose a trans-European political debate over how to redirect the European project. There is also a risk that this option will dissuade the middle classes without satisfying the working classes.

As it is, the euro and its conceptual flaws are creating a de facto solidarity and a common interest among the populations who pay the price of austerity and the growing inequality. This actually includes broad social groups in "core" European countries such as Germany, even though they may not realize it until it is too late. The battle for a new political hegemony cannot be won in any single European country, it has to be waged on the European level. Some of the foremost principles of European construction, such as subsidiarity, are still available to political forces determined to bring this battle to a successful conclusion. However, this means that some Member States must mobilize the political resources which remain at their disposal, such as taxes and economic policies. In this respect, issuing a fiscal currency to complement the euro could be a crucial political tool -though the actual term "currency" should probably be avoided for legal and tactical reasons, as explained below.

Fiscal (tax-credit) complementary currency: the basic principles

The challenge then is to use a national political crisis as an opportunity, and to show to voters that it is possible to emerge from austerity and conduct alternative policies without calling into question a priori the unity of the eurozone. Issuing a tax-credit currency by the State in parallel to the euro issued by commercial banks might enable a progressive national government to inject liquidity in an independent, efficient and targeted fashion, thus immediately reducing its floating debt and ultimately its consolidated debt 4 . Such a currency emission strictly complies with the principle of subsidiarity, as Member States are alone in disposing of their own fiscal power legitimized by an annual vote on the budget by their Parliaments. This strategy retains then the euro as the common currency of legal tender, but complements it by a national means of payment made up of low-denomination Treasury Bonds -of 5 to 50 euros -with limited but renewable duration. The complementary currency can also take the form of an electronic currency run by the Treasury or an independent agency using transparent implementation. Backed, like any public debt, by future tax revenues, this instrument of payment would be called the euro-franc, euro-lire, euro-peseta, euro-escudo, etc., and kept at parity with the euro yet not freely convertible and not negotiable on an exchange market. This new complementary currency can be used to pay a fraction of civil service salaries, welfare benefits and public expenditure, as all these expenses are de facto short-term public debts. In exchange, the State commits to accepting these bonds as payment for taxes, in parity with and as the equivalent the euro issued by the banking system. It is this guarantee that mainly ensures social acceptance of the complementary currency as a means of payment nationally and upholds its parity with the euro 5 .

Parity with the euro, guaranteed by the State, is an essential condition in this strategy, for two reasons. Firstly, it will strengthen confidence in the complementary currency and prevent inflationary expectations. Secondly, it is indispensable to convince the populations of Europe that the strategy to reform the euro system is a cooperative one, and make more difficult tactics such as the one used by the ECB against Greece in June-July 2015, withholding liquidities and strangling the Greek economy. By contrast, creating a convertible complementary currency at risk of immediate devaluation would signal from the outset that an exit was possible. It would trigger negative expectations, then speculation, further devaluation and finally a disordered exit from the eurozone. Indeed, this was the scenario envisaged by the then German Finance Minister Schäuble and the ECB in 2015 with a view to preparing a Grexit 6 .

A tool for strengthening the local economy and reviving popular consumption

To confront current austerity policies there is an urgent need to issue this type of currency wherever the single currency is leading to recession, mass unemployment, rising social insecurity, the decline of public services and insufficient long-term investment required for the ecological transition. The State could agree to pay-rises (of a uniform amount, for example, 300 euro-pesetas or euro-francs a month) to civil servants and pay its suppliers partly in complementary currency. It would thus inject extra liquidities towards two key policy objectives: helping low wage households and strengthen domestic productivity. As the new complementary currency is not freely convertible into euros, its emission will favor suppliers who produce locally. The effect of economic regeneration will rapidly reach the private sectors and all wage-earners. A reduced debt will also give the State a renewed investment capacity, especially for the ecological transition.

A tool for debt reduction

5 In practice, this acceptance can also be boosted by issuing notes with a lifespan limited to, say, 2 years and earning interest, but with a zero coupon. On the possible variety of specific forms of fiscal credit currency, cf. B. Théret, https://www.academia.edu/36548963/Le_papier_monnaie_de_petites_d%C3%A9nominations_%C3%A9m is_par_les_provinces_argentines_entre_1893_et_2003 (Paper money in small denominations issued by the Argentine provinces between 1890 and 2003) (in French). 6 Jennen Birgit & Rainer Buergin (2015), "Schaüble said to cite option of Greek parallel currency », Bloomberg.com, 22 May 2015. http://www.bloomberg.com/news/articles/2015-05-22/schaeuble-said-tocite-option-of-greek-parallel-currency This policy will reduce public debt and the State's dependence on foreign lenders. Combined with defaulting on part of the public debt -that deemed illegal or illegitimate by a citizen audit -and possible restructuration of the part deemed legitimate, issuing a fiscal credit currency emission will, with contribute to resolving the public debt problem. This is because it has a double effect on the dynamics of indebtedness: a direct effect, since the State will cease to incur debt on the financial markets for its floating debt (the debt funding the Treasury cash-flow of a given year), which in turn affects its transformation by consolidation into longer-term debt7 ; and an indirect effect due to the economic vitality regenerated by the injection of money. Public debt will diminish in relation to GDP as the numerator goes down and the denominator goes up. Moreover, the foreign trade balance will also improve with the reduction of imports and this too reduces dependence both on international finance and on foreign markets.

An expression of non-nationalist popular sovereignty

On monetary matters, the political and symbolic dimensions are crucial. Issuance of a fiscal credit currency is the equivalent of creating interest-free indebtedness of the State towards the citizens, so that confidence in this type of money will broadly depend on confidence in the government issuing it and in its political project. In this way the violence exercised "from above" through the euro could be opposed by people's trust in "their" fiscal currency. This revival of popular, national and democratic sovereignty will not be to the detriment of the other nations of the European Union but to the advantage of all its peoples, as a proposed alternative path of development to free our societies from financial dominance. The negotiations with the European institutions will obviously be difficult, but they'll give time to bring this narrative onto the European public stage and wage the struggle for political hegemony.

Here, it would be useful if a group of countries willing to promote such a policy where to take joint action in an ad hoc coalition. It would no doubt be difficult to mobilize the principle of enhanced cooperation as it requires a unanimous vote within the European Council 8 . But in practice, it would only take one country to go down that road for the others quickly to follow, so that the procedure would become a common practice shared by a significant number of member States.

Historical antecedents

In France, the "Treasury circuit" made it possible to finance post-war reconstruction using similar principles. And in some federations, federated States have already successfully tried out recourse to issuing currencies to complement the federal currency, and this over a long period of time. Thus, we know the conditions required for such experiments to be successful: they must be negotiated upfront with the workers' unions and small business federations, the issuance must be moderate and controlled, and the government must win popular support for the political project underpinning the monetary policy. In fact, the idea of complementary fiscal currency springs not from preconceived theoretical concepts but from historical experiments such as:

-the quasi-monies issued by the Provinces of Argentina between 1984 and 2003, most of which -like the patacon of the Province of Buenos Aires during the 2001-2002 crisis [START_REF] Théret | Sur la pluralité des monnaies publiques dans les fédérations. Une approche de ses conditions de viabilité à partir de l'expérience argentine récente[END_REF] , or the bocade of the Province of Tucuman which lasted from 1985 to 2003 [START_REF] Théret | Birth, Life and Death of a Provincial Complementary Currency: Tucuman Argentina (1984 -2003)[END_REF] -met with significant despite the relative weakness of their fiscal back-up and the macro-economic instability at national federal State level.

-the tax anticipation scrips issued in the United States by many major cities during the crisis in the Thirties; and also the currency finance practised in the American colonies -i.e. federated States-in the 18 th Century and, in certain specific forms, in the 19 th Century. Furthermore, similar proposals have been lively debated across Europe since the start of the euro crisis, with numerous academic contributions and press articles [START_REF] Théret | Sortir de l'austérité grâce à des monnaies nationales complémentaires à l'euro : une revue de littérature[END_REF] . Several fiscal currency mechanisms have been proposed, depending on the national context and the authors of the proposal. The model suggested here is inspired by the mechanism adopted by the Argentine Province of Tucuman, which proved resilient -lasting from 1985 until 2003 -and efficient at reducing public debt and as a contracyclical political tool. To mention only one similar proposal, the Italian scheme for tax credit certificates (TCC) to be distributed as "helicopter money" and linked to a tax debit card is also worth examining, even though its option of making the TTC negotiable in euros on a daily basis does seem rather problematic [START_REF] Bossone | Fiscal Debit Cards and Tax Credit Certificates: The Best Way to Boost Economic Recovery in Italy (and Other Euro Crisis Countries)[END_REF] .

A unilateral but cooperative process

The creation of a national fiscal credit currency in complement to the euro avoids the pitfalls of the two usual kinds of proposals for resolving the euro crisis, i.e. sovereignism and Europeanism. The former sacrifices the European project on the altar of a supposed democratic sovereignty at the national level, while the latter (in its different versions, neoliberal or Keynesian -providing, for example, for a system with a common currency accompanied by cooperatively devalued national currencies) in fact sacrifices national democratic choices for an improbable Europe-wide consensus on reform. This initiative is obviously only one element of a much broader economic policy including tax reform, debt audit and cancellation, democratic socialization of banks, etc. But it is the key element, one that will make it possible to resist creditors' blackmail and stay the course long enough to reconcile the two imperatives of any progressive strategy in Europe today: make use of existing democratic spaces -mainly local and nationaland initiate a new European project founded on solidarity. It will give progressive governments time to carry on the European political battle and allow other countries to reach the tipping point and redefine the nature and the contours of the European project.

Preparing for the legal-political battle

The system can be implemented in such a way as not to contradict existing European treaties 13 . The payment instrument proposed here is to be used strictly for tax and local payments and is not legal tender: it is not money in the legal sense of the term, and its creation does not impinge on the prerogatives of the European Central Bank. Neither would the issuance of fiscal credit notes be inflationary, since any excess would result in their devaluation against the euro rather than by inflation of the general level of prices. Also, at the legal level, Member States pursuing this policy cannot be expulsed from the eurozone, which has no institutional existence separate from the European Union, nor in expulsion from the latter, this not being provided for in the treaties14 . These are crucial points in constructing a power balance that is favorable to governments who want to undertake this kind of innovation.

The example of Greece, despite its very specific character 15 , does however suggest that a State which takes the initiative of such an innovation would face retaliatory measures taken by the European institutions, primarily the ECB, in order to force the country either to abandon its project or leave the EU. This battle seems inevitable and therefore should be anticipated. Thus, political parties that might choose this strategy need to prepare in advance -not only to build trust in the fiscal currency, but also to prepare for a tough legal-political battle against interpretations claiming that the initiative would be at variance with the Treaties, obviously with ideological and political motivations.

In fighting that battle, Member States could recall various impingements and exceptions to the treaties introduces by European institutions since the financial crisis of 2007/08, for instance ad hoc organizations such as the Eurogroup and the European Stability Mechanism (ESM), validated a posteriori by the Court of Justice of the European Union (CJEU). A major precedent could also serve as argument in that debate, namely the use of exceptional powers by the governor of the ECB and "non-conventional" monetary policies, which seem to exceed ECBs mandate and were justified by the "exceptional" situation and the need to "save" the euro. Another possible source of inspiration is the German habit of challenging EU prerogatives by submitting them to the German Federal Constitutional Court.

Preparations should also be made for responding to the legal argument which holds that a fiscal credit currency -even if it is considered as an element of the fiscal policy of the Member States, i.e. a prerogative which, while "coordinated", remains the exclusive, sovereign initiative of the Member States -is prohibited by the CJEU as contradicting the spirit of the European treaties, according to which the Member States create "an ever closer union" (Article 1 of the TEU.) 16 The challenge would be to explain to European institutions that given the determination of a national government to escape from austerity policies and the liquidity trap at all costs, the system is in fact a solution for maintaining and even strengthening the Union; the other term of the alternative being not the status quo of the single bank-euro, but the exit from the euro and thus from the Union. After Brexit, if either Portugal or Spain, let alone Italy, were to leave the EU, the effect would be the opposite to moving towards an "ever closer union." Choosing a proper name for the system is also important to avoid accusations of counterfeiting. It must be made clear that these quasi-currencies (terms used by the IMF and the World Bank in the case of Argentina during the 1980s-90s) are purely tax credit instruments, in fact Treasury bonds in bearer form and in small denominations, issued directly to the public in order to serve as payment instruments consistent with a budgetary policy aimed at reducing deficit and debt in euro.

The exact form of the new system requires careful consideration, since from a legal point of view, depending on the country it can be easier to issue digital or paper currency. When a parallel payment system is being set up at the level of a member state, the framework of its implementation must be carefully designed as to reduce legal and regulatory constraints -both European and national -that could hamper it and make it ineffective. Clearly the national fiscal currency must have a high degree of autonomy in relation to the current banking system and the financial markets, and must be founded within a restructured Treasury Circuit that can house it. 17 The simplest solution in an emergency situation is look for inspiration in experiments that have achieved success and whose implementation does not need a complex infrastructure; this would suggest issuance of paper notes complemented by the creation of Treasury and postal current accounts with debit cards.

In any case, the constraint of the EU law would be neither immediate nor heavy; it could not prevent a determined and duly prepared government from instituting a payment system based on anticipation of tax revenues, as is the case with any government debt. In short, the idea should not be abandoned that due to the current institutional shortcomings of the EU and of the Eurozone, a political and legal space exists within which progressive governments can refuse any blackmail regarding an exit from the euro and the EU, and conduct autonomous national policies that may one day change the balance of power in Europe. A government whose program includes the issuance of a complementary fiscal currency, kept at parity with the euro, should be prepared to fight this battle offensively, and not from a situation of weakness at the legal level. In that regard, to prepare such a strategy of defending the legal nature of a complementary fiscal currency, the political forces proposing it need to be backed by a group of qualified legal experts.

In any case, if an exit from the euro and thus from the EU were finally to become inevitable, it would be less painful with a complementary currency already in place. And above all, at the end of such a political and legal battle, the exit would appear to European public opinion as an unjustified expulsion, a sanction against a courageous government looking for a solution to save the eurozone.

  Translated from the French by Snake Arbusto, Vicki Briault and Christine Pagnoulle of the CADTM, revised by Wojtek Kalinowski

The authors would like to thank the legal scholars Matthieu Caron, Jean Grosdidier and Romain Zanolli, for reading and commenting on a previous version of this text. We have tried to take their remarks into account in the present version.

Michel Aglietta, « La monnaie est un rapport social », (Currency is a social relationship), interview with Jean-Marie Harribey and Dominique Plihon, Revue Les Possibles, April 2015 (in French).

Cf. Helmut Siekmann, "Replacing or Supplementing the Euro in Member States whose Currency is the Euro", Working Paper Series no. 109, 2016, Institute for Monetary and Financial Stability, Goethe University Frankfurt Am main).

Cf. Thomas Coutrot, Wojtek Kalinowski, Bruno Théret, https://www.veblen-institute.org/The-Euro-Drachma-a-Monetary-Lifeline-for-Greece.html ; Gaël Giraud, Benjamin Lemoine, Dominique Plihon, Marie Fare, Jérôme Blanc, Jean-Michel Servet, Vincent Gayon, Thomas Coutrot, Wojtek Kalinowski, Bruno Théret, https://www.veblen-institute.org/Ending-Austerity-without-Leaving-the-Euro-How-Complementary-Fiscal-Currencies.html .

Bruno Théret (2016), « Dette publique et auto-répression monétaire des États », (Public debt and the selfoppression of States) Savoir/Agir, n° 35 (in French).

The three French legal scholars, specialized in public finance and monetary issues, that we consulted share this point of view.

Cf. Phoebus Athanassiou (2009), "Withdrawal and expulsion from the EU and EMU: some reflections », Legal Working Paper Series, n° 10 / December, European Central Bank); Helmut

This point has been stressed by M. Caron.

J. Grosdidier and R. Zanolli have emphasized the importance of the accurate institutional design of the complementary currency.


Aubrun Michelle
email: michelle.aubrun@thalesaleniaspace.com

Troya-Galvis Andres
email: andres.troya-galvis@thalesaleniaspace.com

Albughdadi Mohanad
email: mohanad.albughdadi@terranis.fr

Hugues Romain
email: romain.hugues@thalesaleniaspace.com

Spigai Marc
email: marc.spigai@thalesaleniaspace.com

Unsupervised learning of robust representations for change detection on Sentinel-2 Earth Observation images

Keywords: Change detection, Unsupervised method, Artificial Intelligence, Sentinel-2 data, vineyard use case

The recent popularity of artificial intelligence techniques and the wealth of free and open access Copernicus data have led to the development of new data analytics applications in the Earth Observation domain. Among them, is the detection of changes on image time series, and in particular, the estimation of levels and superficies of changes. In this paper, we propose an unsupervised framework to detect generic but relevant and reliable changes using pairs of Sentinel-2 images. To illustrate this method, we will present a scenario focusing on the detection of changes in vineyards due to natural hazards such as frost and hail.

Introduction

With the advent of the Copernicus program and its wealth of free and open data, the Earth Observation (EO) domain is increasingly adopting automatic or semi-automatic data analytics applications, based on artificial intelligence techniques. Using the spectral richness (13 bands), the fine temporal (few days) and spatial resolution (10 meters per pixel) of Sentinel-2, a lot of use cases can be carried out in di-verse sectors, and in particular those related to vineyard health assessment. Winemaking is one of the largest industries that represents a turnover of several billions of euros in France. However, this industry faces severe meteorological challenges such as frost and hail, that can cause significant loss in wine production. After such meteorological events, winemaking farmers need to evaluate the level of damage that occurred in their vineyards in order to receive subsidies from the state and the European insurances. Additionally, insurance companies must also estimate the damage levels using field visits in order to check the information provided, which is non-trivial and requires a huge budget and workforce. Coupling these Copernicus data with an appropriate change detection model will allow farmers and insurance companies to easily build a complete damage profile of the vineyards in case of any natural hazard.

In this context, a generic change detection application on Sentinel-2 time series was developed as part of CANDELA [START_REF]CANDELA project[END_REF], an H2020 research and innovation project. Since the tool provides generic changes, many use cases can take full advantage of it in order to save time, effort and budget.

The rest of this article is structured as follows. Section 2 presents a brief review of existing change detection methods. Section 3 describes the methodology, and Section 4 is dedicated to the experiments and results obtained on the selected use case. Finally, Section 5 discusses our conclusions and future work perspectives.

Related work

Change detection is a well-known problem in the remote sensing community, thus several approaches have been developed to tackle this problem. The most classical approaches rely on pixel difference, image regression, image rationing, radiometric index difference, and metrics based on mutual information or correlation indexes [START_REF] Ashbindu | Review Article Digital change detection techniques using remotely-sensed data[END_REF].

Other approaches compute a distance metric on manually engineered feature spaces such as the Laws filters presented in [START_REF] Kenneth | Textured Image Segmentation[END_REF]. Although these methods are fast and easy to interpret, they are sensitive to noise and often detect subtle but irrelevant changes.

Other approaches rely on machine learning to classify the image pixels into relevant classes and then verify that the class of a given area has not changed between the two images [START_REF] Serra | Post-classification change detection with data from different sensors: Some accuracy considerations[END_REF][START_REF] Alboody | Post-classification and spatial reasoning: new approach to change detection for updating GIS database[END_REF]. Such methods provide additional information about the nature of the changes, but they are very task-specific and require labeled data in order to learn the classifier in the first place.

More recently, some approaches start making use of deep learning techniques such as Generative Adversarial Networks [START_REF] Maoguo | Generative Adversarial Networks for Change Detection in Multispectral Imagery[END_REF] or U-Net [START_REF] De | Unsupervised Change Detection in Satellite Images Using Convolutional Neural Networks[END_REF] to infer the change map directly from the two images.

Since labeled data is scarce and expensive to produce, we propose an unsupervised framework to detect generic but relevant changes between pairs of Sentinel-2 images.

Methodology

Change Detection Service

The proposed Change detection service has been implemented on Candela platform. As seen in Fig. 1, the pipeline is composed of several modules. The first one, named Jpeg2Tiff, consists in extracting the bands of interest, resampling them to get the same spatial resolution for all bands and concatenating them to obtain a single geoTiff image for each Sentinel-2 product. The second module, named Preprocess, verifies that all images provided represent exactly the same area and sorts them in the chronological order. And the last module, named ChangeDetect, computes the change detection maps for each pair of consecutive images of the time-series.

Framework

The proposed framework to generate the change detection map consists in projecting the image pixel space into a more robust feature space which is learnt by a neural network E. Then, computing a distance metric M between two encoded images in order to determine a change score. This whole framework can be described as follows:

( ) ( ( ) ( )) (1)
where and are the two images to be compared, which are split into individual patches on which the encoding and the subsequent distance are computed.

Approach and implementation

In order to generate models of robust representations, an unsupervised approach based on stacked autoencoders [8, 9 & 10] was explored. Stacked autoencoders consist in two sub-networks, the first one is used to compress the input data into a fixed-length representation, while the second one tries to decompress this representation in order to obtain the initial data back. The networks are trained from only one image by minimizing the following loss:

( ) ( ( ( ))) (2)
where x is an input image, e is the encoder network, d is the decoder network, and MSE is the mean squared error. In conclusion, the decoder network learns to reconstruct the input image from a compressed representation, forcing the encoder network to capture the main features of the image and discarding the noise.

Two different architectures of stacked autoencoders have been implemented:

• Dense autoencoder whose architecture makes use of one fully connected layer during the encoding and decoding steps. • Convolutional autoencoder whose architecture is a fully convolutional network made of successive 3x3 convolution layers with 256 filters and stride 2 until the feature map size is reduced to 1x1. The decoder makes use of inverse convolutions until the feature map size is the same as the input image. For both architectures, we used Adam for the optimizer function, a value of 0.001 for the learning rate, and a linear activation function for the last layer.

Experiments

Data description

To demonstrate the applicability of our approaches, a region of interest (ROI) near Bordeaux in France, well-known for its wine and affected by frost on 27th April 2017, was selected (-0.3868367W, 44.5202483N: 0.1090724E, 44.7963392N). Two optical Sentinel-2 Level-2A (atmospherically corrected) data products of the T30TYQ tile with low cloud cover on the ROI were used for the analysis. One acquired during 19th April 2017 (before the frost) and the other during 29th April 2017 (after the frost). These products contain 13 spectral bands in the visible, near infrared and shortwave infrared part of the spectrum with different spatial resolutions.

To quantify the level of change (low, middle or high) at vineyard parcel level, a vector dataset containing 11355 parcels from the French Parcel Registration System [START_REF]French Parcel Registration System[END_REF] was also used.

Settings

The training data come from a Sentinel-2 Level-2A image from Toulouse with low cloud cover. This image have been tiled into normalized patches of 5x5xN pixels with N the number of bands. For our vineyard use case, we have decided to consider all the bands at 10 and 20 meters of resolution, what represents 10 bands, and resample them according to the blue band. Thus, our models were trained on 65536 patches of 5x5x10 pixels selected randomly by the algorithm for 10 epochs. The models are based on the architectures presented in section 3.3 and provide a 25-dimensional vector that corresponds to an encoded representation of the patch in another feature space. Thus, the shapes of the different layers for the dense encoder are 5x5x10  1x250  1x25, and for the convolutional encoder are 5x5x10  3x3x256  2x2x256  1x1x256  1x1x25. Both models are available on Candela platform. The testing data correspond to the two images of our vineyard use case. The same pre-processing procedure as the training image was applied to encode all possible patches. Finally, the L2 distance between each pair of encoded feature vectors have been chosen to measure the amount of change.

Results

To evaluate the performance of our method, we have asked an expert, who has a dual competence in remote sensing and agronomy and whose job is to extract accurate and relevant information from images, to create a ground truth of change levels from the Sentinel-2 Level-2A images. As the analysis takes a lot of time, the ground truth has been done on an area that contains 253 parcels. Fig. 2 shows the ground truth, the results generated by our framework with using both models described in section 4.2 and the result generated by our framework without applying any model. We can see that the results generated by our approach seem more similar to the ground truth than the approach where data are not projected into a learnt feature space. To quantify these similarities, we have extracted the median values of the different change detection maps at parcel level and considered the correlation coefficients as the evaluation metric. The correlation coefficient values were 0.79, 0.80 and 0.56 for respectively the frameworks with the dense encoder, the convolutional encoder and without encoder. These scores prove the efficiency of our approaches compared with classic approaches.

Conclusion

In this study, we have demonstrated on a real use case the effectiveness of our unsupervised approaches to provide trustworthy change detection maps. These approaches lead to generic change level maps, but coupling with vector datasets, the type of changes can be specified and the percentage of changes estimated. Thus, these results may facilitate the work of many operators in different sectors.

Fig. 1 .

 1 Fig. 1. Change detection pipeline

Fig. 2 .

 2 Fig. 2. Comparison of change detection results get by a Remote Sensing Expert (up-left), dense encoder (up-right), convolutional encoder (down-left) and without encoder (down-right). Change levels; violet: low, orange: middle, yellow: high

Acknowledgements. The work presented in this paper was supported by the H2020 CANDELA project under grant agreement No.776193


Richa Dhingra

Hansraj Satyam Verma

Alexandre Reiffers-Masson

Veeraruna Kavitha

Multi-page Menu Recommendation in Cascade Model with Externalities

Keywords: recommender system, dynamic programming, online learning, perturbation analysis, cascade model, stochastic system, sponsored search

In this paper, we consider a variant of the cascade model of customer behavior, where the customer browses through a multi-page menu, scanning each page from top to the bottom predominantly. Each page is assigned items belonging to a specific class out of a set of such classes. He/she adopts the first most attractive content, which generates some revenue. We aim at maximizing the total revenue by finding an optimal index-based policy for ranking the content when the customer preferences and patience levels are known. When we have no prior information about the customer, we design the Online Greedy Algorithm (OGA) which we prove to be asymptotically converging to the optimal solution with probability one. We also provide high probability finite-time convergence bounds for the same.

I. INTRODUCTION

A Recommender System (RS) is an information filtering system, designed to predict or influence the behavior of the user based on the digital footprint left by him/her [START_REF] Ricci | Introduction to recommender systems handbook[END_REF]. These systems have diverse applications, e.g., in Sponsored Search advertisement, product-recommenders for online-purchase portals etc. A recommendation list owner is interested in maximizing the click-through rate, the probability that one of the items will be clicked. The larger the click-through rate, the larger the expected revenue. Alternatively one might have different levels of preferences for click-through rates of different items.

There have been models [START_REF] Edelman | Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords[END_REF], [START_REF] Varian | Position auctions[END_REF] based on the assumptions that the click-through rate of item i depends solely on the attraction probability of the item i and the location of the slot which it is assigned. Such models overlook the effects of other items shown on the same page. An item with lower revenue generation placed more prominently may detract the customer from another item which generates higher revenue but is assigned a lower position on the page. Moreover, an expensive item placed at a higher spot may have lower attraction probability for a customer as compared to a less expensive item assigned a lower spot. Thus, different items on a page appear to alter each others click-through rates.

In this paper, we aim at maximizing the revenue generated by a multi-page menu by taking into account this externality effect items have on each other. This menu consists of different classes of items on each page. The problem can be viewed as an allocation problem of the classes to the pages and of the items to the slots within those pages.

Our model: We focus on a model which recommends items based on user rating when certain groups/classes of products are present. We aim at finding the optimal ordering for a menu consisting of these classes of items using the click-log data of the customer. The menu consists of several pages, each page containing a certain class of items. The customer is interested in consuming/adopting one of the item on this menu. He scans each page from the top to bottom predominantly, however, can follow a random browsing pattern too. We term the customer's browsing pattern as general browsing. He can leave the menu mid-way if he is not able to find something of his interest or if he starts to get disinterested while browsing the list. The menu is such that items and the pages are displayed in a specific order and this order will impact the decision of a customer to adopt a given item. We model the behavior of the customers using parametric Markov chain. Since the click-data has an inherent position-bias effect, therefore the customer's attraction towards the list of items is not just dependent on the list of items shortlisted but also on the order in which that list is presented. This is due to the decay observed in the click through rate, with increase in rank. [START_REF] Craswell | An experimental comparison of click position-bias models[END_REF], [START_REF] Reiffers-Masson | A generalized fractional program for maximizing content popularity in online social networks[END_REF] Additionally, we are finding a recommendation for the customer that helps the recommendation owner (or menu designer) maximize the utility he seeks through the decisions taken by the customer who is presented with it. This helps in offering services that meet the needs of both the players.

Organization and Main Results: The organization of the paper is as follows: In section II, we describe the model and the utility that the owner of the recommendation list is interested in. We also define Look Only Ahead browsing (LoA), i.e., where the user scans the items from top to down, in the context of our model. We provide a perturbation result which shows that there exists a subset of cases with general browsing where the optimal ordering policy for LoA browsing is optimal. In section III, we derive the optimal ranking for LoA browsing when the parameters of the model are known. In section IV, we provide an online learning algorithm (called OGA) which converges to the optimal policy by observing the partial feedback of the customer. The convergence is proved w.p. 1 and we also derive a high probability bound for finite time convergence. In section V, we provide extensive numerical experiments to illustrate the optimal ranking given in this paper. We also include plots illustrating the converging behaviour of OGA to the optimal ordering policy. Finally in section VI, we briefly conclude our work.

Related Work:

The model used in this paper is a variation of the simple Cascade model of customer behaviour. In a simple Cascade model, the user is presented with a list of K items ordered in a specific order. The user browses the menu starting from the first item to the last item in a top to down manner and selects the first attractive item and quits the session thereafter [START_REF] Kveton | Cascading bandits: Learning to rank in the cascade model[END_REF]. The authors in [START_REF] Kempe | A cascade model for externalities in sponsored search[END_REF] focus on a variation of this model called the Slated cascade model. They provide an optimal ordering policy by considering externality effect. However, they considered a special case of user browsing pattern where every user scans any page from top to bottom (until stopping the scan).

We relax this restriction in our work. The user will predominantly scan from top to bottom, however, he can browse items randomly in any order on a given page. We also consider the existence of classes of items to be ranked on different pages. As a result, the model considered in this paper differs from the Slated Cascade model in [START_REF] Kempe | A cascade model for externalities in sponsored search[END_REF]. In fact, the results of this paper can be considered as an extension of their work to a more general environment. Also, in this paper, we have suggested an algorithm that not only provides an ordering scheme for items but also helps in learning the key parameters that drive the behavior of the users (attraction probabilities and impatience level).

There are some timeline based models that study the influence on a customer's choices by other customers present in the social network as highlighted in [START_REF] Hargreaves | Biases in the facebook news feed: a case study on the italian elections[END_REF], [START_REF] Reiffers-Masson | Timelines are publisher-driven caches: Analyzing and shaping timeline networks[END_REF], [START_REF] Dhounchak | A viral timeline branching process to study a social network[END_REF]. There are other models like [START_REF] Craswell | An experimental comparison of click position-bias models[END_REF] that attempt to explain the positionbias effect present in the customer click logs and ways to model it. This is especially seen in the cascade models that tend to impact the customer's decisions.

II. MENU OF MENUS WITH GENERAL BROWSING

Consider a menu containing different pages. On each page, items belonging to one specific class are displayed. Let C :" t1, ¨¨¨, Cu represent these classes. The class c P C contain I c number of items, given by I c " t1, ¨¨¨, I c u. The items are categorised into different classes based on their properties (e.g., physical properties like color, shape).

Menu Ordering Policy: Let Π :" pP 0 , P 1 , P 2 , ¨¨¨P C q denote the set of permutation matrices (menu ordering policy) For a class c P C, P c (with c ě 1) represents the permutation which characterizes the ordering of items of class c on a page. P 0 corresponds to inter-page orderings, and assigns the classes of items to the pages. For simpler notations, we use index 0 to represent quantities related to inter-page entities. Let ∆P be the set of all tuples of permutation matrices.

Given a policy Π, we introduce some notations (characterized by this policy) which we will be using in this paper. P 0 explicitly denotes the permutation matrix rrp cp ss 1ďp,cďC used for assigning the classes of items to pages. Here, pcp " 1 if class c has been assigned to page p and is equal to zero otherwise. s " rs p s 1ďpďC denotes the corresponding vector notation of the ordering of the menus where sp P C represents the class displayed on page p. Also, let vector r " rr c s 1ďcďC denote the mappings of the classes to the respective menu page i.e. the c th component of r denotes the page that class c P C has been assigned to. For a fixed permutation Π, let s p,k be the item from class sp to be placed at position k within the page p. Let r c,i denote the position of item i within the page p :" rc from class c. Finally, for any probability value q we will write 1 ´q as q.

General Browsing: The customer starts the browsing session with the content at position 1 on page 1. If the user gets attracted to an item, he/she buys it and a revenue is generated. β c,i denotes the attraction probability of an item i belonging to class c and w c,i denotes the revenue generated when it is bought. Upon observing the item at position k on page p, the customer takes a sequence of 3 decisions: (i) With probability α p,k :" β sp,s p,k , the customer will buy the item and generate revenue ω p,k :" w sp,s p,k . When doing so, the customer is automatically logged out of the session. (ii) If k ă I sp and the customer does not buy item at position k, then, with probability γ p , he stops scanning the menu and exits the process. (iii) If the customer decides to continue scanning (w.p. γ p " 1 ´γp ), then the customer predominantly scans the item at the next level, but has small probability of going back and forth on the list displayed in any page. Let m p k,l be the probability that the customer scans item at l-th level after scanning the item at k-th level on p-th page.

To simplify the notations and analysis1 , we make the following assumptions with respect to the browsing behaviour: ' We assume that a customer can only browse randomly within a page, but cannot go back and forth across the pages. ' We also assume that m p Is p ,j " 0 for all j ď I sp . i.e. if a customer reaches the end of any page without buying an item, then with probability γ 0 he will quit the menu and with probability γ0 " 1 ´γ0 he will directly go to the next page. The customer will not go to some other level within the same page once he is in the last level. This assumption also implies that if the customer reaches the last item of the last page of the menu (pp, kq " pC, I sC q) without purchasing any item, then he automatically quits the session. ' We fix m p k,k " 0 for any k " 1 . . . I sp . It is a reasonable assumption that if a customer does not buy an item on the current level and does not intend to quit either, then he will not come back to the current level in the immediate nextstep. Let M p When a menu is designed using the ordering pol-icy Π, the overall browsing process including the quitting possibilities can be summarized through the matrix M pΠq " rr mp,p 1 k,k 1 ss 1ďp,p 1 ďC,1ďkďIs p ,1ďk 1 ďI s1 p of dimension I ˆI, where I :" ´řC p"1 I sp ¯, given by: M pΠq "

» - - - - - - - - - - γ1 M 1 γ0 T 1 O 1,3 ¨¨¨O 1,C O 1,C O 2,1 γ2 M 2 γ0 T 2 ¨¨¨O 2,C´1 O 2,C . . . . . . . . . . . . . . . . . . O C´1,1 ¨¨¨¨¨¨¨¨¨γ C´1 M C´1 γ0 T C´1 O C,1 ¨¨¨O C,3 ¨¨¨¨¨¨γ C M C fi ffi ffi ffi ffi ffi ffi ffi ffi ffi fl
where O p,p 1 is the zero matrix with dimension I sp ˆIs p 1 , and T p is the I sp ˆIsp`1 dimensional matrix representing transitions from page p to the next one (e 1 , is all zero vector, except for first component which is one)

Tp " " OI sp ´1ˆI sp`1 e1  .
We derive an optimal menu design with the aim of maximising the overall expected revenue generated for cases with small values of .

Look Only Ahead (LoA) Browsing: We define M 0 pΠq to represent a specialized browsing pattern, in which the customer only scans the next item down the list, i.e., when " 0. In this case, the matrices tM p 0 u p are upper triangular matrices such that m p k,l " 1 if and only if l " k `1. In the next section, we show that for small values of , the optimizers for general browsing setting converge to the the optimizers of LoA browsing setting.

Expected revenue for given policy Π: Let R p pk; Πq be the conditional expected revenue, under ordering policy Π, when user starts browsing from position k on page p. The expected conditional revenue derived by the system for a given user before quitting with/without purchase equals:

R p pk; Πq " α p,k ω p,k `ᾱ p,k ÿ p 1 ,k 1 mp,p 1 k,k 1 R p 1 pk 1 ; Πq (1)
1 ď p ď C, 1 ď k ď I sp .
Define f pΠ, q " R 1 p1; Πq. The menu designer is interested in the optimal menu ordering policy pΠ ˚q defined by:

f ˚p q :" max ΠP∆P f pΠ, q " f pΠ ˚, q (2)
For different values of , we define the set of optimizers as:

Π ˚p q :" arg max Π f pΠ, q. (3)

Theorem 1. [Perturbation]

There exists ¯ ą 0, such that the set of optimizers for any -system is same as that for LoA system, i.e., Π ˚p q " Π ˚p0q for all ď ¯ . ♦

Proof: Appendix (VII-A).

In view of the above theorem, we now derive an optimal menu using optimal menu(s) of LoA system, i.e., from Π ˚p0q.

III. MENU OF MENUS WITH LOA

We have the same setup as defined in the previous section with extra assumption that " 0. Let f pΠ, 0q be the revenue generated by the menu when the items are laid out on the menu according to ordering policy Π " pP 0 , P 1 , ¨¨¨, P C q with classes sorted on different pages as per order P 0 and each class c on the page is ordered as per the order P c . Then, mathematically, we have :

f pΠ, 0q " C ÿ c"1 W c pΠq, where, (4)
W c pΠq :"

ÿ iPIc q c,i pΠqw c,i , (5)
q c,i pΠq :" γprc´1q

0 ś rc´1 p"1 κ sp γIs p ´1 p (6) β c,i rc,i´1 ź k"1 γrc βc,s rc ,k ,
with κ c :" ś iPIc βc,i . Here, q c,i pΠq can be interpreted as the probability that the customer will buy item i belonging to class c, when the classes are ordered according to permutation matrix P 0 and the items for the class c are ordered according to P c , c ą 0. The menu designer is interested in finding the optimal permutation Π ˚that maximize the overall expected revenue obtained i.e.

f ˚p0q " max Π f p0, Πq.
The model setting considered in the [5, Lemma 1] can be seen as a special case of the Look Only Ahead (LoA) browsing where the authors devise an ordering scheme based on the score or index value given through the function hp.q (defined below) for a menu containing only one page and having items from one particular class.

Definition III.1. For a given class c P C assigned to page p where the quitting probability is γ p , we say that item i 1 is bigger than item i 2 , according to the rule h (represented by, i 1 ą Θ h i 2 ) if hpi 1 ; Θq ě hpi 2 ; Θq. Here, hpi; Θq is defined as:

hpi; Θq :"

β c,i w c,i 1 ´γ p βc,i . (7)
where β c,i and w c,i are the attraction probabilities and price of item i respectively, note the ordering depends upon the parameters, Θ :" ttβ c,i , w c,i u l , γ p u.

We refer to ordering scheme given based the score/index given by the above function as the h-index ordering policy. In the following theorem, we further extend the scope of [5, Lemma 1] to a more generalized menu by trying to construct an optimal menu of menus for LoA system using an h-index based ordering scheme.

Theorem 2. Assume γ p " γ for all p. Then, the optimal menu of menus that solves (2) for LoA system is given by the following: (i) Let ri 1 , i 2 ¨¨¨, i Ic s be the optimal order of the items of a class c, then

i 1 ą Θc h i 2 ą Θc h , ¨¨¨, ą Θc h i Ic , with (8)
Θ c :" ttβ c,i , w c,i u i , γu.

(ii) Additionally, the optimal average revenue for this class c is given by:

W c " Ic ÿ j"1 β c,i j w c,i j « j´1 ź l"1 βc,i l γff . (9)
(iii) Let rc 1 , c 2 ¨¨¨, c I s be the optimal allocation of classes to pages, then

c 1 ą Θ h c 2 ą Θ h , ¨¨¨, ą Θ h c I , with Θ :" ttβc, wcuc, γ0u, (10)
wc :" W c p1 ´κcγ Ic´1 q , βc :" 1 ´κcγ Ic´1 .

(iv) The optimal expected revenue for the entire menu equals:

f ˚p0q " C ÿ k"1 w c k β c k k´1 ź j"1 r βc j γ0 s. ♦ (12)
Proof: Appendix (VII-B).

IV. LEARNING THE OPTIMAL RANKING

In the previous section, we study the optimal ranking (menus) in Menu of Menus with LoA browsing and their properties. In reality, the menu designer will not know the customer behaviour related parameters, β and γ. They would only have knowledge about which items belong to which classes. In this section, we are interested in obtaining the optimal ordering policy alongside learning the above required parameters. Towards this, we provide a greedy algorithm and illustrate its convergence to the optimal performance.

In the Online Greedy Algorithm (OGA), we suggest an iterative scheme to update the estimates r βc,i s's, rγ p s's and γ0 , which then are used to choose a revenue optimal menu (for LoA browsing). One of the strengths of the OGA is that, whatever is the succession of the menus that the different customers are facing, the OGA always learns the parameters of the model (rβ c,i s i , rγ p s p and γ 0 ) and therefore optimal menu. This is true at least asymptotically as proved by Theorem 3. However, this scheme does not guarantee that the convergence of all the estimators will be quick enough to ensure sufficient accuracy (required for choosing the correct revenue optimal menu) for initial (or finite number of) customers. Proposition 4 provides a result concerning the finite-time behaviour of the algorithm.

Let t P N `represent the number of customers browsing the menu. Let Πptq be the ordering policy used to design the menu shown to the t th customer. Let θ c,i ptq P t0, 1u be the random variable associated with the event that the t th customer has seen item i from class c, and let ζ c,i ptq P t0, 1u be the random variable indicating whether or not the customer bought that item. For a given ordering policy Πptq and the associated vectors sptq " rs 1 ptq, . . . , sI ptqs, θ c,i ptq is drawn according to a Bernoulli distribution with mean equal to q c,i pΠq{β c,i (see [START_REF] Kveton | Cascading bandits: Learning to rank in the cascade model[END_REF]). Moreover, ζ c,i ptq is drawn from a Bernoulli distribution with parameter β c,i .

For each i, let v c,i ptq :" ř t t 1 "0 θ c,i pt 1 q be the number of customers that were shown item i among the first t customers, and η p ptq :" ř t t 1 "0 p1 ´ζsp,s p,1 pt 1 qq be the number of customers that did not purchase the first item displayed in the menu, for any t ě 0. Similarly, let η 0 ptq :" ř t t 1 "0 p1 ´ζs1,s 1,I s1 pt 1 qq be the number of times a customer did not purchase the item shown at the last level of page 1. Recall that s1 , s 1,I s1

is the item displayed in the last level of page 1. We assume here that one can observe the items (among the menu) seen by the customer. Define step size sequences taptq " 1 t`1 u Ă p0, 8q. Algorithm Explanation: We initialize the algorithm with a price based policy (i.e., arranging items within class in decreasing order of their prices and then arranging the classes in the decreasing order of w c ). Observe that ζ sp,s p,k ptq denotes whether the t th customer bought the item in level k at page p. Similarly, θ sp,s p,k ptq denotes whether the t th customer bought the item in level k at page p. Thus, given a customer bought an item at page p q in level k q , (13) and (14) update ζ c,i to 1 for the item picked, and keep it zero for the other items. Moreover, all the items before page p q are observed. The first Indicator function in (15) updates θ c,i to 1 for all the items observed before page p q . The second Indicator function updates θ c,i for the items observed on page p q before level k q , including k q .

β Estimation: Given that we have the estimate βc,i ptq and item i was seen at time t`1 (i.e. θ c,i pt`1q " 1), βc,i pt`1q is updated using (16). Note that βc,i ptq "

ř t 1 ďt ζc,ipt 1 q vc,iptq
, where v c,i ptq gives the number of observations of the related item i belonging to class c and ř t 1 ďt ζ c,i pt 1 q ď v c,i ptq. So, the update is just an iterative form of law of large numbers.

γ estimation: For each page p, we keep an estimate of the continuation probability γ p . This is done by keeping track of the number of times we do not purchase the item at the first level of the page and continue to see the second item. η p ptq gives the number of estimates for γ p , while the estimate γp can be obtained using ř t 1 ďt θ sp,sp,2 pt 1 q (number of customers that have seen items in position 2 on page p) and η p ptq, i.e., γp ptq " 1´γ p ptq where γp ptq " ř t 1 ďt θs p ,s p,2 pt 1 q ηpptq . Thus (17) is the usual way of rewriting the sample mean estimator for γp , (which is the probability of continuing to browse for page p) using a stochastic approximation based scheme. Iteration (18) can be explained in a similar way.

Online Greedy Ranking (OGA) Initialization:

A tuple of doubly stochastic matrices Πp0q " pP 0 , P 1 , ¨¨¨, P C q. For each new customer t " 1, 2, . . . , n 1) Use the ordering policy Πptq.

2) Observe the quitting level of the customer as pp q , k q q and his last action ζ sr ptq. Compute:

ζ spq ,s pq ,kq ptq " 1, if purchased (13)
ζ c,i ptq " 0, @c, i s.t. i ‰ s pq,kq (14) θ sp,s p,k ptq " 1 păpq `1kďkq,p"pq (15)

3) Compute:

βc,i pt `1q " βc,i ptq `apv c,i pt `1qq (16)
ˆθc,i pt `1q ´ζc,i pt `1q ´β c,i ptq γp pt `1q " γp ptq `apη p ptqq (17) ˆ´θ sp,s p,2 ptq ´γ p ptq γp pt `1q " 1 ´γ p pt `1q γ0 pt `1q " γ0 ptq `apη 0 ptqq (18) ˆ´θ s2,s 2,1 ptq ´γ 0 ptq γ0 pt `1q " 1 ´γ 0 pt `1q 5) For each class c, update P 0 pt `1q where for each pp, cq, set pcp pt `1q " δ r c p ,p , with tc p u are as defined in the theorem 2. using βpt `1q and γpt `1q.

In the next theorem, we show that the above greedy algorithm converges to the optimal menu where the menu contains a single page. This result can be easily extended to prove the convergence of OGA for a menu containing multiple pages. The proof of the extension is avoided to keep the explanations simple. Theorem 3. Let I denote the item set with 0 ă β i ă 1 for all i P I and assume 0 ă γ ă 1. Let P ˚be the permutation matrix corresponding to the optimal menu order. Then, we have the following: (i) With probability one, there exists a customer index t such thatP ptq " P ˚, for all t ě t ˚.

(ii) Further, the derived time-averaged revenue W ptq, converges to optimal expected revenue with probability one: W ptq Ñ W ˚, where,

W ptq :" 1 t ÿ t 1 ďt n ÿ k"1
ζ s k pt 1 q pt 1 qw s k pt 1 q . ♦ Proof: Appendix (VII-C). Remark: The above theorem highlights the strength of OGA. It gives assurance that OGA will eventually learn all the customer parameters and converge to the optimal menu, irrespective of the noise present in the samples collected for parametric learning.

We are now interested in knowing the number of estimates required to achieve convergence with a given probability. For a given α ą 0, the following proposition proves the existence of a time index t 0 (or customer index) beyond which the algorithm converges to the optimal solution with at least probability 1 ´α. Proposition 4. For every α ą 0, there exists t 0 ă 8, such that the OGA converges to the optimal menu, for all t ě t 0 , with probability 1 ´α. Here t 0 is solution of:

r2 ´p1 ´di `di expp´d 2 {2 K 2 qq t ṕ1 ´q `q expp´d 2 {2
K 2 qq t s 0 ě 1 ´α, with rxs 0 " maxt0, xu, d " min i,jPI;i‰j | hpi; Θq hpj; Θq | and q " 1 ´max iPI β i . In other words, for every α ą 0, there exists a finite t 0 ą 0 such that: P rP ptq " P ˚, for all t ě t 0 s ě 1 ´α. ♦

Proof: Appendix (VII-D).

V. NUMERICAL EXPERIMENTS

A. Perturbation Analysis

In this section, we compare the optimal expected revenue for a given system and the expected revenue obtained by the optimal ordering of the equivalent LoA system. We compute both the Monte-Carlo estimate and the theoretical value for the expected revenue and plot them. For the Monte-Carlo estimates, we averaged the revenue obtained over 1000 customers. The theoretical value was obtained using numerical computations. For a given and policy Π, the corresponding revenue can be obtained by solving for R 1 p1; Πq in (1). The theoretical benchmark value was obtained by going through each possible permutation of menus and picking the policy which gives the highest revenue. The theoretical value for hindex menu was obtained by using the h-index policy (say Π h ) for " 0 (LoA system) to calculate R 1 p1; Π h q for different values of . The graphs in Fig. 2. show the plot for expected revenue for a system with three classes having 4, 3 and 3 items. We have also included the plot for the expected revenue on using a price-based menu. We take γ 0 " 0.5 and consider two instances of this system with different levels of user patience within the pages, specifically γ " 0.1 (in the left sub-figure of Fig. 2) and 0.5 (in right sub-figure). The attraction probabilities and prices in both are fixed and are inversely proportional. We observe that as the quitting probability γ increases, the h-index menu gives better approximations for the optimal revenue for larger range of (in right sub-figure). As we decrease the quitting probability, the menu obtained by hindex gives good approximations for lower range of . The percentage revenue loss at " 1 for first and second graphs in Fig. 2. is 7.448% and 3.9339% respectively. The green plot shows the performance of a price-based menu, which is significantly inferior.

We also observe the performance of h-index menu in a system with different γ p for different pages, in particular with increasing values of γ p over the pages. Fig. 3 shows the performance of the same h-index menus as in Fig. 2 (by taking γ " 0.1 and 0.5), except that now we have the quitting probabilities γ p " 0.1, 0.2 and 0.3 for the first system (in the left sub-figure of Fig. 3) and γ p " 0.5, 0.6 and 0.7 for the second system (in the right sub-figure of Fig. 3). The percentage revenue loss at " 1 for first and second graphs in Fig. 3. is 7.5488% and 3.9534% respectively. We observe that small changes of γ p across different pages do not severely affect the performance of hindex menu. Price based menu is once again significantly inferior. Fig. 4 (left sub-figure) portrays another example Fig. 4: (left) γ 0 " 0.3; (right) γ " 0.4, γ 0 " 0.5 with C " 3, and same number of items as before in each class. It contains the plots of theoretical values and not the Monte-Carlo Estimates. We take two different sets of γ p . Three h-index menus are generated for each of the two cases, by using γ 1 , γ 2 and γ 3 to create the menu. In this example, the level of user patience changes more significantly along the pages. For case (a), γ p " t0.2, 0.4, 0.7u. The percentage revenue loss at " 1 is 5.059%, 3.839% and 3.8588% for the three created menus. However, the average percentage revenue loss is 2.336%, 2.577% and 2.585% respectively. For case (b), γ p " t0.4, 0.7, 0.9u. The percentage revenue loss at " 1 is 2.474% while the average percentage revenue loss is 0.594% and both values change negligibly for other values of γ p . We observe that for lower levels of user patience (case (b)), all three h-index policies perform optimally for a significant range of . For case (a), h-index policy corresponding to γ 1 performs optimally for a smaller range of . h-index policies corresponding to γ 2 and γ 3 do not perform optimally for any . We observe that as user patience gets higher, h-index policy may perform suboptimally. However, such scenarios are less likely to be observed.

B. Finite-Time Convergence Rate of OGA

The graph in Fig. 4 (right sub-figure) shows a sample path of the time averaged revenue for the Online-Greedy algorithm in LoA system. We take C " 3 and number of customers " 3000. The 3 classes have 7, 7 and 6 items respectively. The initial policy is taken to be a price-based policy and over-time as the parameter estimates get better, we start converging to the h-optimal policy. The graph portrays the result proved in theorem 3 regarding the convergence of the policy given by OGA to the optimal policy. The expected revenue received by implementing OGA seems to asymptotically converge to the benchmark value. Even from the point of view of finite-time analysis, it can be observed that after 3000 customers, the percentage revenue loss is 7.017% when using the policy obtained by OGA.

VI. CONCLUSION

In this paper, we extend the results of [START_REF] Kempe | A cascade model for externalities in sponsored search[END_REF] where authors focus on a Slated cascade model. We drop the assumption that customer will scan the items from top to bottom as assumed in [START_REF] Kempe | A cascade model for externalities in sponsored search[END_REF] and introduce a variation by considering classes of items. We find the optimal ordering policy for LoA browsing and prove its optimality even for instances of browsing which are not LoA. We propose a learning algorithm that learns the model parameters efficiently and derive mathematical results regarding its convergence to the optimal ordering policy. Moreover, experiments show that the h-index policy performs well in general browsing scenarios especially when user patience is not high, which is highly likely.

Fig. 1 :

 1 Fig. 1: Example, 2-Page menu with 2 classes (5 & 4 items), ᾱp,kprobability of not buying item at level k of page p, after inspection.

Fig. 2 :

 2 Fig. 2: C " 3; γ 0 " 0.5; γ " 0.1 and 0.5 for the first and second graphs respectively

One can easily consider back and forth behaviour across the pages, and take m p I sp ,j pj ď I sp q to be non-zero. An analysis equivalent to the one given in this paper will hold.

VII. APPENDIX

A. Proof of theorem 1

Consider Π P ∆P . We begin by showing the continuity of f pΠ, q. Rewriting the system of equations in [START_REF] Craswell | An experimental comparison of click position-bias models[END_REF] in the vector form, we have:

where B is an IˆI diagonal matrix, having entries p1´α p,k q for 1 ď p ď C, 1 ď k ď I sp . For the sake of understanding, the explicit form of M pΠq where Π assigns a class having 4 items on page 1 and a class of 3 items on page 2 is given below:

To establish the continuity of R p pk; Πq, we first need to show that pI ´BM pΠqq ´1 exists. Towards this, consider the continuity of pI ´BM pΠqq ´1 at " 0 and observe that BM 0 pΠq has non-zero elements only in positions pi, i `1q with 1 ď i ď I ´1 and hence pI ´BM 0 pΠqq ´1 exists as DetppI ´BM 0 pΠqq ´1q ‰ 0. As Ñ 0, BM pΠq Ñ BM 0 pΠq for any given Π. As the determinant is a continuous function, there exists an ˆ such that pI ´BM pΠqq ´1 exists @ P r0, ˆ s and is continuous in . Since there are finitely many Π, one can choose a common ˆ for all Π. Thus, R p pk; Πq is continuous @ P r0, ˆ s for every possible p, k, Π. Specifically, R 1 p1; Πq is continuous, i.e., f pΠ, q is continuous @ P r0, ˆ s, for all Π.

Finally, let Π 0 P Π ˚p0q, be any optimizer at " 0. Then,

Define the following function of , gp q :" f pΠ 0 , q ´max ΠP∆P,ΠRΠ ˚p0q f pΠ, q.

We know that f pΠ 0 , q and f pΠ, q are both continuous for P r0, ˆ s, and max function applied over a continuous function is continuous. Therefore, gp q is continuous @ P r0, ˆ s. Using gp0q ą 0 and the continuity of g, there exists another ¯ ď ˆ such that gp q ě 0 for all ď ¯ . Thus from (19), the policy Π 0 is also optimal for system with any 0 ď ď ¯ . ♦

B. Proof of theorem 2

For any policy, Π " pP 0 , P 1 , . . . , P C q, let:

and let the conditional revenue for any class c, given ordering P c , be denoted as:

Consider an optimal policy for any class c,

We first prove the following:

Using ( 5) and (20), we have:

Substituting the value of q c,i from ( 6) and taking γ p " γ for all pages, we get the following:

From the above equation, it can be easily observed that for any Π " pP 0 , P 1 , . . . , P C q, (22) holds true. We emphasize that the assumption γ p " γ for all pages p is needed for the above inequality to hold true. As the set of all permutations is finite, We can directly take the max on both sides in (22) to get:

(24) is true because Π ˚:" rP 0 , P 1 , ¨¨¨, P C s can achieve the equality where P 0 optimizes the right hand side. Finally, [5, Lemma 1] can be used to solve the optimization problem (21) for each c. This proves part piq and piiq of the theorem. Further V ˚:" max Π V pΠq equals

which can be rewritten in the following way, that facilitates using [5, Lemma 1] again now across the pages,

where the consolidated terms tw c , β c u are defined in equation (11) in the theorem. Thus, part piiiq and pivq of the theorem follow by applying [5, Lemma 1] to (25). ♦

C. Proof of theorem 3

Since we only have a single page, we use all the previously defined notations without the subscript c, for simplicity. For any item i, let p i be the minimum probability of a typical customer visiting item i, among all the possible permutation matrices, i.e., p i :" min

where q i pP q is equivalent to [START_REF] Reiffers-Masson | Timelines are publisher-driven caches: Analyzing and shaping timeline networks[END_REF]. Clearly p i ą 0 for all i, since for all i, 0 ă β i ă 1, 0 ă γ ă 1 and the number of permutations |P| is finite. One can lower bound v i pnq by (coupled) binomial random variable Binpn, p i q which converges to 8 as n Ñ 8 with probability one (w.p.1). Therefore, v i pnq Ñ 8 as n Ñ 8 w.p.1 and hence by strong law of large numbers, all the beta estimators converge to their respective true values w.p.1. The same is the case with estimator of γ. The h-index ordering given by ( 7) are defined using continuous functions of rβ l s l and γ, hence there exists a neighbourhood of true values pγ, rβ l s l q, for which the menu chosen using h-index rule [START_REF] Reiffers-Masson | Timelines are publisher-driven caches: Analyzing and shaping timeline networks[END_REF] in Update step of OGA equals that given by the optimal one of the theorem 2. This proves part (i) of the theorem. Part (ii) immediately follows from part (i), once again by law of large numbers (applied to iterates after t ˚). ♦

D. Proof of proposition 4

Approach: The proof of the theorem is a sophisticated application of the Hoeffding's inequality after bounding the distribution mean of the number of observations/samples for all the items from below.

We denote f pw, β, γq " wβ 1´p1´γqp1´βq which is a Lipschitz function where we let K be the associated Lipschitz constant. We define M βi pv i ptqq " β i ´β i ptq and M γ pηptqq " γ ´γptq as the noise observed while estimating the parameters for customer preference and patience level respectively. For every i P I, the following implies that:

Now, we have to recall the following fact: For any x 1 , y 1 , x 2 , y 2 P R, we have x 1 `x2 , y 1 `y2 sharing the same ordering relation as

We do not prove this fact due to its simplicity.

We aim to show that for all the items of the set I, if the difference in the estimators for the hp.q are bounded, then the menu ordering obtained through the estimators coincides with the optimal ordering. Therefore, if for every i, g i ă d, then the optimal order is preserved. Consider the sequences of noises tM βi pv i ptqqu tě1 and tM γ pηptqqu tě1 . We aim to prove that there exists t o such that with at least probability 1 ´α, for every t ą t o we have the sequence of estimators t βi ptqu tět0 and tγ tět0 u preserving the optimal ordering.

for all t ě t o . If α i ď α I , with P rg i ď ds ě 1 ´αi , then by Frechet inequality, we know that: P rX i g i ď ds ě r ÿ i p1 ´αi q ´pI ´1qs 0 ě r1 ´αs 0 , with rxs 0 " maxt0, xu. By using Frechet inequality, we have reduced the problem to finding t 0 ą 1, such that for all t ą t 0 :

Now, we use Hoeffding's inequality to bound the above probability for a fixed value of v i ptq. After taking expectation on both the sides and bounding the mean of v i ptq by d i from below, we get:

By Hoeffding's Inequality, we have:

Ṅow, applying the Hoeffding on v i ptq first, we have:

expectation on both the sides, we get that:

exp `´2t 2 j ˘pd j i qp1 ´di q n´j " 1 ´2 ˚n ÿ j"0 ppd i ˚expp´2t 2 qq j p1 ´di q n´j q " 1 ´2 ˚pd i ˚expp´2pd 1 {Kq 2 q `1 ´di q t

Note that for d 1 `d2 " d, we have :