Extending Bandit Mechanisms to Markov Decision Processes

44 concepts46 papers1 proposal

The core tension in sequential decision-making lies between mathematical tractability and environmental complexity. Multi-armed bandits (MABs) offer an elegant framework for balancing exploration and exploitation, providing tight regret bounds, robust estimation under heavy-tailed noise, and clear statistical guarantees. However, bandits operate under a restrictive assumption: the world is stateless. Every action yields an immediate reward, completely isolated from past choices.

Real-world reinforcement learning (RL) requires navigating Markov Decision Processes (MDPs), where actions carry long-term consequences. An action chosen today does not merely return a reward; it alters the environment's state, shifting the distribution of future rewards and available actions.

A major frontier in sequential decision-making focuses on bridging this gap. Researchers are working to scale the theoretical insights of bandit algorithms—such as robust estimation, PAC-Bayesian guarantees, and history-perturbation exploration—to handle the state transitions and long-term credit assignment inherent to MDPs.

Robust Estimation Under Heavy-Tailed Feedback

In a standard bandit setting, handling extreme outliers or heavy-tailed reward distributions is well-understood. For instance, Chenlu Ye et al. demonstrate in Catoni Contextual Bandits are Robust to Heavy-tailed Rewards that incorporating Catoni’s robust mean estimator allows contextual bandits to achieve regret bounds scaling with the actual reward variance rather than the maximum reward range. Similarly, Jing Wang et al. introduce an efficient one-pass update framework combining Huber regression with online mirror descent in Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update to achieve optimal regret under heavy-tailed noise.

Bandit Setting:
Action ──> [Immediate Heavy-Tailed Reward] (Affects only local estimate)

MDP Setting:
Action ──> [Heavy-Tailed Reward + State Transition] ──> Next State ──> Value Function Propagation
                                                            │
                                                            └───> Outlier distorts upstream values

Why it breaks in MDPs

In a stateless bandit, an outlier reward only distorts the estimate of that specific arm or context. In an MDP, however, rewards and transition noise propagate through the Bellman optimality equation. Because value functions are computed recursively, a single heavy-tailed outlier can corrupt the value estimates of multiple upstream states. Adapting variance-aware or one-pass robust estimators to linear or general MDPs requires tracking how heavy-tailed noise interacts with long-term credit assignment across state transitions.

Generalizing PAC-Bayesian and Martingale Guarantees

To prove that an online learning algorithm will perform reliably, theorists rely on concentration inequalities to bound the probability of large deviations. Traditional PAC-Bayesian frameworks require independent and identically distributed (i.e.d.) data, a condition routinely violated by sequential decision-making.

To handle this dependency, Yevgeny Seldin et al. extended these boundaries in PAC-Bayesian Analysis of Martingales and Multiarmed Bandits by developing a framework for martingales (sequences of dependent random variables). This mathematical foundation was expanded by Yevgeny Seldin et al. in PAC-Bayes-Bernstein Inequality for Martingales and its Application to Multiarmed Bandits, providing data-dependent bounds that capture the exploration-exploitation trade-off in environments with limited feedback.

Why it breaks in MDPs

While martingales successfully capture the temporal dependence of an agent's history within a stateless bandit, full MDPs introduce structural state transitions governed by an underlying environmental kernel. The probability of entering a specific state depends explicitly on the interaction between the agent's policy and the transition dynamics. This introduces complex feedback loops that standard martingale analyses cannot easily bound, making the extension of PAC-Bayesian priors to continuous or discrete state spaces an ongoing theoretical challenge.

Deconstructing Exploration and Task Classification

Exploration in bandits can often be simplified to avoid the computational burden of tracking exact posterior distributions or confidence intervals. For example, Branislav Kveton et al. propose Perturbed-History Exploration in Perturbed-History Exploration in Stochastic Multi-Armed Bandits, which drives exploration simply by adding random "pseudo-rewards" to an arm's historical data. In meta-learning scenarios, Mirco Mutti et al. frame task exploration as a classification problem in A Classification View on Meta Learning Bandits, using decision trees to identify which task an agent is facing to achieve near-optimal regret.

Bandit Exploration:
Action ──> Immediate Feedback ──> Update History ──> Next Choice (Safe to fail)

MDP Exploration:
Action ──> State Change ──> Potential "Dead End" State (Irreversible loss of information capacity)

Why it breaks in MDPs

In a stateless environment, taking an exploratory action has no bearing on what choices are available next; the agent can always return to a known safe option in the next round. In an MDP, an exploratory action can push the agent into a "dead end" or a highly suboptimal region of the state space, permanently altering its ability to collect future information or rewards. Consequently, history-perturbation or classification-based exploration strategies cannot merely evaluate past rewards; they must be redesigned to anticipate how current actions alter the environmental state and the agent's long-term capacity to safely navigate and classify the environment.

Off-Policy Evaluation and Structural Complexity

Evaluating a new policy using historical data collected by a different logging policy—known as Off-Policy Evaluation (OPE)—is highly tractable in bandit settings. Banghua Zhu et al. map out the exact statistical limits of this in Minimax Off-Policy Evaluation for Multi-Armed Bandits, establishing minimax-optimal estimators (such as the Switch estimator) across various knowledge regimes.

Furthermore, when structural assumptions are introduced, the complexity can drop dramatically. For instance, Kishan Panaganti demonstrates in Bounded Regret for Finitely Parameterized Multi-Armed Bandits that if a bandit environment is governed by one of a finite number of possible parameter types, an algorithm can achieve bounded regret, eventually eliminating mistakes entirely once the true parameter is identified.

Why it breaks in MDPs

In bandits, the data distribution is determined entirely by the logging policy's action choices. In MDPs, the logging policy interacts with the environmental transition dynamics, causing errors in density estimation to compound exponentially over long horizons—a phenomenon known as the "curse of horizon."

To mitigate this structural complexity, the authors of Representation Learning for Online and Offline RL in Low-rank MDPs (Masatoshi Uehara et al.) integrate representation learning directly with exploration and pessimism to handle low-rank state transitions. However, extending minimax OPE guarantees and bounded-regret properties from these structured settings to general high-dimensional or high-Bellman-rank MDPs remains a primary open challenge in sequential decision-making scalability.

Key Foundational Work

Meta-learning of Exploration/Exploitation Strategies: The Multi-armed Bandit Case (2012) — contributed 1 concept elements to this direction.
PAC-Bayesian Analysis of Martingales and Multiarmed Bandits (2011) — contributed 1 concept elements to this direction.
PAC-Bayes-Bernstein Inequality for Martingales and its Application to Multiarmed Bandits (2012) — 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_sequential_decision_making_scalability_71076dd7,
  title = {sequential decision-making scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-decision-making-scalability/rdr_71076dd7f00a4213868ba52316912c9d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_sequential_decision_making_scalability_71076dd7_v1,
  title = {sequential decision-making scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-decision-making-scalability/rdr_71076dd7f00a4213868ba52316912c9d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake