American Institute of Mathematical Sciences

Advanced
April  2014, 1(2): 181-254. doi: 10.3934/jdg.2014.1.181

Approachability, regret and calibration: Implications and equivalences

Vianney Perchet 1,

1. 

Université Paris-Diderot, Laboratoire de Probabilités et Modèles Aléatoires, UMR 7599, 8 place FM/13, Paris, France

Received  January 2013 Revised  January 2014 Published  March 2014

Blackwell approachability, regret minimization and calibration are three criteria used to evaluate a strategy (or an algorithm) in sequential decision problems, described as repeated games between a player and Nature. Although they have at first sight not much in common, links between them have been discovered: for instance, both consistent and calibrated strategies can be constructed by following, in some auxiliary game, an approachability strategy.
    We gather seminal and recent results, develop and generalize Blackwell's elegant theory in several directions. The final objectives is to show how approachability can be used as a basic powerful tool to exhibit a new class of intuitive algorithms, based on simple geometric properties. In order to be complete, we also prove that approachability can be seen as a byproduct of the very existence of consistent or calibrated strategies.
Keywords: Blackwell's approachability, calibration., regret minimization.
Mathematics Subject Classification: Primary: 91A25, 68W27; Secondary: 91A2.
Citation: Vianney Perchet. Approachability, regret and calibration: Implications and equivalences. Journal of Dynamics & Games, 2014, 1 (2) : 181-254. doi: 10.3934/jdg.2014.1.181
References:
[1]

J. Abernethy, P. Bartlett and E. Hazan, Blackwell approachability and low-regret learning are equivalent,, J. Mach. Learn. Res.: Workshop Conf. Proc., 19 (2011), 27.   Google Scholar

[2]

S. As Soulaimani, M. Quincampoix and S. Sorin, Repeated games and qualitative differential games: Approachability and comparison of strategies,, SIAM J. Control Optim., 48 (2009), 2461.  doi: 10.1137/090749098.  Google Scholar

[3]

P. Auer, N. Cesa-Bianchi and C. Gentile, Adaptive and self-confident on-line learning algorithms,, J. Comput. System Sci., 64 (2002), 48.  doi: 10.1006/jcss.2001.1795.  Google Scholar

[4]

R. J. Aumann, Subjectivity and correlation in randomized strategies,, J. Math. Econom., 1 (1974), 67.  doi: 10.1016/0304-4068(74)90037-8.  Google Scholar

[5]

R. J. Aumann and M. B. Maschler, Repeated Games with Incomplete Information,, MIT Press, (1995).   Google Scholar

[6]

M. Benaïm and M. Faure, Consistency of vanishingly smooth fictitious play,, Math. Oper. Res., 38 (2013), 437.  doi: 10.1287/moor.1120.0568.  Google Scholar

[7]

M. Benaïm, J. Hofbauer and S. Sorin, Stochastic approximations and differential inclusions. II. Applications,, Math. Oper. Res., 31 (2006), 673.  doi: 10.1287/moor.1060.0213.  Google Scholar

[8]

A. Bernstein, S. Mannor and N. Shimkin, Opportunistic strategies for generalized no-regret problems,, J. Mach. Learn. Res.: Workshop Conf. Proc., 30 (2013), 158.   Google Scholar

[9]

A. Bernstein and N. Shimkin, Response-based approachability and its application to generalized no-regret algorithms,, Manuscript., ().   Google Scholar

[10]

L. J. Billera and B. Sturmfels, Fiber polytopes,, The Annals of Mathematics, 135 (1992), 527.  doi: 10.2307/2946575.  Google Scholar

[11]

D. Blackwell, An analog of the minimax theorem for vector payoffs,, Pacific J. Math., 6 (1956), 1.  doi: 10.2140/pjm.1956.6.1.  Google Scholar

[12]

D. Blackwell, Controlled random walks,, in Proceedings of the International Congress of Mathematicians, (1954), 336.   Google Scholar

[13]

D. Blackwell and M. A. Girshick, Theory of Games and Statistical Decisions,, John Wiley and Sons, (1954).   Google Scholar

[14]

A. Blum and Y. Mansour, From external to internal regret,, in Learning theory, (2005), 621.  doi: 10.1007/11503415_42.  Google Scholar

[15]

S. Bubeck, Introduction to online optimization,, Manuscript., ().   Google Scholar

[16]

N. Cesa-Bianchi and G. Lugosi, Potential-based algorithms in on-line prediction and game theory,, Machine Learning, 51 (2003), 239.   Google Scholar

[17]

N. Cesa-Bianchi and G. Lugosi, Prediction, Learning, and Games,, Cambridge University Press, (2006).  doi: 10.1017/CBO9780511546921.  Google Scholar

[18]

X. Chen and H. White, Laws of large numbers for Hilbert space-valued mixingales with applications,, Econometric Theory, 12 (1996), 284.  doi: 10.1017/S0266466600006599.  Google Scholar

[19]

A. P. Dawid, The well-calibrated Bayesian,, J. Amer. Statist. Assoc., 77 (1982), 605.  doi: 10.1080/01621459.1982.10477856.  Google Scholar

[20]

A. P. Dawid, Self-calibrating priors do not exist: Comment,, J. Amer. Statist. Assoc., 80 (1985), 339.  doi: 10.1080/01621459.1985.10478117.  Google Scholar

[21]

L. Evans and P. E. Souganidis, Differential games and representation formulas for solutions of Hamilton-Jacobi equations,, Indiana Univ. Math. J., 33 (1984), 773.  doi: 10.1512/iumj.1984.33.33040.  Google Scholar

[22]

K. Fan, Minimax theorems,, Proc. Nat. Acad. Sci. U. S. A., 39 (1953), 42.  doi: 10.1073/pnas.39.1.42.  Google Scholar

[23]

K. Fan, A minimax inequality and applications,, in Inequalities, (1972), 103.   Google Scholar

[24]

W. Feller, An Introduction to Probability Theory and its Applications. Vol. I,, Third edition, (1968).   Google Scholar

[25]

D. P. Foster, A proof of calibration via blackwell's approachability theorem,, Games and Economic Behavior, 29 (1999), 73.  doi: 10.1006/game.1999.0719.  Google Scholar

[26]

D. P. Foster, A. Rakhlin, K. Sridharan and A. Tewari, Complexity-based approach to calibration with checking rules,, J. Mach. Learn. Res.: Workshop Conf. Proc., 19 (2011), 293.   Google Scholar

[27]

D. P. Foster and R. V. Vohra, Calibrated learning and correlated equilibrium,, Games Econom. Behav., 21 (1997), 40.  doi: 10.1006/game.1997.0595.  Google Scholar

[28]

D. P. Foster and R. V. Vohra, Asymptotic calibration,, Biometrika, 85 (1998), 379.  doi: 10.1093/biomet/85.2.379.  Google Scholar

[29]

D. P. Foster and R. V. Vohra, Regret in the on-line decision problem,, Games Econom. Behav., 29 (1999), 7.  doi: 10.1006/game.1999.0740.  Google Scholar

[30]

D. P. Foster and R. V. Vohra, Calibration: Respice, adspice, prospice,, Advances in Economics and Econometrics, 1 (2013), 423.  doi: 10.1017/CBO9781139060011.014.  Google Scholar

[31]

D. Fudenberg and D. M. Kreps, Learning mixed equilibria,, Games Econom. Behav., 5 (1993), 320.  doi: 10.1006/game.1993.1021.  Google Scholar

[32]

D. Fudenberg and D. K. Levine, Conditional universal consistency,, Games Econom. Behav., 29 (1999), 104.  doi: 10.1006/game.1998.0705.  Google Scholar

[33]

D. Fudenberg and D. K. Levine, An easier way to calibrate,, Games Econom. Behav., 29 (1999), 131.  doi: 10.1006/game.1999.0726.  Google Scholar

[34]

F. Gul, D. Pearce and E. Stachetti, A bound on the proportion of pure strategy equilibria in generic games,, Math. Oper. Res., 18 (1993), 548.  doi: 10.1287/moor.18.3.548.  Google Scholar

[35]

P. Hall and C. C. Heyde, Martingale Limit Theory and its Application,, Academic Press Inc., (1980).   Google Scholar

[36]

J. Hannan, Approximation to bayes risk in repeated play,, in Contributions to the Theory of Games, (1957), 97.   Google Scholar

[37]

S. Hart and A. Mas-Colell, A simple adaptive procedure leading to correlated equilibrium,, Econometrica, 68 (2000), 1127.  doi: 10.1111/1468-0262.00153.  Google Scholar

[38]

S. Hart and A. Mas-Colell, A general class of adaptive strategies,, J. Econom. Theory, 98 (2001), 26.  doi: 10.1006/jeth.2000.2746.  Google Scholar

[39]

S. Hart and A. Mas-Colell, Regret-based continuous-time dynamics,, Games Econom. Behav., 45 (2003), 375.  doi: 10.1016/S0899-8256(03)00178-7.  Google Scholar

[40]

E. Hazan and S. M. Kakade, (weak) calibration is computationaly hard,, J. Mach. Learn. Res.: Workshop Conf. Proc., 23 (2012), 1.   Google Scholar

[41]

J. Hofbauer and W. H. Sandholm, On the global convergence of stochastic fictitious play,, Econometrica, 70 (2002), 2265.  doi: 10.1111/1468-0262.00376.  Google Scholar

[42]

J. Hofbauer, S. Sorin and Y. Viossat, Time average replicator and best-reply dynamics,, Math. Oper. Res., 34 (2009), 263.  doi: 10.1287/moor.1080.0359.  Google Scholar

[43]

S. M. Kakade and D. P. Foster, Deterministic calibration and Nash equilibrium,, in Learning theory, (2004), 33.  doi: 10.1007/978-3-540-27819-1_3.  Google Scholar

[44]

O. Kallenberg and R. Sztencel, Some dimension-free features of vector-valued martingales,, Probability Theory and Related Fields, 88 (1991), 215.  doi: 10.1007/BF01212560.  Google Scholar

[45]

E. Kohlberg, Optimal strategies in repeated games with incomplete information,, Internat. J. Game Theory, 4 (1975), 7.  doi: 10.1007/BF01766399.  Google Scholar

[46]

J. Kwon, Hilbert Distance, Bounded Convex Functions, and Application to the Exponential Weight Algorithm,, Master's thesis, (2012).   Google Scholar

[47]

E. Lehrer, Any inspection is manipulable,, Econometrica, 69 (2001), 1333.  doi: 10.1111/1468-0262.00244.  Google Scholar

[48]

E. Lehrer, Approachability in infinite dimensional spaces,, Internat. J. Game Theory, 31 (2002), 253.  doi: 10.1007/s001820200115.  Google Scholar

[49]

E. Lehrer, A wide range no-regret theorem,, Games Econom. Behav., 42 (2003), 101.  doi: 10.1016/S0899-8256(03)00032-0.  Google Scholar

[50]

E. Lehrer and E. Solan, Excludability and bounded computational capacity,, Math. Oper. Res., 31 (2006), 637.  doi: 10.1287/moor.1060.0211.  Google Scholar

[51]

E. Lehrer and E. Solan, Learning to play partially-specified equilibrium,, Manuscript., ().   Google Scholar

[52]

E. Lehrer and E. Solan, Approachability with bounded memory,, Games Econom. Behav., 66 (2009), 995.  doi: 10.1016/j.geb.2007.07.011.  Google Scholar

[53]

E. Lehrer and S. Sorin, Minmax via differential inclusion,, J. Conv. Analysis, 14 (2007), 271.   Google Scholar

[54]

N. Littlestone and M. Warmuth, The weighted majority algorithm,, Information and Computation, 108 (1994), 212.  doi: 10.1006/inco.1994.1009.  Google Scholar

[55]

R. D. Luce and H. Raiffa, Games and Decisions: Introduction and Critical Survey,, John Wiley & Sons Inc., (1957).   Google Scholar

[56]

S. Mannor and N. Shimkin, Regret minimization in repeated matrix games with variable stage duration,, Games Econom. Behav., 63 (2008), 227.  doi: 10.1016/j.geb.2007.07.006.  Google Scholar

[57]

S. Mannor and G. Stoltz, A geometric proof of calibration,, Math. Oper. Res., 35 (2010), 721.  doi: 10.1287/moor.1100.0465.  Google Scholar

[58]

S. Mannor, G. Stoltz and V. Perchet, Robust approachability and regret minimization in games with partial monitoring,, J. Mach. Learn. Res.: Workshop Conf. Proc., 19 (2011), 515.   Google Scholar

[59]

S. Mannor, G. Stoltz and V. Perchet, Set-valued approachability, with applications to regret minimization in games with partial monitoring,, Manuscript., ().   Google Scholar

[60]

S. Mannor and J. N. Tsitsiklis, Approachability in repeated games: Computational aspects and a Stackelberg variant,, Games Econom. Behav., 66 (2009), 315.  doi: 10.1016/j.geb.2008.03.008.  Google Scholar

[61]

D. McFadden, Conditional logit analysis of qualitative choice behavior,, Frontiers in econometrics, (1974), 105.   Google Scholar

[62]

J.-F. Mertens, S. Sorin and S. Zamir, Repeated games,, CORE discussion paper, (1994), 9420.  doi: 10.1057/9780230226203.3424.  Google Scholar

[63]

J. Neveu, Bases Mathématiques du Calcul des Probabilités,, Masson et Cie, (1970).   Google Scholar

[64]

J. Neveu, Martingales à Temps Discret,, Masson et Cie, (1972).   Google Scholar

[65]

D. Oakes, Self-calibrating priors do not exist,, J. Amer. Statist. Assoc., 80 (1985), 339.  doi: 10.1080/01621459.1985.10478117.  Google Scholar

[66]

W. Olszewski, Calibration and expert testing,, in Handbook of Game Theory (eds. P. Young and S. Zamir), ().   Google Scholar

[67]

V. Perchet, Calibration and internal no-regret with random signals,, Algorithmic learning theory, (5809), 68.  doi: 10.1007/978-3-642-04414-4_10.  Google Scholar

[68]

V. Perchet, Approchabilité, Calibration et Regret dans les Jeux à Observations Partielles (in French),, PhD thesis, (2010).   Google Scholar

[69]

V. Perchet, Approachability of convex sets in games with partial monitoring,, J. Optim. Theory Appl., 149 (2011), 665.  doi: 10.1007/s10957-011-9797-3.  Google Scholar

[70]

V. Perchet, No-regret with partial monitoring: Calibration-based optimal algorithms,, J. Mach. Learn. Res., 12 (2011), 1893.   Google Scholar

[71]

V. Perchet, Exponential weights approachability, applications to regret minimization and calibration,, Manuscript., ().   Google Scholar

[72]

V. Perchet and M. Quincampoix, Purely informative game: Application to approachability with partial monitoring,, Manuscript., ().   Google Scholar

[73]

A. Rakhlin, Lecture notes on online learning,, Manuscript., ().   Google Scholar

[74]

A. Rakhlin, K. Sridharan and A. Tewari, Online Learning: Random Averages, Combinatorial Parameters, and Learnability,, in Neural Information Processing Systems, (2010).   Google Scholar

[75]

A. Rakhlin, K. Sridharan and A. Tewari, Online learning: Beyond regret,, J. Mach. Learn. Res.: Workshop Conf. Proc., 19 (2011), 559.   Google Scholar

[76]

W. Rudin, Real and Complex Analysis,, McGraw-Hill Series in Higher Mathematics, (1974).   Google Scholar

[77]

A. Sandroni, R. Smorodinsky and R. V. Vohra, Calibration with many checking rules,, Math. Oper. Res., 28 (2003), 141.  doi: 10.1287/moor.28.1.141.14264.  Google Scholar

[78]

E. Seneta, Nonnegative Matrices and Markov Chains,, 2nd edition, (1981).   Google Scholar

[79]

S. Sorin, A First Course on Zero-Sum Repeated Games,, Springer-Verlag, (2002).   Google Scholar

[80]

S. Sorin, Lectures on Dynamics in Games,, Unpublished Lecture Notes, (2008).   Google Scholar

[81]

S. Sorin, Exponential weight algorithm in continuous time,, Math. Program., 116 (2009), 513.  doi: 10.1007/s10107-007-0111-y.  Google Scholar

[82]

X. Spinat, A necessary and sufficient condition for approachability,, Math. Oper. Res., 27 (2002), 31.  doi: 10.1287/moor.27.1.31.333.  Google Scholar

[83]

G. Stoltz, Incomplete Information and Internal Regret in Prediction of Individual Sequences,, PhD thesis, (2005).   Google Scholar

[84]

G. Stoltz and G. Lugosi, Internal regret in on-line portfolio selection,, Mach. Learn., 59 (2005), 125.  doi: 10.1007/s10994-005-0465-4.  Google Scholar

[85]

G. Stoltz and G. Lugosi, Learning correlated equilibria in games with compact sets of strategies,, Games Econom. Behav., 59 (2007), 187.  doi: 10.1016/j.geb.2006.04.007.  Google Scholar

[86]

N. Vieille, Weak approachability,, Math. Oper. Res., 17 (1992), 781.  doi: 10.1287/moor.17.4.781.  Google Scholar

[87]

Y. Viossat and A. Zapechelnyuk, No-regret dynamics and fictitious play,, J. Econom. Theory, 148 (2013), 825.  doi: 10.1016/j.jet.2012.07.003.  Google Scholar

[88]

V. Vovk, Aggregating strategies,, in Proceedings of the 3rd Annual Workshop on Computational Learning Theory, (1990), 372.   Google Scholar

[89]

V. Vovk, I. Nouretdinov, A. Takemura and G. Shafer, Defensive forecasting for linear protocols,, in Algorithmic Learning Theory, (2005), 459.  doi: 10.1007/11564089_35.  Google Scholar

[90]

D. Walkup and R. J.-B. Wets, A lipschitzian characterization of convex polyhedra,, Proceedings of the American Mathematical Society, 23 (1969), 167.  doi: 10.1090/S0002-9939-1969-0246200-8.  Google Scholar

[91]

A. Zapechelnyuk, Better-reply dynamics with bounded recall,, Math. Oper. Res., 33 (2008), 869.  doi: 10.1287/moor.1080.0323.  Google Scholar

[92]

M. Zinkevich, Online convex programming and generalized infinitesimal gradient ascent,, in Proceedings of the Twentieth International Conference on Machine Learning (ICML), (2003).   Google Scholar

show all references

References:
[1]

J. Abernethy, P. Bartlett and E. Hazan, Blackwell approachability and low-regret learning are equivalent,, J. Mach. Learn. Res.: Workshop Conf. Proc., 19 (2011), 27.   Google Scholar

[2]

S. As Soulaimani, M. Quincampoix and S. Sorin, Repeated games and qualitative differential games: Approachability and comparison of strategies,, SIAM J. Control Optim., 48 (2009), 2461.  doi: 10.1137/090749098.  Google Scholar

[3]

P. Auer, N. Cesa-Bianchi and C. Gentile, Adaptive and self-confident on-line learning algorithms,, J. Comput. System Sci., 64 (2002), 48.  doi: 10.1006/jcss.2001.1795.  Google Scholar

[4]

R. J. Aumann, Subjectivity and correlation in randomized strategies,, J. Math. Econom., 1 (1974), 67.  doi: 10.1016/0304-4068(74)90037-8.  Google Scholar

[5]

R. J. Aumann and M. B. Maschler, Repeated Games with Incomplete Information,, MIT Press, (1995).   Google Scholar

[6]

M. Benaïm and M. Faure, Consistency of vanishingly smooth fictitious play,, Math. Oper. Res., 38 (2013), 437.  doi: 10.1287/moor.1120.0568.  Google Scholar

[7]

M. Benaïm, J. Hofbauer and S. Sorin, Stochastic approximations and differential inclusions. II. Applications,, Math. Oper. Res., 31 (2006), 673.  doi: 10.1287/moor.1060.0213.  Google Scholar

[8]

A. Bernstein, S. Mannor and N. Shimkin, Opportunistic strategies for generalized no-regret problems,, J. Mach. Learn. Res.: Workshop Conf. Proc., 30 (2013), 158.   Google Scholar

[9]

A. Bernstein and N. Shimkin, Response-based approachability and its application to generalized no-regret algorithms,, Manuscript., ().   Google Scholar

[10]

L. J. Billera and B. Sturmfels, Fiber polytopes,, The Annals of Mathematics, 135 (1992), 527.  doi: 10.2307/2946575.  Google Scholar

[11]

D. Blackwell, An analog of the minimax theorem for vector payoffs,, Pacific J. Math., 6 (1956), 1.  doi: 10.2140/pjm.1956.6.1.  Google Scholar

[12]

D. Blackwell, Controlled random walks,, in Proceedings of the International Congress of Mathematicians, (1954), 336.   Google Scholar

[13]

D. Blackwell and M. A. Girshick, Theory of Games and Statistical Decisions,, John Wiley and Sons, (1954).   Google Scholar

[14]

A. Blum and Y. Mansour, From external to internal regret,, in Learning theory, (2005), 621.  doi: 10.1007/11503415_42.  Google Scholar

[15]

S. Bubeck, Introduction to online optimization,, Manuscript., ().   Google Scholar

[16]

N. Cesa-Bianchi and G. Lugosi, Potential-based algorithms in on-line prediction and game theory,, Machine Learning, 51 (2003), 239.   Google Scholar

[17]

N. Cesa-Bianchi and G. Lugosi, Prediction, Learning, and Games,, Cambridge University Press, (2006).  doi: 10.1017/CBO9780511546921.  Google Scholar

[18]

X. Chen and H. White, Laws of large numbers for Hilbert space-valued mixingales with applications,, Econometric Theory, 12 (1996), 284.  doi: 10.1017/S0266466600006599.  Google Scholar

[19]

A. P. Dawid, The well-calibrated Bayesian,, J. Amer. Statist. Assoc., 77 (1982), 605.  doi: 10.1080/01621459.1982.10477856.  Google Scholar

[20]

A. P. Dawid, Self-calibrating priors do not exist: Comment,, J. Amer. Statist. Assoc., 80 (1985), 339.  doi: 10.1080/01621459.1985.10478117.  Google Scholar

[21]

L. Evans and P. E. Souganidis, Differential games and representation formulas for solutions of Hamilton-Jacobi equations,, Indiana Univ. Math. J., 33 (1984), 773.  doi: 10.1512/iumj.1984.33.33040.  Google Scholar

[22]

K. Fan, Minimax theorems,, Proc. Nat. Acad. Sci. U. S. A., 39 (1953), 42.  doi: 10.1073/pnas.39.1.42.  Google Scholar

[23]

K. Fan, A minimax inequality and applications,, in Inequalities, (1972), 103.   Google Scholar

[24]

W. Feller, An Introduction to Probability Theory and its Applications. Vol. I,, Third edition, (1968).   Google Scholar

[25]

D. P. Foster, A proof of calibration via blackwell's approachability theorem,, Games and Economic Behavior, 29 (1999), 73.  doi: 10.1006/game.1999.0719.  Google Scholar

[26]

D. P. Foster, A. Rakhlin, K. Sridharan and A. Tewari, Complexity-based approach to calibration with checking rules,, J. Mach. Learn. Res.: Workshop Conf. Proc., 19 (2011), 293.   Google Scholar

[27]

D. P. Foster and R. V. Vohra, Calibrated learning and correlated equilibrium,, Games Econom. Behav., 21 (1997), 40.  doi: 10.1006/game.1997.0595.  Google Scholar

[28]

D. P. Foster and R. V. Vohra, Asymptotic calibration,, Biometrika, 85 (1998), 379.  doi: 10.1093/biomet/85.2.379.  Google Scholar

[29]

D. P. Foster and R. V. Vohra, Regret in the on-line decision problem,, Games Econom. Behav., 29 (1999), 7.  doi: 10.1006/game.1999.0740.  Google Scholar

[30]

D. P. Foster and R. V. Vohra, Calibration: Respice, adspice, prospice,, Advances in Economics and Econometrics, 1 (2013), 423.  doi: 10.1017/CBO9781139060011.014.  Google Scholar

[31]

D. Fudenberg and D. M. Kreps, Learning mixed equilibria,, Games Econom. Behav., 5 (1993), 320.  doi: 10.1006/game.1993.1021.  Google Scholar

[32]

D. Fudenberg and D. K. Levine, Conditional universal consistency,, Games Econom. Behav., 29 (1999), 104.  doi: 10.1006/game.1998.0705.  Google Scholar

[33]

D. Fudenberg and D. K. Levine, An easier way to calibrate,, Games Econom. Behav., 29 (1999), 131.  doi: 10.1006/game.1999.0726.  Google Scholar

[34]

F. Gul, D. Pearce and E. Stachetti, A bound on the proportion of pure strategy equilibria in generic games,, Math. Oper. Res., 18 (1993), 548.  doi: 10.1287/moor.18.3.548.  Google Scholar

[35]

P. Hall and C. C. Heyde, Martingale Limit Theory and its Application,, Academic Press Inc., (1980).   Google Scholar

[36]

J. Hannan, Approximation to bayes risk in repeated play,, in Contributions to the Theory of Games, (1957), 97.   Google Scholar

[37]

S. Hart and A. Mas-Colell, A simple adaptive procedure leading to correlated equilibrium,, Econometrica, 68 (2000), 1127.  doi: 10.1111/1468-0262.00153.  Google Scholar

[38]

S. Hart and A. Mas-Colell, A general class of adaptive strategies,, J. Econom. Theory, 98 (2001), 26.  doi: 10.1006/jeth.2000.2746.  Google Scholar

[39]

S. Hart and A. Mas-Colell, Regret-based continuous-time dynamics,, Games Econom. Behav., 45 (2003), 375.  doi: 10.1016/S0899-8256(03)00178-7.  Google Scholar

[40]

E. Hazan and S. M. Kakade, (weak) calibration is computationaly hard,, J. Mach. Learn. Res.: Workshop Conf. Proc., 23 (2012), 1.   Google Scholar

[41]

J. Hofbauer and W. H. Sandholm, On the global convergence of stochastic fictitious play,, Econometrica, 70 (2002), 2265.  doi: 10.1111/1468-0262.00376.  Google Scholar

[42]

J. Hofbauer, S. Sorin and Y. Viossat, Time average replicator and best-reply dynamics,, Math. Oper. Res., 34 (2009), 263.  doi: 10.1287/moor.1080.0359.  Google Scholar

[43]

S. M. Kakade and D. P. Foster, Deterministic calibration and Nash equilibrium,, in Learning theory, (2004), 33.  doi: 10.1007/978-3-540-27819-1_3.  Google Scholar

[44]

O. Kallenberg and R. Sztencel, Some dimension-free features of vector-valued martingales,, Probability Theory and Related Fields, 88 (1991), 215.  doi: 10.1007/BF01212560.  Google Scholar

[45]

E. Kohlberg, Optimal strategies in repeated games with incomplete information,, Internat. J. Game Theory, 4 (1975), 7.  doi: 10.1007/BF01766399.  Google Scholar

[46]

J. Kwon, Hilbert Distance, Bounded Convex Functions, and Application to the Exponential Weight Algorithm,, Master's thesis, (2012).   Google Scholar

[47]

E. Lehrer, Any inspection is manipulable,, Econometrica, 69 (2001), 1333.  doi: 10.1111/1468-0262.00244.  Google Scholar

[48]

E. Lehrer, Approachability in infinite dimensional spaces,, Internat. J. Game Theory, 31 (2002), 253.  doi: 10.1007/s001820200115.  Google Scholar

[49]

E. Lehrer, A wide range no-regret theorem,, Games Econom. Behav., 42 (2003), 101.  doi: 10.1016/S0899-8256(03)00032-0.  Google Scholar

[50]

E. Lehrer and E. Solan, Excludability and bounded computational capacity,, Math. Oper. Res., 31 (2006), 637.  doi: 10.1287/moor.1060.0211.  Google Scholar

[51]

E. Lehrer and E. Solan, Learning to play partially-specified equilibrium,, Manuscript., ().   Google Scholar

[52]

E. Lehrer and E. Solan, Approachability with bounded memory,, Games Econom. Behav., 66 (2009), 995.  doi: 10.1016/j.geb.2007.07.011.  Google Scholar

[53]

E. Lehrer and S. Sorin, Minmax via differential inclusion,, J. Conv. Analysis, 14 (2007), 271.   Google Scholar

[54]

N. Littlestone and M. Warmuth, The weighted majority algorithm,, Information and Computation, 108 (1994), 212.  doi: 10.1006/inco.1994.1009.  Google Scholar

[55]

R. D. Luce and H. Raiffa, Games and Decisions: Introduction and Critical Survey,, John Wiley & Sons Inc., (1957).   Google Scholar

[56]

S. Mannor and N. Shimkin, Regret minimization in repeated matrix games with variable stage duration,, Games Econom. Behav., 63 (2008), 227.  doi: 10.1016/j.geb.2007.07.006.  Google Scholar

[57]

S. Mannor and G. Stoltz, A geometric proof of calibration,, Math. Oper. Res., 35 (2010), 721.  doi: 10.1287/moor.1100.0465.  Google Scholar

[58]

S. Mannor, G. Stoltz and V. Perchet, Robust approachability and regret minimization in games with partial monitoring,, J. Mach. Learn. Res.: Workshop Conf. Proc., 19 (2011), 515.   Google Scholar

[59]

S. Mannor, G. Stoltz and V. Perchet, Set-valued approachability, with applications to regret minimization in games with partial monitoring,, Manuscript., ().   Google Scholar

[60]

S. Mannor and J. N. Tsitsiklis, Approachability in repeated games: Computational aspects and a Stackelberg variant,, Games Econom. Behav., 66 (2009), 315.  doi: 10.1016/j.geb.2008.03.008.  Google Scholar

[61]

D. McFadden, Conditional logit analysis of qualitative choice behavior,, Frontiers in econometrics, (1974), 105.   Google Scholar

[62]

J.-F. Mertens, S. Sorin and S. Zamir, Repeated games,, CORE discussion paper, (1994), 9420.  doi: 10.1057/9780230226203.3424.  Google Scholar

[63]

J. Neveu, Bases Mathématiques du Calcul des Probabilités,, Masson et Cie, (1970).   Google Scholar

[64]

J. Neveu, Martingales à Temps Discret,, Masson et Cie, (1972).   Google Scholar

[65]

D. Oakes, Self-calibrating priors do not exist,, J. Amer. Statist. Assoc., 80 (1985), 339.  doi: 10.1080/01621459.1985.10478117.  Google Scholar

[66]

W. Olszewski, Calibration and expert testing,, in Handbook of Game Theory (eds. P. Young and S. Zamir), ().   Google Scholar

[67]

V. Perchet, Calibration and internal no-regret with random signals,, Algorithmic learning theory, (5809), 68.  doi: 10.1007/978-3-642-04414-4_10.  Google Scholar

[68]

V. Perchet, Approchabilité, Calibration et Regret dans les Jeux à Observations Partielles (in French),, PhD thesis, (2010).   Google Scholar

[69]

V. Perchet, Approachability of convex sets in games with partial monitoring,, J. Optim. Theory Appl., 149 (2011), 665.  doi: 10.1007/s10957-011-9797-3.  Google Scholar

[70]

V. Perchet, No-regret with partial monitoring: Calibration-based optimal algorithms,, J. Mach. Learn. Res., 12 (2011), 1893.   Google Scholar

[71]

V. Perchet, Exponential weights approachability, applications to regret minimization and calibration,, Manuscript., ().   Google Scholar

[72]

V. Perchet and M. Quincampoix, Purely informative game: Application to approachability with partial monitoring,, Manuscript., ().   Google Scholar

[73]

A. Rakhlin, Lecture notes on online learning,, Manuscript., ().   Google Scholar

[74]

A. Rakhlin, K. Sridharan and A. Tewari, Online Learning: Random Averages, Combinatorial Parameters, and Learnability,, in Neural Information Processing Systems, (2010).   Google Scholar

[75]

A. Rakhlin, K. Sridharan and A. Tewari, Online learning: Beyond regret,, J. Mach. Learn. Res.: Workshop Conf. Proc., 19 (2011), 559.   Google Scholar

[76]

W. Rudin, Real and Complex Analysis,, McGraw-Hill Series in Higher Mathematics, (1974).   Google Scholar

[77]

A. Sandroni, R. Smorodinsky and R. V. Vohra, Calibration with many checking rules,, Math. Oper. Res., 28 (2003), 141.  doi: 10.1287/moor.28.1.141.14264.  Google Scholar

[78]

E. Seneta, Nonnegative Matrices and Markov Chains,, 2nd edition, (1981).   Google Scholar

[79]

S. Sorin, A First Course on Zero-Sum Repeated Games,, Springer-Verlag, (2002).   Google Scholar

[80]

S. Sorin, Lectures on Dynamics in Games,, Unpublished Lecture Notes, (2008).   Google Scholar

[81]

S. Sorin, Exponential weight algorithm in continuous time,, Math. Program., 116 (2009), 513.  doi: 10.1007/s10107-007-0111-y.  Google Scholar

[82]

X. Spinat, A necessary and sufficient condition for approachability,, Math. Oper. Res., 27 (2002), 31.  doi: 10.1287/moor.27.1.31.333.  Google Scholar

[83]

G. Stoltz, Incomplete Information and Internal Regret in Prediction of Individual Sequences,, PhD thesis, (2005).   Google Scholar

[84]

G. Stoltz and G. Lugosi, Internal regret in on-line portfolio selection,, Mach. Learn., 59 (2005), 125.  doi: 10.1007/s10994-005-0465-4.  Google Scholar

[85]

G. Stoltz and G. Lugosi, Learning correlated equilibria in games with compact sets of strategies,, Games Econom. Behav., 59 (2007), 187.  doi: 10.1016/j.geb.2006.04.007.  Google Scholar

[86]

N. Vieille, Weak approachability,, Math. Oper. Res., 17 (1992), 781.  doi: 10.1287/moor.17.4.781.  Google Scholar

[87]

Y. Viossat and A. Zapechelnyuk, No-regret dynamics and fictitious play,, J. Econom. Theory, 148 (2013), 825.  doi: 10.1016/j.jet.2012.07.003.  Google Scholar

[88]

V. Vovk, Aggregating strategies,, in Proceedings of the 3rd Annual Workshop on Computational Learning Theory, (1990), 372.   Google Scholar

[89]

V. Vovk, I. Nouretdinov, A. Takemura and G. Shafer, Defensive forecasting for linear protocols,, in Algorithmic Learning Theory, (2005), 459.  doi: 10.1007/11564089_35.  Google Scholar

[90]

D. Walkup and R. J.-B. Wets, A lipschitzian characterization of convex polyhedra,, Proceedings of the American Mathematical Society, 23 (1969), 167.  doi: 10.1090/S0002-9939-1969-0246200-8.  Google Scholar

[91]

A. Zapechelnyuk, Better-reply dynamics with bounded recall,, Math. Oper. Res., 33 (2008), 869.  doi: 10.1287/moor.1080.0323.  Google Scholar

[92]

M. Zinkevich, Online convex programming and generalized infinitesimal gradient ascent,, in Proceedings of the Twentieth International Conference on Machine Learning (ICML), (2003).   Google Scholar

[1]

Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020074
[2]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

 Impact Factor: 

Tools

Metrics

  • PDF downloads (74)
  • HTML views (0)
  • Cited by (9)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences