# Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoring

arXiv: https://arxiv.org/abs/2510.19158 · HTML: https://mlsanity.com/paper/2510.19158/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 58 references that are in the map.
- First posted on arXiv 22 Oct 2025.

## Builds on (most cited first, 24 of 24)

- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback](https://mlsanity.com/paper/1409.8428/) (2014)
- [An Information-Theoretic Approach to Minimax Regret in Partial Monitoring](https://mlsanity.com/paper/1902.00470/) (2019)
- [Information Directed Sampling for Linear Partial Monitoring](https://mlsanity.com/paper/2002.11182/) (2020)
- [Mirror Descent and the Information Ratio](https://mlsanity.com/paper/2009.12228/) (2020)
- [On the Complexity of Adversarial Decision Making](https://mlsanity.com/paper/2206.13063/) (2022)
- [Exploration by Optimisation in Partial Monitoring](https://mlsanity.com/paper/1907.05772/) (2019)
- [Best-of-Both-Worlds Algorithms for Partial Monitoring](https://mlsanity.com/paper/2207.14550/) (2022)
- [Cleaning up the neighborhood: A full classification for adversarial partial monitoring](https://mlsanity.com/paper/1805.09247/) (2018)
- [Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds](https://mlsanity.com/paper/2305.17301/) (2023)
- [Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini's Regret](https://mlsanity.com/paper/2202.10997/) (2022)
- [Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applications](https://mlsanity.com/paper/2302.03683/) (2023)
- [Regret Lower Bound and Optimal Algorithm in Finite Stochastic Partial Monitoring](https://mlsanity.com/paper/1509.09011/) (2015)
- [Tight Bounds for Bandit Combinatorial Optimization](https://mlsanity.com/paper/1702.07539/) (2017)
- [Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring](https://mlsanity.com/paper/2006.09668/) (2020)
- [Cheap Bandits](https://mlsanity.com/paper/1506.04782/) (2015)
- [Utility-based Dueling Bandits as a Partial Monitoring Game](https://mlsanity.com/paper/1507.02750/) (2015)
- [Phased Exploration with Greedy Exploitation in Stochastic Combinatorial Partial Monitoring Games](https://mlsanity.com/paper/1608.06403/) (2016)
- [Information Capacity Regret Bounds for Bandits with Mediator Feedback](https://mlsanity.com/paper/2402.10282/) (2024)
- [Randomized Confidence Bounds for Stochastic Partial Monitoring](https://mlsanity.com/paper/2402.05002/) (2024)
- [Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoring](https://mlsanity.com/paper/2402.08321/) (2024)
- [Neural Active Learning Meets the Partial Monitoring Framework](https://mlsanity.com/paper/2405.08921/) (2024)

## Built on by (most cited first, 1 of 1)

- [Efficient Logistic Regression with Mixture of Sigmoids](https://mlsanity.com/paper/2604.02920/) (2026)

## Abstract (arXiv)

In contrast to the classic formulation of partial monitoring, linear partial monitoring can model infinite outcome spaces, while imposing a linear structure on both the losses and the observations. This setting can be viewed as a generalization of linear bandits where loss and feedback are decoupled in a flexible manner. In this work, we address a nonstochastic (adversarial), finite-actions version of the problem through a simple instance of the exploration-by-optimization method that is amenable to efficient implementation. We derive regret bounds that depend on the game structure in a more transparent manner than previous theoretical guarantees for this paradigm. Our bounds feature instance-specific quantities that reflect the degree of alignment between observations and losses, and resemble known guarantees in the stochastic setting. Notably, they achieve the standard √T rate in easy (locally observable) games and T2/3 in hard (globally observable) games, where T is the time horizon. We instantiate these bounds in a selection of old and new partial information settings subsumed by this model, and illustrate that the achieved dependence on the game structure can be tight in interesting cases.