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
- A Bound on the Proportion of Pure Strategy Equilibria in Generic Games
- A first course on zero-sum repeated games
- A general class of adaptive strategies
- A geometric proof of calibration
- A Lipschitzian Characterization of Convex Polyhedra
- A Necessary and Sufficient Condition for Approachability
- A proof of calibration via Blackwell's approachability theorem.
- A Simple Adaptive Procedure Leading to Correlated Equilibrium
- 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
- 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?)
- Internal regret in on-line portfolio selection
- Internal regret with partial monitoring: calibration-based optimal algorithms
- Learning correlated equilibria in games with compact sets of strategies
- Learning mixed equilibria
- Learning Theory
- Learning Theory
- 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 weighted majority algorithm
- The Well-Calibrated Bayesian
- Time Average Replicator and Best-Reply Dynamics
- Weak Approachability
Cited in
(20)- Approachability of convex sets in generalized quitting games
- Approachability in Stackelberg stochastic games with vector costs
- Approachability with constraints
- Constrained no-regret learning
- A differential game on Wasserstein space. Application to weak approachability with partial monitoring
- Exponential weight approachability, applications to calibration and regret minimization
- A general internal regret-free strategy
- A geometric proof of calibration
- Calibration and internal no-regret with random signals
- scientific article; zbMATH DE number 1057578 (Why is no real title available?)
- scientific article; zbMATH DE number 7626715 (Why is no real title available?)
- 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
- Playing against no-regret players
- Robust correlated equilibrium: definition and computation
- Statistical calibration: a simplification of Foster's proof
- Replicator dynamics: old and new
- Approachability with delayed information
- Smale strategies for network prisoner's dilemma games
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)
