Research map / Bandits and online learning / Online convex optimization and games
Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoring
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes a simple anchored exploration-by-optimization (EXO) policy for finite-action adversarial linear partial monitoring and proves instance-dependent regret bounds of order sqrt(T) for locally observable games and T^{2/3} for globally observable games.
Problem
Adversarial (nonstochastic) linear partial monitoring with finite actions and infinite outcome spaces, where losses and observations are linear in features; prior regret bounds for EXO in this setting are opaque and the algorithm is hard to implement.
Approach
An efficiently implementable anchored EXO policy (exponential weights over Pareto-optimal actions with shifted loss estimators) whose regret is bounded via minimax theorem and game-dependent alignment constants (beta_loc, beta_glo, w*, u*) that are more interpretable than prior general bounds.
Key results
- Locally observable games: regret O(sqrt(alpha T log k)) via Lambda bound 12 L^2 beta_loc^2 d.
- Globally observable games: regret O((alpha T)^{2/3} (log k)^{1/3}) with Lambda bound scaling as 1/sqrt(eta).
- Full-information and strongly observable graphs recover O(sqrt(alpha(G) T log k)); bandits with ill-conditioned observers give (1/eps) sqrt(kT log k).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Anchored EXO in a locally observable game | Adversarial linear partial monitoring · Locally observable games | regret: \cO \brb{ \sqrt{\alpha T \log k}} | Helped |
| use Anchored EXO in a globally observable game | Adversarial linear partial monitoring · Globally observable games | regret: \cO \brb{ (\alpha T)^{2/3}(\log k)^{1/3}} | Helped |
| apply the locally observable bound to full information | Anchored EXO · Full information | regret: \cO(\sqrt{T \log k}) | Helped |
| apply the locally observable bound to strongly observable feedback graphs | Anchored EXO · Strongly observable feedback graphs | regret: \cO(\sqrt{\alpha(\cG)T\log k}) | Helped |
| apply the locally observable bound to linear bandits | Anchored EXO · Linear bandits | regret: \sqrt{dT\log(k)} | Helped |
| apply the locally observable bound to linear dueling bandits | Anchored EXO · Linear dueling bandits | regret: \sqrt{dT\log(k)} | Helped |
| reduce observer informativeness by using ill-conditioned observers with parameter ε | Anchored EXO · Bandits with ill-conditioned observers | regret: \nicefrac{1}{\varepsilon}\sqrt{k T\log k} | Hurt |
| apply the globally observable bound to weakly observable feedback graphs | Anchored EXO · Weakly observable feedback graphs | regret: \cO((\delta(\cG)\log k)^{1/3}T^{2/3}) | Helped |
| apply the globally observable bound to composite graph feedback | Anchored EXO · Composite graph feedback | regret: \cO((k \log k)^{1/3}(\beta_{2,\glo} T)^{2/3}) | Helped |
Limitations
- Restricted to full-dimensional loss spaces and finite actions
- Bounds for finite partial monitoring not tight since observability conditions do not match in general
- Some constants (e.g. B) chosen conservatively
Experimental setup
Metrics: regret bound order in T
Baselines: general EXO bound for linear partial monitoring stochastic linear partial monitoring algorithms
Builds on: exploration-by-optimization exponential weights linear bandits finite partial monitoring observability
Closest papers by meaning
- Randomized Confidence Bounds for Stochastic Partial Monitoring (ICML 2024 · similarity 0.89)
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.89)
- Linear Bandits with Partially Observable Features (ICML 2025 · similarity 0.88)
- Sparsity-Agnostic Linear Bandits with Adaptive Adversaries (NeurIPS 2024 · similarity 0.88)
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.88)
- Testing the Feasibility of Linear Programs with Bandit Feedback (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.