Exploration by Optimisation in Partial Monitoring

Tor Lattimore, Csaba Szepesvári

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.

Visualization of action regions in a partial monitoring game.

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:

  1. The divergence between the sampling distribution $p$ and the target distribution $q$.
  2. The bias of the loss estimator.
  3. The stability (variance) of the importance-weighted estimator.
The transition from the target distribution q to the sampling distribution p through optimisation.

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

Abstract

We provide a simple and efficient algorithm for adversarial $k$-action $d$-outcome non-degenerate locally observable partial monitoring game for which the $n$-round minimax regret is bounded by $6(d+1) k^{3/2} \sqrt{n \log(k)}$, matching the best known information-theoretic upper bound. The same algorithm also achieves near-optimal regret for full information, bandit and globally observable games.
BibTeX
@inproceedings{lattimore2020exploration,
  author = {Tor Lattimore and Csaba Szepesvári},
  title = {{Exploration by Optimisation in Partial Monitoring}},
  booktitle = {Conference on Learning Theory},
  year = {2020},
}
Figure