Sequential Decision Making with Indirect Feedback

This direction is split into other directions: partial monitoring. Its last version stays readable and citable here.

Version 1 of 136 papers36 conceptsfrozen 2026-10-04

In the standard multi-armed bandit problem, an agent pulls a lever and immediately sees the resulting reward. However, real-world decision-making is rarely so transparent. Consider a doctor choosing a treatment: they don't see a "reward" number; they see a clinical test result that is only a noisy signal of the patient's true health. Or consider dynamic pricing: a seller sets a price and only observes whether a customer bought the item, not the maximum price the customer was willing to pay.

This research direction, known as Partial Monitoring, studies how agents can learn to make optimal decisions when they never directly observe their own rewards or the true state of the environment. Instead, they must reconstruct the truth from a stream of indirect, often cryptic, signals.

The Feedback Matrix

The core intuition of partial monitoring lies in the relationship between actions, hidden states, and signals. This is often modeled as two matrices: a loss matrix (what you actually lose but don't see) and a feedback matrix (what you actually see).

As Gábor Lugosi and Gilles Stoltz established in Strategies for Prediction Under Imperfect Monitoring, the difficulty of the problem depends entirely on whether the feedback matrix provides enough information to distinguish between different environmental states. If two states result in different rewards but produce the exact same signals for every action you take, you are "blind" and cannot minimize regret.

The Four Worlds of Difficulty

Research by Gábor Bartók, Dávid Pál, and Csaba Szepesvari in Minimax Regret of Finite Partial-Monitoring Games in Stochastic Environments revealed that all partial-monitoring games fall into one of four distinct difficulty classes based on their information structure:

  1. Trivial: The best action is obvious from the start. Regret is zero.
  2. Easy: You can estimate the losses of all actions relatively quickly. Regret grows at a rate of $O(\sqrt{T})$, similar to standard bandits.
  3. Hard: To learn about the best action, you must occasionally take "informative" actions that are known to be sub-optimal. This trade-off forces regret to grow faster, at $O(T^{2/3})$.
  4. Hopeless: The signals are insufficient to ever identify the best action. Regret grows linearly ($O(T)$), meaning the agent never learns.

Local Observability and Neighborhood Watch

Why do some games have $O(\sqrt{T})$ regret while others have $O(T^{2/3})$? The answer lies in local observability.

In No Internal Regret via Neighborhood Watch, Alexander Rakhlin and Dean P. Foster introduced the "Neighborhood Watch" algorithm. The intuition is that if an agent can estimate the difference in loss between two neighboring actions using only the signals available from those actions (or their neighbors), they can navigate the action space efficiently. If they have to jump to a completely different, high-loss action just to get information about their current neighborhood, the game becomes "Hard."

Modern Algorithmic Strategies

Recent work has moved toward making these theoretical insights practical and robust.

Bayesian and Information-Theoretic Approaches

Traditional algorithms for partial monitoring were often mathematically dense and computationally heavy. Tor Lattimore and Csaba Szepesvari simplified this in An Information-Theoretic Approach to Minimax Regret in Partial Monitoring by using Bregman divergences to bound regret, removing the massive constants that plagued earlier proofs.

For stochastic settings, Taira Tsuchiya, Junya Honda, and Masashi Sugiyama developed TSPM in Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring. This was the first algorithm to successfully apply Thompson Sampling—a method that picks actions based on the probability they are optimal—to the partial monitoring setting with proven logarithmic regret.

Information Directed Sampling

A particularly powerful framework is Information Directed Sampling (IDS). As explored by Johannes Kirschner and Andreas Krause in Information Directed Sampling for Linear Partial Monitoring, IDS explicitly balances the "cost" of an action (its expected regret) against its "gain" (how much information it provides about the hidden parameters). By choosing actions that minimize the ratio of squared regret to information gain, the agent naturally transitions between exploration and exploitation.

Expanding the Frontier

The principles of partial monitoring are now being applied to increasingly complex scenarios:

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_sequential_decision_making_with_indirect_5f35e998,
  title = {Sequential Decision Making with Indirect Feedback},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-decision-making-with-indirect-feedback/rdr_5f35e9985d574e0da16b256464cb6ecb},
  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_sequential_decision_making_with_indirect_5f35e998_v1,
  title = {Sequential Decision Making with Indirect Feedback},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-decision-making-with-indirect-feedback/rdr_5f35e9985d574e0da16b256464cb6ecb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}