Aurélie Lemaitre
email: aurelie.lemaitre@irisa.fr

Jean Camillerapp

Bertrand Coüasnon

A perceptive method for handwritten text segmentation

Keywords: Structure analysis, handwritten text, text line segmentation, word segmentation

INTRODUCTION

In this paper, we address the problem of the segmentation of handwritten pages into text lines and words. It is still a difficult problem as the handwriting is not constrained (slope, varying curvature inside a document) and the writing varies a lot depending on the writer (thick or thin, with large or small space between words). And yet, it is an important step for the recognition of content: the segmentation into words can significantly help the process of recognition. In this domain, the objective is to propose generic methods, which are able to deal with various kinds of unconstrained writings and various alphabets.

In this paper, we propose a new way to address this problem, thanks to the principles of perceptive vision. The perceptive vision consists of combining several levels of resolution of the images and use the saliency of structural elements. We have previously proposed to localize text lines thanks to a line segment extractor. [START_REF] Lemaitre | Text line extraction in handwritten document with Kalman filter applied on low resolution image[END_REF] In this paper, we propose now to assign each pixel to the text lines they belong to. Indeed, the use of perceptive vision is an efficient way to deal with slope and curvature, overlapping text lines and varying styles of writers.

Concerning the segmentation into words, we propose to combine two aspects: some digital data and some structural rules. Thus, we propose to combine inter/intra word distances with a structural description of the structure of a page of text.

The paper is organized as follows. In section 2, we present the related work and show the originality of our approach. Then, we present our method for both line segmentation (section 3) and word segmentation (section 4). In section 5, we detail our implementation. At last, we show the efficiency of our method thanks to an evaluation on the database of ICDAR'2009 segmentation contest and the comparison with other methods of the literature. The results show that our method is particularly suitable to detect overlapping text lines and to deal with various kinds of writings.

RELATED WORK

The topic of handwritten text segmentation has been widely studied during the last years and various kinds of methods have been proposed.

In, [START_REF] Louloudis | Text line and word segmentation of handwritten documents[END_REF] Louloudis et al. propose a complete state of the art on this topic. First, we can notice that the methods that are used for printed text analysis, such as projections, are not suitable for handwritten documents, due to the irregularity of the writings, the slope and the curvature of the text lines, and the overlapping between text lines. Thus, various works have been proposed that separate the two steps of text line segmentation and word segmentation.

For example, Li et al. present in 3 an interesting method for script independent text line segmentation but do not address in this paper the problem of word segmentation.

Most of the works on text and word segmentation have been compared during a contest at the last ICDAR 2009. [START_REF] Gatos | ICDAR 2009 handwriting segmentation contest[END_REF] We propose to synthesize in table 1 the different techniques that are used by the participants of the contest.

Authors

Text line segmentation Word segmentation Yin, Liu Among all these methods, we can pick out the works of Papavassiliou et al. [START_REF] Papavassiliou | Handwritten document image segmentation into text lines and words[END_REF] and the method of Shi et al. [START_REF] Shi | A steerable directional local profile technique for extraction of handwritten arabic text lines[END_REF] that have obtained the best results for the segmentation contest of ICDAR 2009. [START_REF] Gatos | ICDAR 2009 handwriting segmentation contest[END_REF] We can also mention that the work of Papavassiliou et al. [START_REF] Papavassiliou | Handwritten document image segmentation into text lines and words[END_REF] is one of the only works that is particularly efficient for both text line and word segmentation. These authors explain that their remaining difficulties occur when the writings are very segmented.

In order to be able to deal with any kind of writing, we have proposed in a previous work [START_REF] Lemaitre | Text line extraction in handwritten document with Kalman filter applied on low resolution image[END_REF] to combine several levels of perception of the image. Thus, we consider that having a global vision of the document (at low resolution) enables the detection of text line position, as if they were line segments. Then, the vision at high resolution enables the confirmation of the presence of text lines. However, in this previous work, we were just giving the localization of the text lines without assigning each pixel to each text line. The novelty of our work in this paper is to assign each pixel of the image to a given text line and a given word.

OUR METHOD FOR TEXT LINE SEGMENTATION

The segmentation into text lines is realized in four steps of analysis, detailed below: global localization of text lines as line segment at low resolution (figure 1

Extraction of line segments

At low resolution, the text lines appear as line segments. Indeed, at low resolution, we apply a line segment extractor based on Kalman filtering, as we described in. [START_REF] Lemaitre | Text line extraction in handwritten document with Kalman filter applied on low resolution image[END_REF] This robust operator is able to follow line segments, even if they are dotted (as text lines), curved or irregular. At the end of this step, the system emits some hypotheses on the presence of text lines that will be confirmed using high resolution analysis. This method is particularly suitable as it enables the prediction of text line position, whatever their kind of writing, thickness, slope or curvature.

Positioning of baselines

In this step, we use the global vision of the text lines in order to find the precise position of the body of the words. Thus, we have presented in 10 our operator to position the baselines of the writing, using the global context of the text line. This operator is based on the global detection of a zone of interest in the image. Then, it locally adjusts the position of the baseline, taking into account the presence of upper and lower black pixels. In this work, we find the position of three baselines: at the top, at the bottom and at the middle of the text body (figure 2). The interest of this method is to precisely obtain the position of the body of the words, even in the case of slope and curvature. This is very interesting for a process of word recognition.

Detection of overlapping connected components

The third part of the work consists of allotting each connected component to the associated text line. For this purpose, we study the position of each connected component, relative to the baselines that have been obtained at the previous step. This analysis makes it possible to detect conflicting connected components when they cross the baselines of several text lines. In that case, our method launches a re-segmentation of the connected components. We use the global perception of baselines to define the point where the connected component should be cut. In this first version of our work, our method is very simple: we segment the connected component at the average position of the upper and the lower middle baselines (figure 3). This method is not very precise, but it is enough for the proposed application. We are planning to improve this method in future work.

OUR METHOD FOR WORD SEGMENTATION

When the segmentation into text lines has been done, we can realize a segmentation into words. We propose to combine two kinds of information: digital data and structural knowledge.

Digital data

The digital data is a distance threshold between connected components.

We assume that the writings are regular inside of a same page. Thus, we compute the distance threshold for each page. For this purpose, we calculate all the distances between neighbor connected components, inside of the whole page. We choose the distance based on the Delaunay graph (figure 4). Thus, we compute a precise distance between the pixels of the connected components, 11 instead of using a distance between bounding boxes. We obtain a list of distance, from which we remove the nbl larger distances, where nbl is the number of text lines. Indeed, we consider that the too big distances will disturb the computation of the threshold. With the remaining distances, we compute a k-mean (k=2) to separate the inter and intra word distances. We obtain a threshold that will be used to group together the connected components of the same words for all the page. An example of result is presented in figure 5.

Structural knowledge

The originality of our approach is that we enrich the digital threshold between connected components by using some structural knowledge. For example, in our ground truth, the punctuation signs are always associated with the previous words. However, this may cause troubles when the writer makes a too large space between a word and the following sign (dot, coma . . . ): two separate words are computed. Consequently, we have proposed to introduce some knowledge in a post-process that groups together, when necessary, a word and the following punctuation. This is illustrated in figure 6: the words in black have been associated with the following dots and comas. This introduction of structural knowledge has been realized really simply as we work in the context of a grammatical generic method, DMOS-P.

IMPLEMENTATION WITH DMOS-P METHOD

Presentation of the method

As an example of implementation of our work, we present how we have implemented our process of segmentation using an existing method for document structure recognition, DMOS-P (Description and Modification of the Segmentation with Perceptive vision). [START_REF] Lemaitre | Interest of perceptive vision for document structure analysis[END_REF] This method is made of a bidimensionnal grammatical language, EPF (Enhanced Position Formalism), which enables a physical and a logical description of the structure of documents. For each kind of document to study, the user builds a grammatical description that consist in explaining the relative position of each structural element in the image. The terminals of the grammatical analysis are the connected components and the line segments extracted from the image. The terminals are organized into perceptive layers, that enable the cooperation between various resolution levels of the images. When a description has been realized in EPF, the associate parser is automatically produced by a compilation step.

Thanks to this EPF formalism, the knowledge is separated to the system, and the digital level is entirely guided by the symbolical description. Thus, this method is generic and can be applied on any kind of document. It has been validated on various kinds of documents: musical scores, mathematical formulas, military forms and at a large scale on more than 500,000 document pages. [START_REF] Coüasnon | DMOS: A generic document recognition method to application to an automatic generator of musical scores, mathematical formulae and table structures recognition systems[END_REF]

Our implementation

For our application, we have realized a generic grammatical description of the organization of a page of text into text lines and words. We use two levels of perception of the image, that is to say two perceptive layers that are made of:

• the line segments that are extracted in a low resolution image (dimensions divided by 16) thanks to our Kalman based extractor (called LowResolution layer),

• the connected components that are extracted in the initial image, after a binarization step (called HighResolution layer).

These two layers are the base for the grammatical description of the text lines and words.

A text line is described as a line segment at low resolution and a succession of connected components, in the same place, at high resolution. This rule is expressed as follows in the EPF language * : textLine ::= USE_LAYER(LowResolution) FOR(oneLineSegment) && AT(overLineSegment)&& USE_lAYER(HighResolution) FOR(setOfConnectedComponents).

Once every text line has been built, we can segment them into words, using the fact that a text line is a succession of words. This is expressed by arecursive rule:

textLineInWords ::= word && AT(rightWord)&& setOfWords.
where a word is described as a succession of connected components, that are close (with a lower distance than the inter-word threshold T that is computed for each page) :

word ::= connectedComponent && AT(closeEnough T)&& setOfConnectedComponents.

The main interest of this method is that it can include easily structural knowledge such as the rule presented in section 4.2. Indeed, thanks to EPF language, we can easily add another description of a word that take into account the punctuation (dots, coma). This rule is:

word ::= word && AT(rightWord)&& punctuationSign.
where a punctuationSign is a small isolated connected component.

As a conclusion, the use of DMOS-P method is very interesting as it easily enables the introduction of structural knowledge, such as the rule concerning the punctuation presented above. Moreover, as this method is generic, it enables the use of the result of text line segmentation for the analysis of more complex documents. For example, we have applied the results of the segmentation for the analysis of incoming mail and on text pages as we will show in the results. * AT is the position operator and && is the concatenation operator

APPLICATION

In order to validate the interest of our method, we present our results on the international database proposed for the segmentation contest of ICDAR'2009. [START_REF] Gatos | ICDAR 2009 handwriting segmentation contest[END_REF]

Data base

This database is made of handwritten pages, written by different writers who had to copy a given text. These pages are written in four languages: English, French, German and Greek.

We consider two sets: a training set made of 100 images, and a test set made of 200 images. For each set, we were given a ground truth that associates each pixel to its line and to its word. Some example of images are given on figure 7.

(a) (b) (c) (d)
Figure 7. Example of studied images

Metrics from ICDAR'2009 segmentation contest

The evaluation of the performance is realized by counting the number of matches between the entities (lines, words) detected by the algorithm and the entities in the ground-truth. [START_REF] Gatos | ICDAR 2009 handwriting segmentation contest[END_REF] Let N, the number of entities in the ground-truth. M is the number of entities that are retrieved by the analysis. Then, we calculate the number o2o of one to one matching entities between N and M. Two entities (lines, words) are considered as matching if they have more than a threshold S of common pixels. In the segmentation contest, this threshold S is 95% for lines and 90% for words. The detection rate DR and the recognition accuracy RA are defined as follows.

DR = o2o N , RA = 020 M
The performance metric FM is computed by combination of the detection rate and the recognition accuracy.

F M = 2 * DR * RA DR + RA

Results

We apply our method for line and word segmentation on both the training set and the test set. An example of segmentation is presented in figure 8. The obtained statistical results are presented in table 2. We obtain a very good result for line segmentation, with a performance FM of 99.25% on the test set, which means that 99.25% of text lines have more than 95% correct pixels. Concerning words, our algorithm obtains a performance of 94.20%, which means that 94.20% of words have more than 90% correct pixels. We can notice that the detection rate, DR, and the accuracy, RA, are similar for each of our processes.

The results that we have obtained on the test set enable the comparison of our approach with the methods that have been proposed in ICDAR'2009 contest. [START_REF] Gatos | ICDAR 2009 handwriting segmentation contest[END_REF] We present this comparison on table 3. We can notice that our method obtains the second place for both words and lines. Our results are very close to the first ones (about We will soon obtain other results as we have taken part to the ICFHR'2010 segmentation contest, which results will be published on November 2010. This new competition will make possible another comparison with the other methods.

CONCLUSION

In this paper, we have proposed a new method for text line and word segmentation.

For the detection of text lines, we use a method based on perceptive vision. Thus, the global perception of text lines as line segment is a way to deal with varying writings, overlapping characters, slope and curvature of text lines. Then, the use of a high resolution analysis enables a re-segmentation of connected components and a precise assignment of each pixel to each text line.

Concerning the segmentation into words, we propose to combine digital data and symbolical knowledge. Thus, we use distances obtained from Delaunay graph, in order to precisely compute an inter/intra word distance threshold, at pixel level. Then, the novelty consists of combining this digital information with structural knowledge about the organisation of the page of text, such as the localization of the punctuation.

We have evaluated our method in an international context, based on ICDAR'2009 contest. We have shown that our method obtains results that are similar to the best methods. More precisely, we propose one of the two methods that are able to properly segment both lines and words. Our method is able to deal with overlapping text lines and varied kinds of writings, which are the difficulties met by other methods. We now wait for the results of ICFHR'2010 contest, in order to improve our method. More precisely, in the future work, we are planning to use some more elaborate techniques for the re-segmentation of connected components and for the classification of intra and inter word distances.

  (a)), adjustment of the position of the baselines at high resolution (figure 1(b)), detection of overlapping connected components and re-segmentation (figure 1(c)), assignment of each connected component to the final text lines (figure 1(d)).

Figure 1 .

 1 Figure 1. Steps of our method of segmentation into text lines (image 014 of ICDAR base)

Figure 2 .

 2 Figure 2. Positioning of three baselines that delimit the text body, following the global slope and curvature

Figure 4 .

 4 Figure 4. Delaunay graph for distance computation: the vertexes give the distance between pixels of the neighbor connected components

Figure 5 .

 5 Figure 5. Words that are found by the application of the inter-word/intra-word distance threshold between connected components

Figure 6 .

 6 Figure 6. Introduction of structural knowledge: the punctuation is associated with the previous word (black boxes), instead of making two separate words

Figure 8 .

 8 Figure 8. Result of the segmentation, represented with various grey levels and bounding boxes (image 03 of ICDAR base)

Table 1 .

 1 Synthesis of the latest main methods of handwritten text segmentation

	5		Selection of edges in a Minimum Span-	Extraction of 11 characteristics about
			ning Tree	the distances between connected com-
				ponents and classification with a SVM
	Shi, Setlur, Govindaraju 6 Adaptive local connectivity map	Convex hull distance and threshold
				based on mean and variance
	Rivest-Hénault, Cheriet 7	Text smearing and morphological oper-	Text smearing and morphological oper-
			ators	ators
	Papavassiliou, Stafylakis,	Use of Viterbi algorithm to detect hor-	Use o the negative logarithm of the ob-
	Katsouros, Caryannis 8	izontal separators	jective function of a SVM
	Khandelwal, Choudhury,	Analysis of features of the connected	Difference in intra-word and inter-word
	Sarkar, Basu, Nasipuri,	components in a given neighborhood	distances
	Das 9
	Louloudis,	Gatos,	Hough transform and adapted post pro-	Combination of 2 distance metrics, and
	Pratikakis, Halatsis 2	cessing	threshold obtained thanks to Gaussian
				mixtures

Table 2 .

 2 Detailed results obtained by our method 0.5%). As we have seen in table 2, our results vary depending on the studied database (from 90.4% for words on the training database to 94.20% on test database). Consequently, we can consider that our results are similar to the best methods of ICDAR'2009 contest, and that it is necessary to use a bigger database in order to evaluate more precisely the difference of performance between methods. We can also notice that our method obtains good results for both line and word segmentation, which is only the case for the method of ILSP-LWseg-09.[START_REF] Papavassiliou | Handwritten document image segmentation into text lines and words[END_REF] The interest of our work is that it properly deals with the varied kinds of writings, even with very segmented characters, contrary to Papavassiliou et al.[START_REF] Papavassiliou | Handwritten document image segmentation into text lines and words[END_REF] that meets difficulties with segmented characters.

	Author	Method	FM lines FM words
	Yin et al.	CASIA-MSTSeg 5	95.69%	84.85%
	Hassane et al.	CMM	98.42%	88.91%
	Shi et al.	CUBS 6	99.53%	86.96%
	Rivest-Hénault et al. ETS 7	86.67%	84.93%
	Papavassiliou et al.	ILSP-LWseg-09 8	99.05%	94.74%
	Sarkar et al.	Jadavpur Univ 9	87.34%	82.74%
	Geraud et al.	LRDE 14	92.25%	83.92%
	Lu et al.	PAIS	98.52%	90.54%
		Proposed method 99.25%	94.20%

Table 3 .

 3 Comparison of the performance (FM) with results obtained on the set of ICDAR'2009 contest[START_REF] Gatos | ICDAR 2009 handwriting segmentation contest[END_REF]


Vianney Perchet
email: vian-ney.perchet@normalesup.

Internal Regret with Partial Monitoring Calibration-Based Optimal Algorithms

Keywords: Repeated games, On-line learning, Regret, Partial Monitoring, Calibration, Voronoï and Laguerre Diagrams

We provide consistent random algorithms for sequential decision under partial monitoring, i.e. when the decision maker does not observe the outcomes but receives instead random feedback signals. Those algorithms have no internal regret in the sense that, on the set of stages where the decision maker chose his action according to a given law, the average payoff could not have been improved in average by using any other fixed law.

They are based on a generalization of calibration, no longer defined in terms of a Voronoï diagram but instead of a Laguerre diagram (a more general concept). This allows us to bound, for the first time in this general framework, the expected average internal -as well as the usual external -regret at stage n by O(n -1/3 ), which is known to be optimal.

Hannan [START_REF] Hannan | Approximation to Bayes risk in repeated play[END_REF] introduced the notion of regret in repeated games: a player (that will be referred as a decision maker or also a forecaster) has no external regret if, asymptotically, his average payoff could not have been greater if he had known, before the beginning of the game, the empirical distribution of moves of the other player. Blackwell [START_REF] Blackwell | Controlled random walks[END_REF] showed that the existence of such externally consistent strategies, first proved by [START_REF] Hannan | Approximation to Bayes risk in repeated play[END_REF], is a consequence of his approachability theorem. A generalization of this result and a more precise notion of regret are due to Foster & Vohra [START_REF] Foster | Calibrated learning and correlated equilibrium[END_REF] and Fudenberg & Levine [START_REF] Fudenberg | Conditional universal consistency[END_REF]: there exist internally consistent strategies, i.e. such that for any of his action, the decision maker has no external regret on the set of stages where he actually chose this specific action. Hart & Mas-Colell [START_REF] Hart | A simple adaptive procedure leading to correlated equilibrium[END_REF] also used Blackwell's approachability theorem to construct explicit algorithms that bound the internal (and therefore the external) regret at stage n by O n -1/2 . Some of those results have been extended to the partial monitoring framework, i.e. where the decision maker receives at each stage a random signal, whose law might depend on his unobserved payoff. Rustichini [START_REF] Rustichini | Minimizing regret: the general case[END_REF] defined -and proved the existence of -externally consistent strategies, i.e. such that the average payoff of the decision maker could not have been asymptotically greater if he had known, before the beginning of the game, the empirical distribution of signals. Actually, the relevant information is a vector of probability distributions, one for each action of the decision maker, that is called a flag.

Some algorithms bounding optimally the expected regret by O n -1/3 have been exhibited under some strong assumptions on the signalling structure -see Cesa-Bianchi & Lugosi [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF], Theorem 6.7 for the optimality of this bound. For example, Jaksch, Ortner & Auer [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] considered the Markov decision process framework, Cesa-Bianchi, Lugosi & Stoltz [START_REF] Cesa-Bianchi | Minimizing regret with label efficient prediction[END_REF] assumed that payoffs can be deduced from flags and Lugosi, Mannor & Stoltz [START_REF] Lugosi | Strategies for prediction under imperfect monitoring[END_REF] that feedbacks are deterministic (along with the fact that the worst compatible payoff is linear with respect to the flag). When no such assumption is made, Lugosi, Mannor & Stoltz [START_REF] Lugosi | Strategies for prediction under imperfect monitoring[END_REF] provided an algorithm (based on the exponential weight algorithm) that bounds regret by O n -1/5 . In this framework, internal regret was defined by Lehrer & Solan [START_REF] Lehrer | Learning to play partially-specified equilibrium[END_REF]; stages are no longer distinguished as a function of the action chosen by the decision maker (as in the full monitoring case) but as a function of its law. Indeed, the evaluation of the payoff (usually called worst case) is not linear with respect to the flag. So a best response -in a sense to be defined -to a given flag might consist only in a mixed action (i.e. a probability distribution over the set of actions). Lehrer & Solan [START_REF] Lehrer | Learning to play partially-specified equilibrium[END_REF] also proved the existence and constructed internally consistent strategies, using the characterization of approachable convex sets due to Blackwell [START_REF] Blackwell | An analog of the minimax theorem for vector payoffs[END_REF]. Perchet [START_REF] Perchet | Calibration and internal no-regret with random signals[END_REF] provided an alternative algorithm, recalled in section 2.2; this latter is based on calibration, a notion introduced by Dawid [START_REF] Dawid | The well-calibrated Bayesian[END_REF]. Roughly speaking, these algorithms ε-discretize arbitrarily the space of flags and each point of the discretization is called a possible prediction. Then, stage after stage, they predict what will be the next flag and output a best response to it. If the sequence of predictions is calibrated then the average flag, on the set of stages where a specific prediction is made, will be close to this prediction.

Thanks to the continuity of payoff and signaling functions, both algorithms bound the internal regret by ε + O n -1/2 . However the first drawback lies in their computational complexities: at each stage, the algorithm of Perchet [START_REF] Perchet | Calibration and internal no-regret with random signals[END_REF] solves a system of linear equations while the one Lehrer & Solan [START_REF] Lehrer | Learning to play partially-specified equilibrium[END_REF], after a projection on a convex set, solves a linear program. In both case, the size of the linear system or program considered is polynomial in ε and exponential in the numbers of actions and signals. The second drawback is that the constants in the rate of convergence depend drastically on ε.

As a consequence, a classic doubling trick argument will generate an algorithm with a strongly sub-optimal rate of convergence -that might even depend on the size of the actions sets -and a complexity that increases with time.

Our main result is Theorem 2.10, stated in section 2.3: it provides the first algorithm that bounds optimally both internal and external regret by O n -1/3 in the general case. It is a modification of the algorithm of Perchet [START_REF] Perchet | Calibration and internal no-regret with random signals[END_REF] that does not use an arbitrary discretization but constructs carefully a specific one and then computes, stage by stage, the solution of a system of linear equations of constant size. In section 3.1, an other algorithmbased on Blackwell's approachability as the one of Lehrer & Solan [START_REF] Lehrer | Learning to play partially-specified equilibrium[END_REF] with optimal rate and smaller constants is exhibited; it requires however to solve, at each stage, a linear program of constant size.

Section 1 is devoted to the simpler framework of full monitoring. We recall definitions of calibration and regret and we provide a naïve algorithm to construct strategies with internal regret asymptotically smaller than ε. We show how to modify this algorithm -however in a not efficient wayin order to bound optimally the regret by O n -1/2 . This has to be seen only as a tool that can be easily adapted with partial monitoring in order to reach the optimal bound of O n -1/3 ; this is done in section 2. Some extensions (the second algorithm, the so-called compact case and variants to strengthen the constants) are presented in section 3. Some technical proofs can be found in Appendix.

1 Full monitoring

Model and definitions

Consider a two-person game Γ repeated in discrete time, where at stage n ∈ N, a decision maker, or forecaster, (resp. the environment or Nature) chooses an action i n ∈ I (resp. j n ∈ J ). This generates a payoff ρ n = ρ(i n , j n ), where ρ is a mapping from I × J to R, and a regret r n ∈ R I defined by:

r n = ρ(i, j n ) -ρ(i n , j n ) i∈I ∈ R I ,
where I is the finite cardinality of I (and J the one of J ). This vector represents the differences between what the decision maker could have got and what he actually got. The choices of i n and j n depend on the past observations (also called finite history) h n-1 = (i 1 , j 1 , . . . , i n-1 , j n-1 ) and may be random. Explicitly, the set of finite histories is denoted by H = n∈N (I × J ) n , with (I × J ) 0 = ∅ and a strategy σ of the decision maker is a mapping from H to ∆(I), the set of probability distributions over I. Given the history

h n ∈ (I × J ) n , σ(h n ) ∈ ∆(I) is the law of i n+1 .
A strategy τ of Nature is defined similarly as a function from H to ∆(J ). A pair of strategies (σ, τ ) generates a probability, denoted by P σ,τ , over (H, A) where H = (I × J ) N is the set of infinite histories embedded with the cylinder σ-field.

We extend the payoff mapping ρ to ∆(I)×∆(J ) by ρ(x, y) = E x,y [ρ(i, j)] and for any sequence a = (a m ) m∈N and any n ∈ N * , we denote by ān = 1 n n m=1 a m the average of a up to stage n. Definition 1.1 (Hannan [17]) A strategy σ of the forecaster is externally consistent if for every strategy τ of Nature:

lim sup n→∞ ri n ≤ 0, ∀i ∈ I, P σ,τ -as.
In words, a strategy σ is externally consistent if the forecaster could not have had a greater payoff if he had known, before the beginning of the game, the empirical distribution of actions of Nature. Indeed, the external consistency of σ is equivalent to the fact that :

lim sup n→∞ max x∈∆(I) ρ(x, n ) -ρn ≤ 0, P σ,τ -as. (1)
Foster & Vohra [START_REF] Foster | Calibrated learning and correlated equilibrium[END_REF] (see also Fudenberg & Levine [START_REF] Fudenberg | Conditional universal consistency[END_REF]) defined a more precise notion of regret. The internal regret of the stage n, denoted by R n ∈ R I×I , is also generated by the choices of i n and j n and its (i, k)-th coordinate is defined by:

R ik n = ρ(k, j n ) -ρ(i, j n ) if i = i n 0 otherwise.
Stated differently, every row of the matrix R n is null except the i n -th which is r n .

Definition 1.2 (Foster & Vohra [START_REF] Foster | Calibrated learning and correlated equilibrium[END_REF]) A strategy σ of the forecaster is internally consistent if for every strategy τ of Nature:

lim sup n→∞ Rik n ≤ 0 ∀i, k ∈ I, P σ,τ -as.
We introduce the following notations to define ε-internally consistency. Denote by N n (i) the set of stages before the n-th where the forecaster chose action i and n (i) ∈ ∆(J ) the empirical distribution of Nature's actions on this set. Formally,

N n (i) = {m ∈ {1, . . . , n}; i m = i} and n (i) = m∈Nn(i) j m |N n (i)| ∈ ∆(J ). (2) A strategy is ε-internally consistent if for every i, k ∈ I lim sup n→∞ |N n (i)| n ρ k, n (i) -ρ i, n (i) -ε ≤ 0, P σ,τ -as.
If we define, for every ε ≥ 0, the ε-best response correspondence by :

BR ε (y) = x ∈ ∆(I); ρ(x, y) ≥ max z∈∆(I) ρ(z, y) -ε ,
then a strategy of the decision maker is ε-internally consistent if any action i is either an ε-best response to the empirical distribution of Nature's actions on N n (i) or the frequency of i is very small. We will simply denote BR 0 by BR and call it the best response correspondence.

From now on, given two sequences l m ∈ L, a m ∈ R d ; m ∈ N where L is a finite set, we will define the subset of integers N n (l) and the average ān (l) as in equation ( 2). Proposition 1.3 (Foster & Vohra [13]) For every ε ≥ 0, there exist εinternally consistent strategies.

Although the notion of internal regret is a refinement of the notion of external regret (in the sense that any internally consistent strategy is also externally consistent), Blum & Mansour [START_REF] Blum | From external to internal regret[END_REF] proved that any externally consistent algorithm can be efficiently transformed into an internally consistent one (actually they obtained an even stronger property called swap consistency).

Foster & Vohra [START_REF] Foster | Calibrated learning and correlated equilibrium[END_REF] and Hart & Mas-Colell [START_REF] Hart | A simple adaptive procedure leading to correlated equilibrium[END_REF] proved directly the existence of 0-internally consistent strategies using different algorithms (with optimal rates and based respectively on the Expected Brier Score and Blackwell's approachability theorem). In some sense, we merge these two last proofs in order to provide a new one -given in the following sectionthat can be extended quite easily to the partial monitoring framework.

A naïve algorithm, based on calibration

The algorithm (a similar idea was used by Foster & Vohra [START_REF] Foster | Calibrated learning and correlated equilibrium[END_REF]) that constructs an ε-internally consistent strategy is based on this simple fact: if the forecaster can, stage by stage, foresee the law of Nature's next action, say y ∈ ∆(J ), then he just has to choose any best response to y at the following stage. The continuity of ρ implies that the forecasts need not be extremely precise but only up to some δ > 0.

Let {y(l); l ∈ L} be a δ-grid of ∆(J ) (i.e. a finite set such that for every y ∈ ∆(J ) there exists l ∈ L such that yy(l) ≤ δ) and i(l) be a best response to y(l), for every l ∈ L. Then if δ is small enough:

y -y(l) ≤ 2δ ⇒ i(l) ∈ BR 2ε (y)
It is possible to construct a good sequence of forecasts by computing a calibrated strategy (introduced by Dawid [START_REF] Dawid | The well-calibrated Bayesian[END_REF] and recalled in the following subsection 1.2.1).

Calibration

Consider a two-person repeated game Γ c where, at stage n, Nature chooses the state of the world j n in a finite set J and a decision maker (that will be referred in this setting as a predictor) predicts it by choosing y(l n ) in Y = {y(l); l ∈ L}, a finite δ-grid of ∆(J ) -its cardinality is denoted by L. As usual, a behavioral strategy σ of the predictor (resp. τ of Nature) is a mapping from the set of finite histories H = n∈N (L × J ) n to ∆(L) (resp. ∆(J )). We also denote by P σ,τ the probability generated by the pair (σ, τ ) over (H, A) the set of infinite histories embedded with the cylinder topology. Definition 1.4 (Dawid [START_REF] Dawid | The well-calibrated Bayesian[END_REF]) A strategy σ of the predictor is calibrated (with respect to Y = {y(l); l ∈ L}) if for every strategy τ of Nature, P σ,τ -as:

lim sup n→∞ |N n (l)| n n (l) -y(l) 2 -n (l) -y(k) 2 ≤ 0, ∀k, l ∈ L,
where • is the Euclidian norm of R J .

In words, a strategy is calibrated if for every l ∈ L, the empirical distribution of states, on the set of stages where y(l) was predicted, is closer to y(l) than to any other y(k) ( or the frequency of l, |N n (l)|/n, is small). Given a finite grid of ∆(J ), the existence of calibrated strategies has been proved by Foster & Vohra [START_REF] Foster | Asymptotic calibration[END_REF] using either the Expected Brier Score or a minmax theorem (actually this second argument is acknowledged to Hart). We give here a construction, related but simpler than the one of Foster and Vohra, due to Sorin [START_REF] Sorin | Lectures on Dynamics in Games[END_REF].

Proposition 1.5 (Foster & Vohra [14]) For any finite grid Y of ∆(J ), there exist calibrated strategies with respect to Y such that for every strategy τ of Nature:

E σ,τ max l,k∈L |N n (l)| n n (l) -y(l) 2 -n (l) -y(k) 2 ≤ O 1 √ n .
Proof. Consider the auxiliary game where, at stage n ∈ N, the predictor (resp. Nature) chooses l n ∈ L (resp. j n ∈ J ) and the vector payoff is the matrix U n ∈ R L×L where

U lk n = j n -y(l) 2 -j n -y(k) 2 if l = l n 0 otherwise.
A strategy σ is calibrated with respect to L if Ūn converges to the negative orthant. Indeed for every l, k ∈ L, the (l, k)-th coordinate of Ūn is

Ū lk n = |N n (l)| n m∈Nn(l) j m -y(l) 2 -j m -y(k) 2 |N n (l)| = |N n (l)| n n (l) -y(l) 2 -n (l) -y(k) 2 .
Denote by Ū + n := max 0, Ū lk n l,k∈L =: Ūn -Ūn the positive part of Ūn and by λ n ∈ ∆(L) any invariant measure of Ū + n . We recall that λ is an invariant measure of a nonnegative matrix U if, for every l ∈ L,

k∈L λ(k)U kl = λ(l) k∈L U lk .
Its existence is a consequence of Perron-Frobenius Theorem, see e.g. Seneta [START_REF] Seneta | Nonnegative Matrices and Markov Chains[END_REF].

Define the strategy σ of the predictor inductively as follows. Choose arbitrarily σ(∅), the law of the first action and at stage n + 1, play accordingly to any invariant measure of Ū + n . We claim that this strategy is an approachability strategy of the negative orthant of R L×L because it satisfies Blackwell [START_REF] Blackwell | An analog of the minimax theorem for vector payoffs[END_REF]'s sufficient condition:

∀n ∈ N, Ūn -Ū - n , E λn [U n+1 |j n+1 ] -Ū - n ≤ 0.
Indeed, for every possible j n+1 ∈ J :

Ū + n , E λn [U n+1 |j n+1 ] = 0 = Ū + n , Ū - n , (3)
where the second equality follows from the definition of positive and negative parts.

Consider the first equality. The (l, k)-th coordinate of

E λn [U n+1 |j n+1 ] is λ n (l) j n+1 -y(l) 2 -j n+1 -y(k) 2 , therefore the coefficient of j n+1 - y(l) 2 in the first term is λ n (l) k∈L Ū + n lk -k∈L λ n (k) Ū + n kl
. This equals 0 since λ n is an invariant measure of Ū + n .

Blackwell [START_REF] Blackwell | An analog of the minimax theorem for vector payoffs[END_REF]'s result also implies that E σ,τ Ū + n ≤ 2M n n -1/2 for any strategy τ of Nature where

M 2 n = sup m≤n E σ,τ U m 2 = 4L.
Interestingly, the strategy σ we constructed in this proof is actually internally consistent in the game with action spaces L and J and payoffs defined by ρ(l, j) =jy(l) 2 . Corollary 1.6 For any finite grid Y of ∆(J ), there exists σ, a calibrated strategy with respect to Y, such that for every strategy τ of Nature, with P σ,τ probability at least 1δ:

max l,k∈L |N n (l)| n n (l) -y(l) 2 -n (l) -y(k) 2 ≤ 2M n √ n + Θ n ,
where Θ n = min

v n √ n 2 ln L 2 δ + 2 3 K n n ln L 2 δ , K n √ n 2 ln L 2 δ ; M n = sup m≤n E σ,τ U m 2 ≤ 3 √ L; v 2 n = sup m≤n sup l,k∈L E σ,τ U lk n -E σ,τ U lk n 2 ≤ 3; K n = sup m≤n sup l,k∈L U lk n -E σ,τ U lk n ≤ 3.
Proof. Proposition 1.5 implies that E σ,τ Ūn ≤ 2M n n -1/2 . Hoeffding-Azuma's inequality (see Lemma 3.4 below in section 3.3.1) implies that with probability at least 1δ :

Ū lk n -E σ,τ Ū lk n ≤ K n √ n 2 ln 1 δ .
Freedman's inequality (an analogue of Bernstein's inequality for martingale see Freedman [START_REF] Freedman | On tail probabilities for martingales[END_REF], Proposition 2.1 or Cesa-Bianchi & Lugosi [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF], Lemma A.8) implies that with probability at least 1δ :

Ū lk n -E σ,τ Ū lk n ≤ v n √ n 2 ln 1 δ + 2 3
K n n ln 1 δ .
The result is a consequence of these two inequalities and of Proposition 1.5.

The definition of Θ n as a minimum (and the use of Freedman's inequality) will be useful when we will refer to this corollary in the subsequent sections. Obviously, in the current framework,

Θ n ≤ 3 √ n 2 ln L 2 δ .

Back to the Naïve Algorithm

Let us now go back to the construction of ε-consistent strategies in Γ. Compute σ, a calibrated strategy with respect to a δ-grid Y = {y(l); l ∈ L} of ∆(J ) in an abstract calibration game Γ c . Whenever the decision maker (seen as a predictor) should choose the action l in Γ c , then he (seen as a forecaster) chooses i(l) ∈ BR(y(l)) in the original game Γ. We claim that this defines a strategy σ ε which is 2ε-internally consistent.

Proposition 1.7 (Foster & Vohra [START_REF] Foster | Calibrated learning and correlated equilibrium[END_REF]) For every ε > 0, the strategy σ ε described above is 2ε-internally consistent.

Proof. By definition of a calibrated strategy, for every η > 0, there exists with probability 1, an integer N ∈ N such that for every l, k ∈ L and for every n ≥ N :

|N n (l)| n n (l) -y(l) 2 -n (l) -y(k) 2 ≤ η.
Since {y(k); k ∈ L} is a δ-grid of ∆(J ), for every l ∈ L and every n ∈ N,

there exists k ∈ L such that n (l) -y(k) 2 ≤ δ 2 , hence n (l) -y(l) 2 ≤ δ 2 + η n |Nn(l)| . Therefore, since i(l) ∈ BR(y(l)): |N n (l)| n ≥ η δ 2 ⇒ n (l) -y(l) 2 ≤ 2δ 2 ⇒ ρ(k, n (l)) -ρ(i(l), n (l)) ≤ 2ε,
for every k ∈ I, l ∈ L and n ≥ N . The (i, k)-th coordinate of Rn satisfies:

|N n (i)| n Rik n -2ε ≤ 1 n m∈Nn(i) ρ(k, j m ) -ρ(i, j m ) -2ε = 1 n l:i(l)=i m∈Nn(l) ρ(k, j m ) -ρ(i, j m ) -2ε = l:i(l)=i |N n (l)| n ρ(k, n (l)) -ρ(i(l), n (l)) -2ε . Recall that either |Nn(l)| n ≥ η δ 2 and ρ(k, n (i)) -ρ(i(l), n (l)) -2ε ≤ 0, or |Nn(l)| n < η δ 2 . Since ρ is bounded (by M ρ > 0), then : |N n (i)| n Rik n -2ε ≤ η 2M ρ L δ 2 , ∀i ∈ I, ∀k ∈ I, ∀n ≥ N,
which implies that σ is 2ε-internally consistent.

Remark 1.8 This naïve algorithm only achieves ε-consistency and Proposition 1.5 implies that

E σ,τ max i,k∈I Rik n -ε ≤ O 1 √ n .
The constants depend drastically on L, which is in the current framework in the order of ε J , therefore it is not possible to obtain 0-internally consistency at the same rate with a classic doubling trick argument (i.e. use a 2 -k -internally consistent strategy on N k stages, then switch to a 2 -(k+1)internally consistent strategy, and so on, see e.g. Sorin [START_REF] Sorin | Supergames. In Game theory and applications[END_REF], Proposition 3.2 page 56). Moreover, since this algorithm is based on calibration, it computes at each stage an invariant measure of a non-negative matrix; this can be done, using Gaussian elimination, with O L 3 operations, thus this algorithm is far from being efficient (since its computational complexity is polynomial in ε and exponential in J). There exist 0-internally consistent algorithms, see e.g. the reduction of Blum & Mansour [START_REF] Blum | From external to internal regret[END_REF], that do not have this exponential dependency in the complexity or in the constants.

On the bright side, this algorithm can be modified to obtain 0-consistency at optimal rate; obviously, it will still not be efficient with full monitoring (see section 1.4). However, it has to be understood as a tool that can be easily adapted in order to exhibit, in the partial monitoring case, an optimal internal consistent algorithm (see section 2.3). And in that last framework, it is not clear that we can remove the dependency on L (especially for the internal regret).

Calibration and Laguerre diagram

Given a finite subset of Voronoï sites {z(l) ∈ R d ; l ∈ L}, the l-th Voronoï cell V (l), or the cell associated to z(l), is the set of points closer to z(l) than to any other z(k):

V (l) = Z ∈ R d ; Z -z(l) 2 ≤ Z -z(k) 2 , ∀k ∈ L ,
where • is the Euclidian norm of R d . Each V (l) is a polyhedron (as the intersection of a finite number of half-spaces) and {V (l); l ∈ L} is a covering of R d . A calibrated strategy with respect to {z(l); l ∈ L} has the property that for every l ∈ L, the frequency of l goes to zero, or the empirical distribution of states on N n (l), converges to V (l).

The naïve algorithm uses the Voronoï diagram associated to an arbitrary grid of ∆(J ) and assigns to every small cell an ε-best reply to every point of it; this is possible by continuity of ρ. A calibrated strategy ensures that n (l) converges to V (l) (or the frequency of l is small), thus choosing i(l) on N n (l) was indeed a ε-best response to n (l). With this approach, we cannot construct immediately 0-internally consistent strategy. Indeed, this would require that for every l ∈ L there exists a 0-best response i(l) to every element y in V (l). However, there is no reason for them to share a common best response because {z(l); l ∈ L} is chosen arbitrarily.

On the other hand, consider the simple game called Matching Penny. Both players have two action Heads and T ails, so ∆(J ) = ∆(I) = [0, 1], seen as the probability of choosing T . The payoff is 1 if both players choose the same action and -1 otherwise. Action H (resp. T ) is a best response for Player 1 to any y in [0, 1/2] (resp. in [1/2, 1]). These two segments are exactly the cells of the Voronoï diagram associated to {y(1) = 1/4, y(2) = 3/4}, therefore, performing a calibrated strategy with respect to {y(1), y(2)} and playing H (resp. T ) on the stages of type 1 (resp. 2) induces a 0-internally consistent strategy of Player 1.

This idea can be generalized to any game. Indeed, by Lemma 1.10 stated below, ∆(J ) can be decomposed into polytopial best-response areas (a polytope is the convex hull of a finite number of points, its vertices). Given such a polytopial decomposition, one can find a finer Voronoï diagram (i.e. any best-response area is an union of Voronoï cells) and finally use a calibrated strategy to ensure convergence with respect to this diagram.

Although the construction of such a diagram is quite simple in R, difficulties arise in higher dimension -even in R 2 . More importantly, the number of Voronoï sites can depend not only on the number of defining hyperplanes but also on the angles between them (thus being arbitrarily large even with a few hyperplanes). On the other hand, the description of a Laguerre diagram -this concept generalizes Voronoï diagrams -that refines a polytopial decomposition is quite simple and is described in Proposition 1.11 below. For this reason, we will consider from now on this kind of diagram (sometimes also called Power diagram) .

Given a subset of Laguerre sites {z(l) ∈ R d ; l ∈ L} and weights {ω(l) ∈ R; l ∈ L}, the l-th Laguerre cell P (l) is defined by:

P (l) = Z ∈ R d ; Z -z(l) 2 -ω(l) ≤ Z -z(k) 2 -ω(k), ∀k ∈ L ,
where • is the Euclidian norm of R d . Each P (l) is a polyhedron and P = {P (l); l ∈ L} is a covering of R d . Definition 1.9 A covering K = {K i ; i ∈ I} of a polytope K with nonempty interior is a polytopial complex of K if for every i, j in the finite set I, K i is a polytope with non-empty interior and the polytope K i ∩ K j has empty interior. This definition extends naturally to a polytope K with empty interior, if we consider the affine subspace generated by K.

Lemma 1.10 There exists a subset I ′ ⊂ I such that {B i ; i ∈ I ′ } is a polytopial complex of ∆(J ), where B i is the i-th best response area defined by

B i = {y ∈ ∆(J ); i ∈ BR(y)} = BR -1 (i).
Proof. For any y ∈ ∆(J ), ρ(•, y) is linear on ∆(I) thus it attains its maximum on I and i∈I B i = ∆(J ). Without loss of generality, we can assume that each B i is non-empty, otherwise we drop the index i.

For every i, k ∈ I, ρ(i, •) -ρ(k, •) is linear on ∆(J ) therefore B i is a polytope; it is indeed defined by B i = {y ∈ ∆(J ); ρ(i, y) ≥ ρ(k, y), ∀k ∈ I} = k∈I {y ∈ R J ; ρ(i, y) -ρ(k, y) ≥ 0} ∩ ∆(J ),
so it is the intersection of a finite number of half-spaces and the polytope ∆(J ). Moreover if B ik 0 , the interior of B i ∩ B k , is non-empty then ρ(i, •) equals ρ(k, •) on the subspace generated by B ik 0 and therefore on ∆(J ); consequently B i = B k . Denote by I ′ any subset of I such that for every i ∈ I, there exists exactly one i ′ ∈ I ′ such that

B i = B i ′ = ∅, then {B i ; i ∈ I ′ } is a polytopial complex of ∆(J ).
Proposition 1.11 Let K = {K i ; i ∈ I} be a polytopial complex of a polytope K ⊂ R d . Then there exists {z(l) ∈ R d , ω(l) ∈ R; l ∈ L}, a finite set of Laguerre sites and weights, such that the Laguerre diagram P = {P (l); l ∈ L} refines K, i.e. every K i is a finite union of cells.

Proof. Let K = {K i ; i ∈ I} be a polytopial complex of K ⊂ R d . Each K i is a polytope, thus defined by a finite number of hyperplanes. Denote by H = {H t ; t ∈ T } the set of all defining hyperplanes (the finite cardinality of T is denoted by T ) and K = { K l ; l ∈ L} the finest decomposition of R d induced by H -usually called arrangement of hyperplanes -which by definition refines K. Theorem 3 and Corollary 1 of Aurenhammer [START_REF] Aurenhammer | A criterion for the affine equivalence of cell complexes in R d and convex polyhedra in R d+1[END_REF] imply that K is the Laguerre diagram associated to some {z(l), ω(l); l ∈ L} whose exact computation requires the following notation: i) for every t ∈ T , let c t ∈ R d and b t ∈ R (which can, without loss of generality, be assumed to be non zero) such that

H t = X ∈ R d ; X, c t = b t .
ii) For every l ∈ L and t ∈ T , σ t (l) = 1 if the origin of R d and K l are in the same halfspace defined by H t and σ t (l) = -1 otherwise.

iii) For every l ∈ L, we define :

z(l) = t∈T σ t (l)c t T and ω(l) = z(l) 2 + 2 t∈T σ t (l)b t T . (4)
Note that one can add the same constant to every weight ω(l).

Buck [START_REF] Buck | Partition of space[END_REF] proved that the number of cells defined by T hyperplanes in R d is bounded by d k=0 T k =: φ(T, d), where T k is the binomial coefficient, T choose k. Moreover, T is smaller than I(I -1)/2 (in the case where each K i has a non-empty intersection with every other polytope), so

L ≤ φ I 2 2 , d . If d ≥ n, then φ(n, d) = 2 n .
Pascal's rule and a simple induction imply that, for every n, d ∈ N, φ(n, d) ≤ (n + 1) d . Finally, for any n ≥ 2d, by noticing that

n d + n d-1 + . . . + n 0 n d ≤ d m=0 d n -d + 1 m ≤ ∞ m=0 d n -d + 1 m which equals n-d+1 n-2d+1 ≤ 1+d, we deduce that φ(n, d) ≤ (1+d) n d ≤ (1+d) n d d! .
Lemma 1.12 Let P = {P (l); l ∈ L} be a Laguerre diagram associated to the set of sites and weights {z(l) ∈ R d , ω(l) ∈ R; l ∈ L}. Then, there exists a positive constant M P > 0 such that for every

Z ∈ R d if Z -z(l) 2 -ω(l) ≤ Z -z(k) 2 -ω(k) + ε, ∀l, k ∈ L (5) then d (Z, P (l)) is smaller than M P ε.
The proof can be found in Appendix A.1; the constant M P depends on the Laguerre diagram, and more precisely on the inner products c t , c t ′ , for every t, t ′ ∈ T .

Optimal algorithm with full monitoring

We reformulate Proposition 1.5 and Corollary 1.6 in terms of Laguerre diagram.

Theorem 1.13 For any set of sites and weights {y(l) ∈ R J , ω(l) ∈ R; l ∈ L} there exists a strategy σ of the predictor such that for every strategy τ of Nature:

E σ,τ Ūω,n + ≤ O 1 √ n
where U ω,n is defined by :

U lk ω,n = j n -y(l) 2 -ω(l) -j n -y(k) 2 -ω(k) if l = l n 0 otherwise
Corollary 1.14 For any set of sites and weights {y(l) ∈ R J , ω(l) ∈ R; l ∈ L}, there exists a strategy σ of the predictor such that, for every strategy τ of Nature, with P σ,τ probability at least 1δ, and l, l ∈ L:

|N n (l)| n n (l) -y(l) 2 -ω(l) -n (l) -y(k) 2 -ω(k) ≤ 2M n √ n + Θ n where M n = sup m≤n E σ,τ U ω,m 2 ≤ 4 √ L (b, c) ∞ ; Θ n = min v n √ n 2 ln L 2 δ + 2 3 K n n ln L 2 δ , K n √ n 2 ln L 2 δ ; v 2 n = sup m≤n sup l,k∈L E σ,τ U lk ω,m -E σ,τ U lk ω,m 2 ≤ 4 (b, c) 2 ∞ ; K n = sup m≤n sup l,k∈L U lk ω,m -E σ,τ U lk ω,m ≤ 4 (b, c) ∞ , (b, c) ∞ = sup t∈T c t + sup t∈T |b t |.
Such a strategy is said to be calibrated with respect to {y(l), ω(l); l ∈ L}.

The proof are identical to the one of Proposition 1.5 and Corollary 1.6. We have now the material to construct our new tool algorithm:

Theorem 1.15 There exists an internally consistent strategy σ of the forecaster such that for every strategy τ of Nature and every n ∈ N, with P σ,τ probability greater than 1δ:

max i,k∈I Rik n ≤ O   ln 1 δ n   . (6)
Proof. The existence of a Laguerre Diagram {Y (l); l ∈ L} associated to a finite set {y(l) ∈ R J , ω(l) ∈ R; l ∈ L} that refines {B i ; i ∈ I} is implied by Lemma 1.10 and Proposition 1.11. So, for every l ∈ L, there exists i(l) such that Y (l) ⊂ B i(l) . As in the naïve algorithm, the strategy σ of the decision maker is constructed through a strategy σ calibrated with respect to {y(l), ω(l); l ∈ L}. Whenever, accordingly to σ, the decision maker (seen as a predictor) should play l in Γ c , then he (seen as a forecaster) plays i(l) in Γ.

If we denote by  n (l) the projection of n (l) onto Y (l) then:

Rik n = l:i(l)=i |N n (l)| n ρ k, n (l) -ρ i(l), n (l) ≤ l:i(l)=i |N n (l)| n ρ k, n (l) -ρ k,  n (l) + ρ i(l),  n (l) -ρ i(l), n (l) ≤ l:i(l)=i |N n (l)| n 2M ρ  n (l) -n (l) ≤ (2M ρ M P L) max l,k∈L |N n (l)| n n (l) -y(l) 2 -ω(l) -n (l) -y(k) 2 -ω(k)
where the second inequality is due to the fact that i(l) ∈ BR(  n (l)) and the third to the fact that ρ is M ρ -Lipschitz. The fourth inequality is a consequence of Lemma 1.12. Corollary 1.14 yields that for every strategy τ of Nature, with P σ,τ probability at least 1δ:

max l,k N n (l) n n (l) -y(l) 2 -ω(l) -n (l) -y(k) 2 -ω(k) ≤ 8 √ L (b, c) ∞ √ n + 4 (b, c) ∞ √ n 2 ln L 2 δ , therefore with Ω 0 = 16M ρ M P L 3/2 (b, c) ∞ and Ω 1 = 8M ρ M P L 1/2 (b, c) ∞
one has that for every strategy of Nature and with probability at least 1δ:

max i,k∈I Rik n = max i,k∈I |N n (i)| n ρ k, n (i) -ρ i, n (i) ≤ Ω 0 √ n + Ω 1 √ n 2 ln L 2 δ .
Remark 1.16 Theorem 1.15 is already well-known. The construction of this internally consistent strategy relies on Theorem 1.13, which is implied by the existence of internally consistent strategies... Moreover, as mentioned before, it is far from being efficient since L -that enters both in the computational complexity and in the constant -is polynomial in I J . There exist efficient algorithms, see e.g. Foster & Vohra [START_REF] Foster | Calibrated learning and correlated equilibrium[END_REF] or Blum & Mansour [START_REF] Blum | From external to internal regret[END_REF]. However, the calibration is defined in the space of Nature's action, where real payoffs are irrelevant; they are only used to decide which action is associated to each prediction. Therefore the algorithm does not require that the forecaster observes his real payoffs, as long as he knows what is the best response to his information (Nature's action in this case). This is precisely why our algorithm can be generalized to the partial monitoring framework.

The polytopial decomposition of ∆(J ) induced by {b t , c t ; t ∈ T } is exactly the same as the one induced by {γb(t), γc(t); t ∈ T } for any γ > 0. Thus, by choosing γ small enough, (b, c) ∞ -and therefore the constants in Corollary 1.14 -can be arbitrarily small (i.e. multiplied by any γ > 0).

However, these two Laguerre diagrams are associated to the sets of sites and weights L(1) and L(γ), where 1), then the constant M P defined in Lemma 1.12 should be divided by γ. So, as expected, the constants in the proof of Theorem 1.15 do not depend on γ. From now on, we will assume that (b, c) ∞ is smaller than 1.

L(γ) = {γz(l), γω(l) + γ 2 z(l) 2 - γ z(l) ; l ∈ L}. If L(γ) is used instead of L(

Partial monitoring 2.1 Definitions

In the partial monitoring framework, the decision maker does not observe Nature's actions. There is a finite set of signals S (of cardinality S) such that, at stage n the forecaster receives only a random signal s n ∈ S. Its law is s(i n , j n ) where s is a mapping from I × J to ∆(S), known by the decision maker.

We define s from ∆(J ) to ∆(S) I by s(y

) = E y [s(i, j)] i∈I ∈ ∆(S) I .
Any element of ∆(S) I is called a flag (it is a vector of probability distributions over S) and we will denote by F the range of s. Given a flag f in F, the decision maker cannot distinguish between any different mixed actions y and y ′ in ∆(J ) that generate f , i.e. such that s(y) = s(y ′ ) = f . Thus s is the maximal informative mapping about Nature's action. We denote by f n = s(j n ) the (unobserved) flag of stage n ∈ N.

c). In order to distinguish between those two actions, the forecaster needs to know s(o, y) although action o is never a best response (but is purely informative).

The worst payoff compatible with x and f ∈ F is defined by:

W (x, f ) = inf y∈s -1 (f ) ρ(x, y), (7)
and W is extended to ∆(S) I by W (x, f ) = W (x, Π F (f )).

As in the full monitoring case, we define, for every ε ≥ 0, the ε-best response multivalued mapping BR ε : ∆(S) I ⇉ ∆(I) by :

BR ε (f ) = x ∈ ∆(I); W (x, f ) ≥ sup z∈∆(I) W (z, f ) -ε .
Given a flag f ∈ ∆(S) I , the function W (•, f ) may not be linear so the best response of the forecaster might not contain any element of I.

Example 2.2 Matching Penny in the dark:

Consider the Matching Penny game where the forecaster does not observe the coin but always receives the same signal c: every choice of Nature generates the same flag (c, c). For every x ∈ [0, 1] = ∆({H, T }) -the probability of playing T -, the worst compatible payoff W (x, (c, c)) = min y∈∆(J) ρ(x, y) is equal to -|1 -2x| thus is non-negative only for x = 1/2. Therefore the only best response of the forecaster is to play 1 2 H + 1 2 T , while actions H and T give the worst payoff of -1.

The definition of external consistency and especially equation ( 1) extend naturally to this framework: a strategy of the decision maker is externally consistent if he could not have improved his payoff by knowing, before the beginning of the game, the average flag: Definition 2.3 (Rustichini [START_REF] Rustichini | Minimizing regret: the general case[END_REF]) A strategy σ of the forecaster is externally consistent if for every strategy τ of Nature:

lim sup n→+∞ max z∈∆(I)
W (z, fn )ρn ≤ 0, P σ,τ -as.

The main issue is the definition of internally consistency. In the full monitoring case, the forecaster has no internal regret if, for every i ∈ I, the action i is a best-response to the empirical distribution of Nature's actions, on the set of stages where i was actually chosen. In the partial monitoring framework, the decision maker's action should be a best response to the average flag. Since it might not belong to I but rather to ∆(I), we will (following Lehrer & Solan [START_REF] Lehrer | Learning to play partially-specified equilibrium[END_REF]) distinguish the stages not as a function of the action actually chosen, but as a function of its law.

We make an extra assumption on the characterization of the forecaster's strategy: it can be generated by a finite family of mixed actions {x(l) ∈ ∆(I); l ∈ L} such that, at stage n ∈ N, the forecaster chooses a type l n and, given that type, the law of his action i n is x(l n ) ∈ ∆(I).

Denote by N n (l) = {m ∈ {1, . . . , n}; l m = l} the set of stages before the n-th whose type is l. Roughly speaking, a strategy will be ε-internally consistent (with respect to the set L) if, for every l ∈ L, x(l) is an ε-best response to fn (l), the average flag on N n (l) (or the frequency of the type l, |N n (l)|/n, converges to zero).

The finiteness of L is required to get rid of strategies that trivially insure that every frequency converges to zero (for instance by choosing only once every mixed action). The choice of {x(l); l ∈ L} and the description of the strategies are justified more precisely below by Remark 2.7 in section 2.3. [START_REF] Lehrer | Learning to play partially-specified equilibrium[END_REF]) For every n ∈ N and every l ∈ L, the average internal regret of type l at stage n is

Definition 2.4 ( Lehrer & Solan

R n (l) = sup x∈∆(I) W (x, fn (l)) -ρn (l) .
A strategy σ of the forecaster is (L, ε)-internally consistent if for every strategy τ of Nature:

lim sup n→+∞ |N n (l)| n R n (l) -ε ≤ 0, ∀l ∈ L, P σ,τ -as.
In words, a strategy is (L, ε)-internally consistent if, for every l ∈ L, the forecaster could not have had, for sure, a better payoff (of at least ε) if he had known, before the beginning of the game, the average flag on N n (l) (or the frequency of l is small).

A naïve algorithm

Theorem 2.5 ( Lehrer & Solan [START_REF] Lehrer | Learning to play partially-specified equilibrium[END_REF]) For every ε > 0, there exist (L, ε)internally consistent strategies.

Lehrer & Solan [START_REF] Lehrer | Learning to play partially-specified equilibrium[END_REF] proved the existence and constructed such strategies and an alternative, yet close, algorithm has been provided by Perchet [START_REF] Perchet | Calibration and internal no-regret with random signals[END_REF]. The main ideas behind them are similar to the full monitoring case so we will quickly describe them. For simplicity, we assume in the following sketch of the proof, that the decision maker fully observes the sequence of flags

f n = s(j n ) ∈ ∆(S) I .
Recall that W is continuous (see Lugosi, Mannor & Stoltz [START_REF] Lugosi | Strategies for prediction under imperfect monitoring[END_REF], Proposition A.1), so for every ε > 0 there exist two finite families G = {f (l) ∈ ∆(S) I ; l ∈ L}, a δ-grid of ∆(S) I , and X = {x(l) ∈ ∆(I); l ∈ L} such that if f is δ-close to f (l) and x is δ-close to x(l) then x belongs to BR ε (f ). A calibrated algorithm ensures that: i) fn (l) is asymptotically δ-close to f (l) -because it is closer to f (l) than to every other f (k);

ii) īn (l) converges to x(l) as soon as |N n (l)| is big enough -because on N n (l) the choices of action of the decision maker are independent and identically distributed accordingly to x(l);

iii) ρn (l) converges to ρ(x(l), n (l)) which is greater than W x(l), fn (l)

-because n (l) generates the flag fn (l).

Therefore, W x(l), fn (l) is close to W x(l), f (l) which is greater than W z, f (l) for any z ∈ ∆(I). As a consequence ρn (l) is asymptotically greater (up to some ε > 0) than sup z W z, fn (l) , as long as |N n (l)| is big enough.

The difference between the two algorithm lies in the construction of a calibrated strategy. On one hand, the algorithm of Lehrer & Solan [START_REF] Lehrer | Learning to play partially-specified equilibrium[END_REF] reduces to Blackwell's approachability of some convex set C ⊂ R LSI ; it therefore requires to solve at each stage a linear program of size polynomial in ε SI , after a projection on C. On the other hand, the algorithm of Perchet [START_REF] Perchet | Calibration and internal no-regret with random signals[END_REF] is based on the construction given in section 1.2.1; it solves at each stage a system of linear equation of size also polynomial in ε SI .

The conclusions of the full monitoring case also apply here: these highly non-efficient algorithms cannot be used directly to construct (L, 0)-internally consistent strategy with optimal rates since the constants depend drastically on ε . We will rather prove that one can define wisely once for all {f (l), ω(l); l ∈ L} and {x(l); l ∈ L} (see Proposition 2.6 and Proposition 1.11) so that x(l) ∈ ∆(I) is a 0-best response to any flag f in P (l), the Laguerre cell associated to f (l) and ω(l).

The strategy associated with these choices will be (L, 0)-internally consistent, with an optimal rate of convergence and a computational complexity polynomial in L.

Optimal algorithms

As in the full monitoring framework (cf Lemma 1.10), we define for every x ∈ ∆(I) the x-best response area B x as the set of flags to which x is a best response :

B x = f ∈ ∆(S) I ; x ∈ BR(f ) = BR -1 (x).
Since W is continuous, the family {B x ; x ∈ ∆(I)} is a covering of ∆(S) I . However, one of its finite subsets can be decomposed into a finite polytopial complex:

Proposition 2.6 There exists a finite family X = {x(l) ∈ ∆(I); l ∈ L} such that the family B x(l) ; l ∈ L of associated best response area can be further subdivided into a polytopial complex of ∆(S) I .

The rather technical proof can be found in Appendix A.2. In this framework and because of the lack of linearity of W , any B x(l) might not be convex nor connected. However, each one of them is a finite union of polytopes and the family of all those polytopes is a complex of ∆(S) I .

Remark 2.7 As a consequence of Proposition 2.6, there exists a finite set X ⊂ ∆(I) that contains a best response to any flag f . In particular, if the decision maker could observe the flag f n before choosing his action x n then, at every stage, x n would be in X. So in the description of the strategies of the forecaster, the finite set {x(l); l ∈ L} = X is in fact intrinsic i.e. determined by the description of the payoff and signal functions.

As a consequence of this remark, mentioning L is irrelevant; so we will, from now on, simply speak of internally consistent strategies.

Outcome dependent signals

In this section, we assume that the laws of the signal received by the decision maker are independent of his action. Formally, for every i, i ′ ∈ I, the two mappings s(i, •) and s(i ′ , •) are equal. Therefore, F (the set of realizable flags) can be seen as a polytopial subset of ∆(S). Proposition 2.6 holds in this framework, hence there exists a finite family {x(l); l ∈ L} such that for any flag f ∈ F, there is some l ∈ L such that x(l) is a best-reply to f . Moreover, for a fixed l ∈ L, the set of such flags is a polytope. Theorem 2.8 There exists an internally consistent strategy σ such that for every strategy τ of Nature, with P σ,τ -probability at least 1δ:

sup l∈L |N n (l)| n R n (l) ≤ O   ln 1 δ n   . ( 8
)
Proof. Propositions 1.11 and 2.6 imply the existence of two finite families {x(l); l ∈ L} and {f (l), ω(l); l ∈ L} such that x(l) is a best response to any f in P (l), the Laguerre cell associated to f (l) and ω(l). Assume, for the moment, that for any two different l and k in L, the probability measures x(l) and x(k) are different.

The strategy σ is defined as follows. Compute a strategy σ calibrated with respect to {f (l), ω(l); l ∈ L}. When the decision maker (seen as a predictor) should choose l ∈ L accordingly to σ, then he (seen as a forecaster) plays accordingly to x(l) in the original game. Corollary 1.14 (with the assumption that (b, c) ∞ is smaller than 1) implies that with P σ,τ probability at least 1δ 1 :

max l∈L |N n (l)| n sn (l) -f (l) 2 -ω(l) -sn (l) -f (k) 2 -ω(k) ≤ 8 √ L √ n + 4 √ n 2 ln L 2 δ 1 ,
therefore combined with Lemma 1.12, this yields that :

max l∈L |N n (l)| n sn (l) -f n (l) ≤ 8M P √ L √ n + 4M P √ n 2 ln L 2 δ 1 , (9)
where f n (l) is the projection of sn (l) onto P (l).

Hoeffding-Azuma's inequality implies that with P σ,τ probability at least 1δ 2 :

max l∈L |N n (l)| n sn (l) -fn (l) ≤ 2 ln 2SL δ 2 n (10)
and with probability at least 1δ 3 :

max l∈L |N n (l)| n ρn (l) -ρ(x(l), n (l)) ≤ M ρ 2 ln 2L δ 3 n . (11)
W is M W -Lipschitz in f (see Lugosi, Mannor & Stoltz [START_REF] Lugosi | Strategies for prediction under imperfect monitoring[END_REF]) and s ( n (l)) = fn (l) therefore: [START_REF] Dawid | The well-calibrated Bayesian[END_REF] and max x∈∆(I) W x, fn (l) is smaller than max

ρn (l) ≥ W x(l), f n (l) -ρn (l) -ρ(x(l), n (l)) -M W fn (l) -f n (l)
x∈∆(I) W x, f n (l) + M W sn (l) -fn (l) + sn (l) -f n (l) = W x(l), f n (l) + M W sn (l) -fn (l) + sn (l) -f n (l) (13)
since x(l) is a best response to f n (l). Equations ( 12) and ( 13) yield

R n (l) ≤ 2M W sn (l) -fn (l) + 2M W sn (l) -f n (l) + ρn (l) -ρ(x(l), n (l)) . (14)
Combining equations ( 9), ( 10), ( 11) and ( 14) gives that with probability at least 1δ, if we define

Ω 0 = 16M P M W √ L, Ω 1 = (2M W + 8M W M P + M ρ ) and Ω 2 = L (L + 2S + 2): sup l∈L |N n (l)| n R n (l) ≤ Ω 0 √ n + Ω 1 √ n 2 ln 2Ω 2 δ (15)
If there exist l and k such that x(l) = x(k), then although the decision maker made two different predictions f (l) or f (k), he played accordingly to the same probability x(l) = x(k). Define N n (l, k) as the set of stages where the decision maker predicts either f (l) or f (k) up to stage n, fn (l, k) as the average flag on this set, ρn (l, k) as the average payoff and R n (l, k) as the regret. Since W (x, •) is convex for every x ∈ ∆(I), then max x∈∆(I) W (x, •)

is also convex so |Nn(l,k)| n max x∈∆(I) W (x, fn (l, k)) is smaller than |N n (l)| n max x∈∆(I) W (x, fn (l)) + |N n (k)| n max x∈∆(I) W (x, fn (k)) and - |N n (l, k)| n ρn (l, k) = - |N n (l)| n ρn (l) - |N n (k)| n ρn (k)
so we still have

|N n (l, k)| n R n (l, k) ≤ O   ln 1 δ n   .
Hence the previous bound holds up to a factor L.

Remark 2.9 Lugosi, Mannor & Stoltz [START_REF] Lugosi | Strategies for prediction under imperfect monitoring[END_REF] have constructed an externally consistent strategy, i.e. such that, asymptotically, for any strategy τ of Nature: ρn ≥ max z∈∆(I) W z, fn , P σ,τ -as.

The final argument in the proof of Theorem 2.8 also implies that an internally consistent strategy is also externally consistent, hence we can compare bounds between our algorithm. If the signals are deterministic, Lugosi, Mannor & Stoltz [START_REF] Lugosi | Strategies for prediction under imperfect monitoring[END_REF]'s efficient algorithm has an expected regret smaller than O n -1/2 . However this bound became, with random signals, O n -1/4 . Thus our algorithm, along with computing no internal regret, has a better rate of convergence -the optimal one. Concerning the computational complexity, the true purpose of this algorithm being the minimization of internal regret, it is not efficient to bound external regret.

Action-Outcome dependant signals

In this section, we consider the most general framework and we assume that the laws of the signals might depend on the decision maker's actions. Our main result is the following: Theorem 2.10 There exists an internally consistent strategy σ such that, for every strategy τ of Nature, with P σ,τ probability at least 1δ:

max l∈L |N n (l)| n R n (l) ≤ O 1 n 1/3 ln 1 δ + 1 n 2/3 ln 1 δ . (16)
Proof. The proof is essentially the same as the one of Theorem 2.8, so we can assume that x(l) = x(k) for any two different l and k in L. The only difference is due to the fact that at stage n ∈ N, the unobserved flag f n has to be estimated (see e.g. Lugosi, Mannor & Stoltz [START_REF] Lugosi | Strategies for prediction under imperfect monitoring[END_REF]).

Following Auer, Cesa-Bianchi, Freund & Schapire [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF], we define for every l ∈ L and n ∈ N, the γ n -perturbation of x(l) by x(l, n) = (1γ n )x(l) + γ n u where u is the uniform probability over I and ( γ n ) n∈N is a non-negative non-increasing sequence. For every n ∈ N, let

e n = 1 i=in x(l n , n)[i n ] (1 s=sn ) s∈S i∈I ∈ R S I ,
where x(l n , n)[i n ] ≥ γ n = γ n /I > 0 is the weight put by x(l n , n) on i n . With this notation, e n is an unbiased estimator of f n since E σ,τ e n |h n-1 = f n , seen as an element of R S I .

We define now the strategy of the forecaster. Assume that in an auxiliary game Γ c , a predictor computes σ, a calibrated strategy with respect to {f (l), ω(l); l ∈ L}, but where the state at stage n is the estimator e n ∈ R IS . When the decision maker (seen as a predictor) should choose l n accordingly to σ in Γ c , then he (seen as a forecaster) chooses i n accordingly to x(l n ) in the original game.

In order to use Corollary 1.14, we need to bound v n , M n and K n . In the current framework and thanks to Proposition 1.11, one has for every l, k ∈ L and n ∈ N:

U l,k ω,n = 21 l=ln t∈T σ t (k) -σ t (l) T e n , c t + b t ,
so using the fact that (b, c) 2 ∞ = 1 and the definition of e n : sup l,k∈L

sup m≤n E σ,τ U l,k ω,m 2 ≤ 16E σ,τ e n 2 ≤ 16 i∈I x(l n , n)[i] ( x(l n , n)[i]) 2 ≤ 16 I γ n .
As a consequence, K n ≤ 4 1 γn , v n ≤ 4 I γn and M n ≤ 4 LI γn . Lemma 1.12 implies that, with P σ,τ probability at least (1δ 1 ), for every l ∈ L:

|N n (l)| n ēn (l) -f n (l) ≤ 8 √ LIM P √ γ n n + 8 √ IM P √ γ n n 2 ln L 2 δ 1 + 8 3
M P γ n n ln L 2 δ 1 ,
where f n (l) is the projection of ēn (l) onto P (l). Following Lugosi, Mannor & Stoltz [START_REF] Lugosi | Strategies for prediction under imperfect monitoring[END_REF], since for every i ∈ I and s ∈ S,

E σ,τ |e i,s n | 2 ≤ 1/γ n , Freedman's inequality implies that with probability at least 1 -δ 2 , for every l ∈ L |N n (l)| n ēn (l) -fn (l) ≤ √ IS 2 1 nγ n ln 2LIS δ 2 + 2 3nγ n ln 2LIS δ 2 .
Hoeffding-Azuma's inequality implies that with probability at least 1δ 3 :

max l∈L N n (l) n ρn (l) -ρ(x(l), n (l)) ≤ M ρ 2 n ln 2L δ 3 + 2M ρ m∈Nn(l) γ m n ,
and by taking γ n = n -1/3 , one has m∈Nn(l) γ m ≤ 3I 2 n 2/3 . As a consequence, for every l ∈ L, with probability at least 1δ:

N n (l) n R n (l) ≤ Ω 1 n 1/3 + Ω 2 n 1/3 2 ln 2Ω 5 δ + Ω 3 n 1/2 2 ln 2Ω 5 δ + 2 3 Ω 4 n 2/3 ln 2Ω 5 δ
with the constants defined by

Ω 1 = 16M P M W √ LI + 3M W M ρ I, Ω 2 = 2M W √ I 8M P + √ S , Ω 3 = M ρ , Ω 4 = 2M W (4M P + √ IS)
and Ω 5 = L (L + 2 + 2IS). They can be decreased if concentration inequalities in Hilbert spaces are used (see section 3.3).

In the label efficient prediction game defined in Example 2.1, for every strategy σ of the decision maker there exists a sequence of outcomes such that the forecaster expected regret is greater than n -1/3 /7 (see Theorem 5.1 in Cesa-Bianchi, Lugosi & Stoltz [START_REF] Cesa-Bianchi | Minimizing regret with label efficient prediction[END_REF]). Therefore the rate of n -1/3 of our algorithm is optimal for both internal and external regret.

The computational complexity of this internally consistent algorithm is polynomial in L. Thus it can be seen, in some sense, as an efficient one. A question left open is the existence of an algorithm whose computational complexity is polynomial in the minimal number of best-response areas required to cover ∆(S) I , see Proposition 2.6.

The following section 3.1 deals with a simpler question and exhibits an internally consistent algorithm which requires to solve at each stage a linear program of size polynomial in L 0 , the minimal number of polytopes on which BR is constant, instead of a system of linear equations of size L.

3 Concluding remarks 3.1 Second algorithm: calibration and polytopial complex.

The algorithms we described are quite easy to run stage by stage since the forecaster only needs to compute some invariant measures of non-negative matrices. However, they require to construct the Laguerre diagram P = {P (l); l ∈ L} given the set {b t , c t ; t ∈ T }. And we have shown that L, which is a factor both in the complexity of the algorithms and in their rate of convergence, can be in the order of T SI hence polynomial in L SI 0 .

This section is devoted to a modification of the algorithm that does not require to compute a Laguerre diagram but which is more difficult, stage by stage, to implement. The only difference between the two algorithms is in the definition of calibration.

Let {K(l); l ∈ L 0 } be a finite polytopial complex of ∆(J ). It is defined by two finite families c t ∈ R J , b t ∈ R; t ∈ T and {T (l) ⊂ T ; l ∈ L} such that:

K(l) = {y ∈ ∆(J ); y, c t ≤ b t , ∀t ∈ T (l) ⊂ T } , ∀l ∈ L 0 .
Let us define (c t,l , b t,l ) = (c t , b t ) if t ∈ T (l) and (c t,l , b t,l ) = (0, 0) otherwise. Then we can rewrite K(l) = {y ∈ ∆(J ); y, c t,l ≤ b t,l , ∀t ∈ T }. Definition 3.1 A strategy σ is calibrated w.r.t. the complex {K(l); l ∈ L 0 } if for every strategy τ of Nature, P σ,τ -as:

lim sup n→∞ |N n (l)| n n (l), c t,l -b t,l ≤ 0, ∀t ∈ T , ∀l ∈ L 0 .
Theorem 3.2 There exist calibrated strategies w.r.t. any finite polytopial complex {K(l); l ∈ L 0 }.

Proof. Consider the following auxiliary two-person game Γ ′ c , where at stage n ∈ N the predictor (resp. Nature) chooses l n ∈ L 0 (resp. j n ∈ J ) which generates the vector payoff U n ∈ R T L 0 defined by:

U lk n = 1 jn=j , c t,l -b t,l if l = l n 0 otherwise.
Any strategy that approaches the negative orthant Ω -in Γ ′ c is calibrated w.r.t. the complex {K(l); l ∈ L 0 }.

Blackwell's characterization of approachable convex sets (see Blackwell [START_REF] Blackwell | An analog of the minimax theorem for vector payoffs[END_REF], Theorem 3) implies that the predictor can approach the convex set Ω - if (and only if) for every mixed action of Nature in ∆(J ), he has an action x ∈ ∆(L 0 ) such that the expected payoff is in Ω -. Given y n ∈ ∆(J ), choosing l(y n ) ∈ L 0 , where l(y n ) is the index of the polytope that contains y n , ensures that E yn,l(yn) [U n ] is in Ω -. Therefore there exist calibrated strategies with respect to any polytopial complex. This modification of the definition of calibration does not change the other part of our algorithms nor the remaining of the proofs (in particular, to calibrate the sequence of unobserved flags, the forecaster must use γ nperturbations). The constants in the rates of convergence are now smaller since L 0 can be much smaller than L and in Γ

′ c , E[ U n 2 ] is bounded by O T 0 γn
where T 0 = sup l∈L 0 T (l) is the maximum number of hyperplanes defining a polytope of the complex.

The main argument behind this algorithm (i.e. the characterization of approachable convex sets of Blackwell [START_REF] Blackwell | An analog of the minimax theorem for vector payoffs[END_REF]) is quite close, in spirit, to the one of Lehrer & Solan [START_REF] Lehrer | Learning to play partially-specified equilibrium[END_REF]. Note that however, with our representation, the projection on Ω -can be computed linearly in T L 0 , so polynomially in L 0 . Therefore, it reduces to the construction of an approachability strategy and so -as shown by Blackwell [START_REF] Blackwell | An analog of the minimax theorem for vector payoffs[END_REF] -to the resolution, at each stage, of a linear programming of size polynomial in L 0 .

Extension to the compact case

We prove in this section that the finiteness of J is not required.

Assume that instead of choosing j n at stage n ∈ N -which generates the flag f n = s(j n ) and an outcome vector ρ(i, j n ) i∈I -Nature chooses directly an outcome vector O n ∈ [-1, 1] I and a flag f n which belongs to s(O n ) where s is a multivalued mapping from [-1, 1] I into ∆(S) I . As before, the decision maker's payoff is O in n (the i n -th coordinate of O n ) and he receives a signal s n whose law is f in n . Strategies of the forecaster and consistency are defined as before.

Theorem 3.3 If the graph of s is a polytope, then there exists an internally consistent strategy σ such that, for every strategy τ of Nature, with P σ,τ probability at least 1δ:

max l∈L |N n (l)| n R n (l) ≤ O 1 n 1/3 ln 1 δ + 1 n 2/3 ln 1 δ . (17)
The proof of this result is identical to the one of Theorem 2.10. Note that the assumption that the graph of s is a polytope is fulfilled in the finite dimension case. The mapping s is multivalued since in finite dimension there might exist two different mixed actions y 1 , y 1 in ∆(J ) that generate the same outcome vectore (i.e. ρ(•, y

1 ) = ρ(•, y 2 ) = O) but different flags (i.e. f 1 = s(y 1 ) = s(y 2 ) = f 2 ). Hence we should have f 1 , f 2 ∈ s(O).

Strengthening of the constants

We propose two different ideas to strengthen the constants of our algorithm. First, we can use (as did Lugosi, Mannor & Stoltz [START_REF] Lugosi | Strategies for prediction under imperfect monitoring[END_REF]) only one concentration inequality for every coordinate of the vector U ω,n instead of one concentration inequality per coordinate. Second, we can implement sparser vector payoffs (so that its norm decreases) by looking at a slight different definition of calibration.

Concentration Inequalities in Hilbert Spaces

The rates of convergence of our algorithms rely mainly on three properties: Blackwell's approachability theorem, Hoeffding-Azuma's and Freedman's inequalities. These tools allowed us to study the convergence of a sequence of vectors Ū + n towards 0. Approachability is well defined for sequences of vectors, however the two concentration inequalities hold only for real valued martingales. To circumvent this issue, we used in the proofs the fact that if a process U n ∈ R d n∈N is a martingale then, for each coordinate, the process U k n ∈ R n∈N is a real valued martingale. This does not use the fact that U n might be sparse and the use of concentration inequalities in Hilbert space can sharpen the constant. Indeed, recall Hoeffding-Azuma's inequality: Lemma 3.4 (Hoeffding [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF], Azuma [START_REF] Azuma | Weighted sums of certain dependent random variables[END_REF]) Let U n be a sequence of martingale differences bounded by K, i.e. for every n ∈ N, E σ,τ [U n+1 |h n ] = 0 and |U n | < K.

Then for every n ∈ N and every ε > 0:

P σ,τ Ūn ≥ ε ≤ 2 exp -nε 2 2K 2 ,
which can be expressed as

P σ,τ Ūn ≤ K 2 n ln 2 δ ≥ 1 -δ. (18)
Chen & White [START_REF] Chen | Laws of large numbers for Hilbert space-valued mixingales with applications[END_REF] proved an equivalent property for vector martingale in R d .

Lemma 3.5 (Chen & White [START_REF] Chen | Laws of large numbers for Hilbert space-valued mixingales with applications[END_REF]) Let U n be a sequence of martingale differences in R d bounded almost-surely by K > 0. Then for every n ∈ N and for every ε > 0:

P σ,τ Ūn ≥ ε ≤ 2 max 1, nε 2 2K 2 exp -nε 2 2K 2 ≤ 2 exp -α nε 2 2K 2 ,
for every α ≤ 1 -1 2e (which equals approximatively 0.81).

Assume that for every n ∈ N, U n ∞ ≤ U ∞ and U n 2 ≤ U 2 ; we can deduce from the use of only Hoeffding-Azuma's inequality that:

P σ,τ max l,k |N n (l)| n Ū l,k n ≥ ε ≤ 2L 2 exp -nε 2 2 U 2 ∞ .
However, Chen and White's result, along with the fact that U n ≤ L, implies that:

P σ,τ max l,k |N n (l)| n Ū l,k n ≥ ε ≤ 2 exp -nε 2 4 U 2 2
which can reduce the dependency in L. The effects is even more dramatic when estimating the sequences of flags, since e n has only positive component (so e n ∞ = e n 2 ).

There also exist variants of Bernstein's inequality (see e.g. Yurinskii [START_REF] Yurinskii | Exponential inequalities for sums of random vectors[END_REF]) in Hilbert spaces that can be used in order to get more precise constants.

For any vertex v of P (l), there exists t 1 , . . . , t d ∈ T (l) such that

v = d k=1 Z ∈ R d ; Z, c t k = b t k and {c t 1 , . . . , c t d } is a basis of R d . If we denote by v ε the point defined by v ε = d k=1 Z ∈ R d ; Z, c t k = b t k + ε then P ε (l) is included in the convex hull of every v ε .
Equation ( 5) can be rephrased as: if x belongs to P ε (l) then d(x, P (l)) is smaller than M P ε. Therefore it is enough to prove this property for every v ε since d(•, P (l)) is a convex mapping thus maximized over a polytope on one of its vertices.

With these notations, for every k ∈ {1, . . . , d}, v εv, c t k = ε and there exists a unique decomposition v 2

ε -v = d k=1 α k c t k . Define the symmetric d × d Gram matrix Q l by Q kk ′ l = c t k , c t k ′ and α = (α 1 , . . . , α d ). Then following classical properties hold: 1) v ε -v 2 = α T Q l α
) Qα = ε = (ε, . . . , ε) therefore α = Q -1 l ε; 3) v ε -v 2 = (Q -1 l ε) T Q l (Q -1 l ε) = ε T P T D -1 P ε ≤ ε 2 dλ -1 1 .
Therefore, for any Z ∈ P ε -and in particular for any point that satisfies Equation ( 5

) -, Z -Π l (Z) ≤ max v v ε -v ≤ ε. √ d √ λ 1 -1 .
The result follows from the fact that L is finite. The constant M P in Lemma 1.12 is smaller than the square root of the inverse of the smallest eigenvalue of all Q l times √ d; it depends on the inner products c t , c t ′ and on the dimension of F.

A.2 Proof of proposition 2.6

Definition A.1 Let K be a polytope. A correspondence B : K ⇉ R d is polytopial constant, if there exists {K(l); l ∈ L} a finite polytopial complex of K and {x(l); l ∈ L} such that x(l) ∈ B(f ) for every f ∈ K(l).

Let us now restate Proposition 2.6:

Proposition A.2 BR is polytopial constant.
This theorem is well-known and quite useful in the full monitoring case (see for example the Lemke-Howson [START_REF] Lemke | Equilibrium points of bimatrix games[END_REF] algorithm). In the compact case, Proposition 2.6 becomes: Proposition A.3 If s has a polytopial graph, then BR is polytopial constant.

The proofs of both propositions rely on polytopial parameterized max-min programs defined in the next subsection. where A is a d 1 × d 2 matrix, {E f , e f ; f ∈ F} is a family of matrices and vectors (we do not specify the sizes the matrices, as long as each inequality makes sense) and D, d are also a fixed matrix and vector such that the admissible set D = {x ∈ X; Dx ≤ d} is a polytope. The solution set of (P f ) is denoted by B(f ) ⊂ X and this defines a multivalued mapping B(•) from F into X . Points i) and ii) imply that if x f maximizes (P f ) -which is then minimized at some a vertex of S f denoted by y f , because of point i) -then it can be assumed that -x f A is a vertex of the polytope N C S f (y f ) ∩ D A-where D A-:= {-xA; x ∈ D}. Thus B(f ), the solution set to (P f ) contains at least an element of

X f = x ∈ D; -xA vertex of D A-∩ N C S f (y f ), y f vertex of S f .
By point iii), the normal fan and therefore X f are constant on K(l). The latter can also be assumed to be finite by taking a unique representant x ∈ X f for every vertices of the intersection of the normal fan and D A-. Since the number of different fans is finite, for any f ∈ F, the solution set to (P f ) contains at least an element of the finite set X = f ∈F X f . Moreover, for every x ∈ X: where, respectively, the second line is a consequence of point iv), the third line of the definition of X and the fourth and fifth lines of points i) and v).

B -1 (x) = f ∈ F; min
By point v), the two mapping y(•) and y ′ (•) are affine on K(l), so each possible set f ∈ K(l); xAy(f ) ≥ x ′ Ay ′ (f ) is a polytope as the intersection of an half-space and the polytope K(l).

Since, the intersection of a union of polytopes remains a union of polytopes, for every x ∈ X, B -1 (x) is a finite union of polytopes and B is polytopial constant.

We can now prove simultaneously Propositions A. is polytopial constant. We denote by {K(l); l ∈ L} a corresponding polytopial complex. If B is constant on K(l), then it is also constant on K(l) = Π -1 S (K(l)), which is a finite union of polytopes.

Example 2 . 1

 21 Label efficient prediction (Example 6.8 in Cesa-Bianchi & Lugosi [9]): Consider the following game. Nature chooses an outcome G or B and the forecaster can either observe the actual outcome (action o) or choose to not observe it and pick a label g or b. His payoff is equal to 1 if he chooses the right label and otherwise is equal to 0. Payoffs and laws of signals are defined by the following matrices (where a, b and c are three different probabilities over a finite given set S).Action G, whose best response is g, generates the flag (a, c, c) and action B, whose best response is b, generates the flag (b, c,

  and there exist a D = diag(λ 1 , . . . , λ d ) a diagonal matrix with 0 < λ 1 ≤ . . . ≤ λ d and a d × d matrix P and such that P -1 = P T and Q l = P T DP ;

A. 2 . 1

 21 Constant Solution of a Polytopial Parameterized Max-Min ProgramA Polytopial Parameterized Max-Min Program (PPMP) is defined as follows. Let X and Y be two Euclidian spaces of respective dimension d 1 and d 2 . Consider the program (P f ) -depending on a parameter f that belongs to some polytope F in R d 3 -that is defined by(P f ) : max x ∈ X s.t. Dx ≤ d min y ∈ Y s.t. E f y ≤ e f xAy,

Theorem A. 4

 4 Assume that the correspondence S defined by:S : F ⇉ Y f → S f = {y ∈ Y; E f y ≤ e f }has a polytopial graph S. Then B : F ⇉ X is polytopial constant.Proof. Before going into full details, we first recall the following properties: i) A linear program is minimized on a vertex of the polytopial feasible set (this is actually implied by the following point);ii) Rockafella[START_REF] Rockafellar | Convex Analysis[END_REF], Theorem 27.4, page 270: Given x ∈ D and f ∈ F, if y minimizes xAy on S f then-xA ∈ N C S f (y),where N C E (y) is the normal cone to the convex set E ⊂ R d at y ∈ E defined by :N C E (y) = p ∈ R d ; p, zy , ∀z ∈ E ;iii) Ziegler[START_REF] Ziegler | Lectures on Polytopes[END_REF], Example 7.3, page 193: If P is a polytope then the finite family {N C P (v); v is a vertex of P } is a polyhedral complex of R d called a normal fan (i.e. it is a finite family of polyhedra that cover R d and such that each pair has an intersection with empty interior); iv) Billera & Sturmfels[START_REF] Billera | Fiber polytopes[END_REF], page 530: Since for every f ∈ F, S f = Π -1 (f ) where Π : S ⊂ F × Y → F is the projection with respect to first coordinates, then there exists {K(l); l ∈ L}, a polytopial complex of F such that the normal fan to S f is constant on every K(l) (this can alternatively be deduced from the following point); v) Rambau & Ziegler[START_REF] Rambau | Projections of polytopes and the generalized Baues conjecture[END_REF], Proposition 2.4, page 221: On each of these polytopes K(l), the mapping f → S f is linear. In particular, there exists a finite family of affine functions Y (l) from K(l) to Y such that the vertices of S f are exactly {y(f ); y(•) ∈ Y (l)}.

=

  l∈L x ′ ∈X y ′ (•)∈Y (l) f ∈ K(l); min y∈S f xAy ≥ x ′ Ay ′ (f ) = l∈L x ′ ∈X y ′ (•)∈Y (l) y(•)∈Y (l) f ∈ K(l); xAy(f ) ≥ x ′ Ay ′ (f ) ,

2 and A. 3 :A. 2 . 2

 322 Proof of Propositions A.2 and A.3 Since s is linear, its graph, denoted by S, is a polytope. Theorem A.4 (with D = ∆(I)) implies that the solution, denoted by B(f ) for every f ∈ F, of the parameterized program max x∈∆(I) min y∈s -1 (f ) ρ(x, y)

Acknowledgements: I deeply thank my PhD advisor Sylvain Sorin for its great help and support. I also acknowledge very useful comments of Gilles Stoltz.

We defined a calibrated strategy with respect to Y, as a strategy σ such that n (l) is asymptotically closer to y(l) than to any other y(k) as soon as the frequency of l does not go to zero. In fact, n (l) needs only to be closer to y(l) than to any of its neighbors. So one can construct neighbors-calibrated strategies by modifying the algorithm given in Proposition 1.5; the payoff at stage n is now denoted by U ′ n and is defined by:

The strategy consisting in choosing an invariant measure of Ū ′ n

, where N is the maximal number of neighbors. This latter can be much smaller than 4, and the gain from this modification is limpid if we consider ε-calibration.

Indeed, in order to construct such strategies, we usually take any εdiscretization of ∆(J) so that L = O ε -(J-1) . However, there exists a discretization such that N = 2 -(J-1) , which is independent of ε.

A Proofs of technical results

This section is devoted to the proofs of previously mentioned results, i.e. Lemma 1.12 and Proposition 2.6.

A.1 Proof of Lemma 1.12

Let l ∈ L be fixed. we denote by C = c t ∈ R d ; t ∈ T (l) the finite family of normal vectors to (d -1)-faces of P (l) and by B = {b t ∈ R; t ∈ T (l)} the family of scalars such that :

Any points satisfying Equation (5) belongs to P ε (l) = Z ∈ R d ; Z, c t ≤ b t + ε, ∀t ∈ T (l) .