Approachability, regret and calibration: implications and equivalences
From MaRDI portal
Publication:2438352
DOI10.3934/JDG.2014.1.181zbMATH Open1286.91028arXiv1301.2663OpenAlexW2320006964MaRDI QIDQ2438352FDOQ2438352
Authors: Vianney Perchet 
Publication date: 11 March 2014
Published in: Journal of Dynamics and Games (Search for Journal in Brave)
Abstract: Blackwell approachability, regret minimization and calibration are three criteria evaluating a strategy (or an algorithm) in different sequential decision problems, or repeated games between a player and Nature. Although they have at first sight nothing in common, links between have been discovered: both consistent and calibrated strategies can be constructed by following, in some auxiliary game, an approachability strategy. We gathered famous or recent results and provide new ones in order to develop and generalize Blackwell's elegant theory. The final goal is to show how it 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.
Full work available at URL: https://arxiv.org/abs/1301.2663
Recommendations
- Response-based approachability with applications to generalized no-regret problems
- Opportunistic approachability and generalized no-regret problems
- Exponential weight approachability, applications to calibration and regret minimization
- scientific article; zbMATH DE number 7626715
- Internal regret with partial monitoring: calibration-based optimal algorithms
- A closer look at adaptive regret
- A closer look at adaptive regret
- Extracting certainty from uncertainty: regret bounded by variation in costs
- On relation between expected regret and conditional value-at-risk
Online algorithms; streaming algorithms (68W27) 2-person games (91A05) Multistage and repeated games (91A20) Dynamic games (91A25) Rationality and learning in game theory (91A26)
Cites Work
- The Well-Calibrated Bayesian
- Prediction, Learning, and Games
- Learning Theory
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Learning mixed equilibria
- Title not available (Why is that?)
- Title not available (Why is that?)
- Subjectivity and correlation in randomized strategies
- The weighted majority algorithm
- Calibrated learning and correlated equilibrium
- Repeated games with incomplete information. With the collaboration of Richard E. Stearns
- Time Average Replicator and Best-Reply Dynamics
- Title not available (Why is that?)
- Title not available (Why is that?)
- Repeated games and qualitative differential games: approachability and comparison of strategies
- A Simple Adaptive Procedure Leading to Correlated Equilibrium
- Minimax Theorems
- Title not available (Why is that?)
- A general class of adaptive strategies
- A first course on zero-sum repeated games
- An analog of the minimax theorem for vector payoffs
- Exponential weight algorithm in continuous time
- Non-negative matrices and Markov chains. 2nd ed
- Title not available (Why is that?)
- Title not available (Why is that?)
- A proof of calibration via Blackwell's approachability theorem.
- Asymptotic calibration
- On the Global Convergence of Stochastic Fictitious Play
- Regret in the on-line decision problem
- Conditional universal consistency.
- Calibration and internal no-regret with random signals
- Internal regret with partial monitoring: calibration-based optimal algorithms
- Internal regret in on-line portfolio selection
- Fiber polytopes
- Stochastic Approximations and Differential Inclusions, Part II: Applications
- Approachability in repeated games: Computational aspects and a Stackelberg variant
- Convex optimization: algorithms and complexity
- A Lipschitzian Characterization of Convex Polyhedra
- Approachability in infinite dimensional spaces
- Regret-based continuous-time dynamics.
- A wide range no-regret theorem
- Approachability with bounded memory
- Weak Approachability
- Title not available (Why is that?)
- Excludability and Bounded Computational Capacity
- A Necessary and Sufficient Condition for Approachability
- Some dimension-free features of vector-valued martingales
- Learning correlated equilibria in games with compact sets of strategies
- Better-reply dynamics with bounded recall
- Adaptive and self-confident on-line learning algorithms
- Optimal strategies in repeated games with incomplete information
- Approachability of convex sets in games with partial monitoring
- Learning Theory
- Consistency of vanishingly smooth fictitious play
- Potential-based algorithms in on-line prediction and game theory
- Calibration with Many Checking Rules
- Algorithmic Learning Theory
- An easier way to calibrate.
- Any Inspection is Manipulable
- Self-Calibrating Priors Do Not Exist
- A Bound on the Proportion of Pure Strategy Equilibria in Generic Games
- No-regret dynamics and fictitious play
- Exponential weight approachability, applications to calibration and regret minimization
- Regret minimization in repeated matrix games with variable stage duration
- A geometric proof of calibration
- On martingale extensions of Vapnik-Chervonenkis theory with applications to online learning
- Response-based approachability with applications to generalized no-regret problems
Cited In (18)
- Replicator dynamics: old and new
- A differential game on Wasserstein space. Application to weak approachability with partial monitoring
- Playing against no-regret players
- A general internal regret-free strategy
- Statistical calibration: a simplification of Foster's proof
- Approachability with constraints
- Exponential weight approachability, applications to calibration and regret minimization
- Constrained no-regret learning
- Approachability of convex sets in generalized quitting games
- Approachability with delayed information
- Title not available (Why is that?)
- Calibration and internal no-regret with random signals
- Smale strategies for network prisoner's dilemma games
- A geometric proof of calibration
- Approachability in Stackelberg stochastic games with vector costs
- Opportunistic approachability and generalized no-regret problems
- Response-based approachability with applications to generalized no-regret problems
- No-regret algorithms in on-line learning, games and convex optimization
This page was built for publication: Approachability, regret and calibration: implications and equivalences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2438352)
