Abstract
Partial monitoring is a general framework for online learning where feedback is decoupled from loss. While "easy" games in this setting theoretically allow for $O(\sqrt{n})$ regret, existing algorithms often suffer from computational inefficiency or regret bounds dependent on large game-specific constants. This paper introduces ExpPM, an algorithm that solves a convex optimisation problem to determine the optimal exploration distribution. ExpPM achieves near-optimal regret bounds across various game types—including bandits, full information, and both locally and globally observable partial monitoring games—without requiring manual tuning for specific game geometries.
Introduction: The Partial Monitoring Landscape
In online learning, the learner repeatedly chooses an action and suffers a loss. In the standard Multi-Armed Bandit (MAB) setting, the learner observes the loss of the chosen action. Partial Monitoring generalizes this by providing a feedback signal that may only indirectly relate to the loss. For instance, a learner might receive a signal about the state of the environment without knowing the exact loss incurred or the potential losses of other actions.
Partial monitoring games are classified by their minimax regret:
- Trivial: Zero regret.
- Easy (Locally Observable): Regret grows at $O(\sqrt{n})$.
- Hard (Globally Observable): Regret grows at $O(n^{2/3})$.
- Hopeless: Regret grows linearly $O(n)$.
Historically, "easy" games have been problematic. While $O(\sqrt{n})$ regret is achievable, previous constructive algorithms were either computationally prohibitive or had regret bounds heavily influenced by the complex geometry of the game's action space.
Methodology: ExpPM and Exploration by Optimisation
The authors propose ExpPM (Exponential Weights for Partial Monitoring), which builds upon the classic Exponential Weights algorithm but introduces a novel Exploration by Optimisation step.
Instead of sampling actions directly from the distribution $q$ generated by exponential weights, the algorithm solves a convex optimisation problem in each round to find a sampling distribution $p$ and a loss estimation function $G$. The objective function minimizes a trade-off between:
- The divergence between the sampling distribution $p$ and the target distribution $q$.
- The bias of the loss estimator.
- The stability (variance) of the importance-weighted estimator.
By solving this problem, ExpPM automatically identifies the most informative actions to play—even if they are currently sub-optimal—to minimize long-term regret. This approach effectively "bridges" the gap between exploitation and exploration by treating the stability term of the regret bound as an optimizable objective.
Key Insights and Theoretical Results
The primary innovation is the use of minimax duality to ensure a valid exploration distribution always exists. The authors leverage concepts like "water transfer operators" from Bayesian experimental design to describe how probability mass is shifted toward informative actions.
Regret Bounds
ExpPM provides a unified framework that adapts to the game's difficulty:
- Locally Observable Games: Achieves $O(m k^{3/2} \sqrt{n \log k})$ regret, where $m$ is the number of outcomes and $k$ is the number of actions. This bound is notable for being independent of the "geometry" constants that affected prior work.
- Globally Observable Games: Recovers the optimal $O(n^{2/3})$ bound.
- Standard Settings: Matches known bounds for MAB ($O(\sqrt{nk \log k})$) and full information games ($O(\sqrt{n \log k})$).
Empirical Performance and Limitations
In synthetic tests such as "Costly Matching Pennies"—a game where information gain requires playing a costly action—ExpPM outperforms state-of-the-art algorithms like "Neighbourhood Watch 2." This demonstrates that the theoretical benefits of the optimisation approach translate into practical efficiency.
However, challenges remain. Solving a convex optimisation problem in every round introduces computational overhead, particularly for large action spaces. Additionally, while the algorithm handles "degenerate" games (where action regions overlap or are non-unique), the regret constants in these cases may scale exponentially with the dimension $d$. Future work aims to extend these principles to infinite outcome spaces and improve the computational efficiency of the per-round optimisation.
Summary updated