Approachability, regret and calibration: implications and equivalences
From MaRDI portal
Publication:2438352
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.
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
Cites work
- scientific article; zbMATH DE number 3122013 (Why is no real title available?)
- scientific article; zbMATH DE number 3128728 (Why is no real title available?)
- scientific article; zbMATH DE number 3137856 (Why is no real title available?)
- scientific article; zbMATH DE number 5604590 (Why is no real title available?)
- scientific article; zbMATH DE number 3723610 (Why is no real title available?)
- scientific article; zbMATH DE number 3472891 (Why is no real title available?)
- scientific article; zbMATH DE number 3437452 (Why is no real title available?)
- scientific article; zbMATH DE number 5176447 (Why is no real title available?)
- scientific article; zbMATH DE number 3249395 (Why is no real title available?)
- scientific article; zbMATH DE number 3323562 (Why is no real title available?)
- scientific article; zbMATH DE number 3090557 (Why is no real title available?)
- A Bound on the Proportion of Pure Strategy Equilibria in Generic Games
- A Lipschitzian Characterization of Convex Polyhedra
- A Necessary and Sufficient Condition for Approachability
- A Simple Adaptive Procedure Leading to Correlated Equilibrium
- A first course on zero-sum repeated games
- A general class of adaptive strategies
- A geometric proof of calibration
- A proof of calibration via Blackwell's approachability theorem.
- A wide range no-regret theorem
- Adaptive and self-confident on-line learning algorithms
- Algorithmic Learning Theory
- An analog of the minimax theorem for vector payoffs
- An easier way to calibrate.
- Any Inspection is Manipulable
- Approachability in infinite dimensional spaces
- Approachability in repeated games: Computational aspects and a Stackelberg variant
- Approachability of convex sets in games with partial monitoring
- Approachability with bounded memory
- Asymptotic calibration
- Better-reply dynamics with bounded recall
- Calibrated learning and correlated equilibrium
- Calibration and internal no-regret with random signals
- Calibration with Many Checking Rules
- Conditional universal consistency.
- Consistency of vanishingly smooth fictitious play
- Convex optimization: algorithms and complexity
- Excludability and Bounded Computational Capacity
- Exponential weight algorithm in continuous time
- Exponential weight approachability, applications to calibration and regret minimization
- Fiber polytopes
- Internal regret in on-line portfolio selection
- Internal regret with partial monitoring: calibration-based optimal algorithms
- Learning Theory
- Learning Theory
- Learning correlated equilibria in games with compact sets of strategies
- Learning mixed equilibria
- Minimax Theorems
- No-regret dynamics and fictitious play
- Non-negative matrices and Markov chains. 2nd ed
- On martingale extensions of Vapnik-Chervonenkis theory with applications to online learning
- On the Global Convergence of Stochastic Fictitious Play
- Optimal strategies in repeated games with incomplete information
- Potential-based algorithms in on-line prediction and game theory
- Prediction, Learning, and Games
- Regret in the on-line decision problem
- Regret minimization in repeated matrix games with variable stage duration
- Regret-based continuous-time dynamics.
- Repeated games and qualitative differential games: approachability and comparison of strategies
- Repeated games with incomplete information. With the collaboration of Richard E. Stearns
- Response-based approachability with applications to generalized no-regret problems
- Self-Calibrating Priors Do Not Exist
- Some dimension-free features of vector-valued martingales
- Stochastic Approximations and Differential Inclusions, Part II: Applications
- Subjectivity and correlation in randomized strategies
- The Well-Calibrated Bayesian
- The weighted majority algorithm
- Time Average Replicator and Best-Reply Dynamics
- Weak Approachability
Cited in
(18)- Replicator dynamics: old and new
- A differential game on Wasserstein space. Application to weak approachability with partial monitoring
- A general internal regret-free strategy
- Playing against no-regret players
- 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
- scientific article; zbMATH DE number 7626715 (Why is no real title available?)
- 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)
