Internal regret with partial monitoring: calibration-based optimal algorithms

MaRDI QIDQ5396662zbMATH OpenFDO

Authors Vianney Perchet

Publication date 3 February 2014

Full work available at URL https://arxiv.org/abs/1102.4442, http://www.jmlr.org/papers/v12/perchet11a.html

zbMATH Keywords

calibrationon-line learningpartial monitoringregretrepeated gamesVoronoi and Laguerre diagrams

Mathematics Subject Classification ID

Computational learning theory (68Q32) Multistage and repeated games (91A20) Rationality and learning in game theory (91A26)

Abstract: 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 Voronoi 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.

Recommendations

• Calibration and internal no-regret with random signals
• Partial monitoring -- classification, regret bounds, and algorithms
• From external to internal regret
• Learning Theory
• A general internal regret-free strategy

Cited in

(10)

• Approachability of convex sets in generalized quitting games
• A differential game on Wasserstein space. Application to weak approachability with partial monitoring
• Approachability, regret and calibration: implications and equivalences
• A general internal regret-free strategy
• On a unified framework for approachability with full or partial monitoring
• Calibration and internal no-regret with random signals
• A primal condition for approachability with partial monitoring
• Partial monitoring -- classification, regret bounds, and algorithms
• Cleaning up the neighborhood: a full classification for adversarial partial monitoring
• Approachability with delayed information

This page was built for publication: Internal regret with partial monitoring: calibration-based optimal algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5396662)