Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoring

2025/10/22 by Federico Di Gennaro, Di Gennaro, Federico, Khaled Eldowa +3
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Game Theory and Applications #Machine Learning (cs.LG) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2510.19158

openalex publication_date 2025/10/22 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28

Abstract

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 T^2/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.

Citations

• Neural Active Learning Meets the Partial Monitoring Framework
• Information Capacity Regret Bounds for Bandits with Mediator Feedback
• Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoring
• Randomized Confidence Bounds for Stochastic Partial Monitoring
• Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds
• Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applications
• Best-of-Both-Worlds Algorithms for Partial Monitoring
• On the Complexity of Adversarial Decision Making
• Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini's Regret
• The Statistical Complexity of Interactive Decision Making
• Mirror Descent and the Information Ratio
• Bandit Algorithms
• Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring
• Information Directed Sampling for Linear Partial Monitoring
• Exploration by Optimisation in Partial Monitoring
• An Information-Theoretic Approach to Minimax Regret in Partial Monitoring
• Cleaning up the neighborhood: A full classification for adversarial partial monitoring
• Differentiating the pseudo determinant
• Tight Bounds for Bandit Combinatorial Optimization
• Phased Exploration with Greedy Exploitation in Stochastic Combinatorial\n Partial Monitoring Games
• Regret Lower Bound and Optimal Algorithm in Finite Stochastic Partial Monitoring
• Cheap Bandits
• Online Learning with Feedback Graphs: Beyond Bandits
• Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback
• Learning to Optimize via Information-Directed Sampling
• An Adaptive Algorithm for Finite Stochastic Partial Monitoring
• Towards minimax policies for online linear optimization with bandit feedback
• No Internal Regret via Neighborhood Watch
• From Bandits to Experts: On the Value of Side-Observations
• Toward a Classification of Finite Partial-Monitoring Games
• The Nonstochastic Multiarmed Bandit Problem

Related

• Best-of-Both-Worlds Algorithms for Partial Monitoring
• Exploration by Optimisation in Partial Monitoring
• No Internal Regret via Neighborhood Watch
• Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applications
• An Information-Theoretic Approach to Minimax Regret in Partial Monitoring