Sequential Decision Making under Partial Monitoring

17 concepts17 papers

In standard online learning, an agent chooses an action and immediately observes its direct consequence—either the reward of that specific action (bandit feedback) or the rewards of all possible actions (full information). However, real-world feedback is rarely so direct. Consider dynamic pricing: a retailer sets a price, and a customer either buys the product or walks away. The retailer never observes the customer's exact maximum willingness to pay; they only receive a binary signal.

This is the core of partial monitoring: a framework where the learner never directly observes the true underlying losses or rewards, nor the exact state of the environment. Instead, they must navigate a stream of indirect, cryptic feedback signals to infer which actions are optimal.

The Core Challenge: Decoupling Information from Reward

Why can't we just use standard bandit algorithms? In a multi-armed bandit, every time you pull an arm, you simultaneously collect a reward and reduce your uncertainty about that specific arm. Information and reward are bundled together.

In partial monitoring, this coupling is broken. An action might yield excellent short-term rewards but provide zero information about the environment's true state. Conversely, another action might be highly suboptimal but yield a crystal-clear feedback signal that reveals the losses of all other actions.

To formalize this, a partial monitoring game is defined by two matrices: a loss matrix $L$ and a feedback matrix $H$. When the learner chooses action $i$ and the environment is in state $j$, the learner incurs loss $L_{i,j}$ but only observes the signal $H_{i,j}$. The fundamental challenge is to figure out how to estimate the unobserved losses using only the observed history of signals. Early foundational work by Gilles Stoltz et al. in Strategies for Prediction Under Imperfect Monitoring provided the first computationally efficient, gradient-based algorithms to prove that learning under such imperfect monitoring is achievable with explicit convergence rates.

The reason we can learn at all is that we don't need to observe the loss directly, as long as the observable signals contain enough linear information to reconstruct it. If the expected feedback signals can be linearly inverted to form an unbiased estimator of the losses, the learner can successfully minimize regret over time.

The Geometry of Hardness: Local vs. Global Observability

Not all partial monitoring games are created equal. The structural relationship between the loss matrix $L$ and the feedback matrix $H$ dictates how hard a game is. Gábor Bartók et al. demonstrated in Minimax Regret of Finite Partial-Monitoring Games in Stochastic Environments that every finite stochastic partial monitoring game falls into one of four distinct minimax regret classes:

  1. Trivial games (Regret = $0$): The optimal action can be deduced immediately without exploration.
  2. Hopeless games (Regret = $\Theta(T)$): The feedback matrix provides absolutely no information to distinguish between optimal and suboptimal actions.
  3. Easy games (Regret = $\Theta(\sqrt{T})$): These games satisfy a condition called local observability.
  4. Hard games (Regret = $\Theta(T^{2/3})$): These games satisfy global observability but lack local observability.

To understand the difference between Easy and Hard games, consider how we estimate losses. In an "Easy" game, the feedback from an action is sufficient to estimate the difference in losses between that action and its immediate neighbors in the action space. As shown by Alexander Rakhlin et al. in No Internal Regret via Neighborhood Watch, we can construct a "Neighborhood Watch" mechanism where actions monitor their neighbors, allowing the learner to control regret at the optimal $\sqrt{T}$ rate without executing wildly suboptimal actions.

In a "Hard" game, however, distinguishing between two high-performing actions requires playing a completely different, highly suboptimal "informative" action. Because the learner must repeatedly pay an "information tax"—incurring heavy losses just to gather information—the optimal regret degrades to $T^{2/3}$. This geometric boundary was later extended to adversarial environments by Tor Lattimore et al. in Cleaning up the neighborhood: A full classification for adversarial partial monitoring, completing the full classification of adversarial partial monitoring via advanced algorithms like NeighborhoodWatch2 and RelExp3.

Algorithmic Mechanisms: How to Learn from Cryptic Signals

Modern partial monitoring algorithms rely on distinct mathematical paradigms to bridge the gap between indirect observations and optimal choices.

Estimation via Linear Inversion

The core trick behind many adversarial algorithms, such as GlobalExp3 proposed by Gábor Bartók in A near-optimal algorithm for finite partial-monitoring games against adversarial opponents, is to construct unbiased estimators of the unobserved losses. Since the expected feedback is a linear function of the environment's state distribution, we can invert this linear relationship to map observed signal frequencies back to estimated losses, scaling the exploration step based on the local complexity of the game.

Information-Directed Sampling

In stochastic settings, we can explicitly quantify the trade-off between reward and information. Johannes Kirschner et al. leveraged this in Information Directed Sampling for Linear Partial Monitoring. Instead of just picking the action with the highest optimistic reward, Information Directed Sampling (IDS) minimizes an information ratio:

$$\Psi_t(p) = \frac{\Delta(p)^2}{g(p)}$$

where $\Delta(p)$ is the expected regret of an action distribution $p$, and $g(p)$ is the information gain about the hidden parameters. If an algorithm takes a suboptimal action, IDS ensures it receives a massive informational dividend in return, rapidly thinning out the hypothesis space.

Bayesian and Posterior Updates

Rather than relying purely on frequentist loss estimators, Bayesian approaches track a posterior distribution over the environment's states. Hastagiri P. Vanchinathan et al. introduced Bayes-update Partial Monitoring (BPM) in Efficient Partial Monitoring with Prior Information, which maintains a confidence ellipsoid over the outcome distributions to accelerate computation.

For a long time, applying Thompson Sampling to partial monitoring relied on shaky heuristics. However, Taira Tsuchiya et al. introduced TSPM in Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring, providing the first exact posterior sampling method with proven logarithmic regret bounds for stochastic partial monitoring.

+-----------------------------------------------------------------------+
|                          Partial Monitoring                           |
+-----------------------------------------------------------------------+
                                    |
         +--------------------------+--------------------------+
         |                                                     |
         v                                                     v
+----------------------------------+       +----------------------------------+
|       Adversarial Settings       |       |       Stochastic Settings        |
+----------------------------------+       +----------------------------------+
| • Linear Inversion of Signals    |       | • Posterior Sampling (TSPM)      |
| • Neighborhood Watch (Local Est) |       | • Info-Directed Sampling (IDS)   |
| • Minimax Regret: T^1/2 or T^2/3 |       | • Logarithmic Regret Bounds      |
+----------------------------------+       +----------------------------------+
         |                                                     |
         +--------------------------+--------------------------+
                                    |
                                    v
+-----------------------------------------------------------------------+
|                    Best-of-Both-Worlds (BOBW)                         |
|      Automatically adapts to environment type via hybrid regularizers |
+-----------------------------------------------------------------------+

Advanced Frontiers: Universality and Robustness

The principles of partial monitoring extend far beyond standard regret minimization. For instance, in multi-objective optimization or game theory, an agent might want to ensure that their average payoff vector approaches a target "goal zone," a framework known as Blackwell approachability. Joon Kwon et al. established optimal convergence rates for this setting in Online Learning and Blackwell Approachability with Partial Monitoring: Optimal Convergence Rates, extending the calibration-based frameworks originally designed by Vianney Perchet in Internal Regret with Partial Monitoring: Calibration-Based Optimal Algorithms.

To clean up the mathematical complexity of these diverse proofs, Tor Lattimore et al. introduced a streamlined framework in An Information-Theoretic Approach to Minimax Regret in Partial Monitoring. By leveraging Bregman divergences and a new minimax theorem, they bypassed the massive constants of earlier proofs, providing a clean, unified toolkit for analyzing partial monitoring games. Similarly, in An adaptive algorithm for finite stochastic partial monitoring, the authors developed a versatile, adaptive algorithm that doesn't need to know the game's difficulty class in advance, dynamically adjusting its exploration strategy based on the history of cryptic signals. To achieve the absolute theoretical limits in stochastic settings, the authors of Regret Lower Bound and Optimal Algorithm in Finite Stochastic Partial Monitoring established the first logarithmic distribution-dependent regret lower bound using a minimum empirical divergence approach (PM-DMED).

A major recent push focuses on environmental robustness. Historically, an algorithm designed for predictable, stochastic environments would fail miserably against an adaptive adversary, and vice versa. To solve this, Taira Tsuchiya et al. developed the first "Best-of-Both-Worlds" (BOBW) algorithms for partial monitoring in Best-of-Both-Worlds Algorithms for Partial Monitoring.

Further refining this paradigm, Shinji Ito et al. introduced hybrid regularizers in Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoring. By dynamically adjusting the regularization function based on the observed feedback, these algorithms achieve the ultimate goal: securing tight logarithmic regret if the environment is stochastic, while maintaining robust minimax safety guarantees if the environment turns adversarial.

Key Foundational Work

Regret Minimization Under Partial Monitoring (2006) — contributed 1 concept elements to this direction.
Strategies for prediction under imperfect monitoring (2008) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_partial_monitoring_543a4cef,
  title = {partial monitoring},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/partial-monitoring/rdr_543a4cef6c4e4e7a8dc35e989ba43b22},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_partial_monitoring_543a4cef_v1,
  title = {partial monitoring},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/partial-monitoring/rdr_543a4cef6c4e4e7a8dc35e989ba43b22/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}

See something wrong? Report a mistake