In many decision-making paradigms—ranging from contextual bandits and causal inference to offline model-based optimization—we possess highly sophisticated statistical tools. These frameworks allow us to evaluate new policies safely, bound our uncertainty, correct for distribution shifts, and optimize multiple conflicting objectives using historical data.
However, a core frontier in reinforcement learning (RL) research is the mathematical and conceptual chasm between these single-step frameworks and full, multi-step Markov Decision Processes (MDPs). When we transition from independent, one-shot choices to sequential trajectories, our established statistical guarantees frequently break down. Understanding why these single-step methods fail in sequential environments reveals the exact mechanisms—such as compounding variance, dynamic covariate shift, and delayed credit assignment—that multi-step RL algorithms must overcome.
The Curse of Horizon in Off-Policy Evaluation
In a single-step contextual bandit, evaluating a new target policy $\pi$ using data collected by a different behavior policy $\mu$ relies on importance sampling. For a given context, the estimator scales the observed reward by an importance weight:
$$\omega = \frac{\pi(a|x)}{\mu(a|x)}$$
If an action is rare under the behavior policy but frequent under the target policy, $\omega$ becomes large, increasing variance. To make these estimators practical, researchers have developed powerful variance-reduction and inference techniques. For instance, Armin Behnamnia et al. introduced a robust estimator based on the Log-Sum-Exponential operator in Log-Sum-Exponential Estimator for Off-Policy Evaluation and Learning to effectively insulate single-step evaluations from extreme outliers and heavy-tailed rewards.
To safely deploy new policies without traditional A/B testing, we also need tight confidence intervals. Ian Waudby-Smith et al. developed martingale-based techniques in Anytime-valid off-policy inference for contextual bandits to provide confidence sequences that remain valid at any stopping time. Similarly, Nikos Karampatziakis et al. leveraged non-parametric betting games in Off-Policy Confidence Sequences to construct valid sequences even when importance weights are unbounded. To further tighten these bounds, Claire Vernade et al. utilized self-normalized importance weights in Confident Off-Policy Evaluation and Selection through Self-Normalized Importance Weighting to stabilize the estimator when behavior policy probabilities are small.
Single-Step: [Context x] ---> (Action a) ---> [Reward r] (Variance is bounded)
Multi-Step: [State s_0] ---> (Action a_0) ---> [State s_1] ---> (Action a_1) ---> [State s_2]
Weights: ω_0 × ω_1 (Variance explodes exponentially)
The fundamental barrier to scaling these methods to full reinforcement learning is that trajectories compound these weights sequentially. Over a horizon of $T$ steps, the trajectory-level importance weight becomes a product of single-step weights:
$$\Omega = \prod_{t=1}^T \frac{\pi(a_t|s_t)}{\mu(a_t|s_t)}$$
This product causes the estimator's variance to explode exponentially with the horizon $T$. As a result, safety-focused evaluation methods designed for single-step decisions—such as those analyzed by Philip S. Thomas et al. in High-Confidence Off-Policy Evaluation—face severe statistical degradation when applied to sequential trajectories. The tight, anytime-valid guarantees disappear because errors and weight discrepancies multiply at every sequential state transition.
Dynamic Covariate Shift and Compounding Uncertainty
When learning a policy entirely from offline, historical data, an agent must avoid selecting out-of-distribution (OOD) actions that might have erroneously high predicted values. In single-step settings, we enforce this through pessimism: penalizing rewards in regions where data is scarce.
For linear contextual bandits, Gene Li et al. demonstrated in Pessimism for Offline Linear Contextual Bandits using $\ell_p$ Confidence Sets that constructing uniform norm ($\ell_\infty$) confidence sets yields adaptively minimax-optimal policies without requiring full data coverage. When the data distribution shifts, single-step frameworks can correct for this covariate shift directly. For example, Hao Liu et al. developed a "Triply Robust" estimator in Triply Robust Off-Policy Evaluation that minimizes bias even when the logging policy is completely unknown, while Xiaoying Zhang et al. modeled logging policy uncertainty via instance reweighting in Uncertainty-Aware Instance Reweighting for Off-Policy Learning.
In an MDP, however, covariate shift is not a static property of a fixed dataset; it is a dynamic process. An action taken at step $t$ changes the environment's state, altering the state distribution at step $t+1$. This means any initial distribution shift or estimation error propagates forward through the transition dynamics.
As identified by Qi Han et al. in Data-Driven Offline Decision-Making via Invariant Representation Learning, offline optimization techniques that assume independent, single-step designs fail in RL because they cannot account for how internal representations must remain invariant across cascading temporal dependencies. Similarly, the semiparametric efficiency and policy adaptation frameworks established by Xueqing Liu et al. in Optimal Policy Adaptation Under Covariate Shift must be fundamentally restructured for sequential settings to maintain statistical efficiency as distribution shifts compound across long-term trajectories.
The Credit Assignment Problem in Complex Objectives
The transition from single-step to multi-step environments also complicates how we optimize complex objectives, such as regularized, multi-objective, or preference-based targets.
In single-step settings, regularized offline learning enjoys clean theoretical bounds. Qingyue Zhao et al. showed in Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits that under strongly convex regularizers like $\chi^2$-divergence, fast policy learning is achievable with zero data coverage requirements. When balancing multiple conflicting goals, offline single-step frameworks can map out Pareto-optimal frontiers reliably, as shown by Shima Alizadeh et al. in Pessimistic Off-Policy Multi-Objective Optimization and Association for Artificial Intelligence 2026 et al. in Offline Multi-Objective Bandits: From Logged Data to Pareto-Optimal Policies. Even human preference alignment (such as Direct Preference Optimization) can be cleanly bounded in bandit settings, as demonstrated by Andi Nika et al. in Policy Teaching via Data Poisoning in Learning from Human Preferences.
Single-Step Preference: (Action a) -------------------------> [Immediate Preference Feedback]
(Direct Credit Assignment)
Multi-Step Preference: (Action a_0) -> (Action a_1) -> (Action a_2) -> [Delayed Preference Feedback]
(Which action caused the preference?)
The barrier to scaling these frameworks to sequential MDPs is the credit assignment problem. When a reward, preference, or cost is delayed or depends on a sequence of multiple choices, a single-step framework cannot determine which specific action caused the outcome.
For instance, reward decomposition techniques designed to handle massive action spaces (Yuta Saito et al. in Off-Policy Evaluation for Large Action Spaces via Conjunct Effect Modeling) break down when actions have long-term downstream consequences. To optimize expected utility over a trajectory, an agent cannot treat decisions independently; it must maintain and propagate entire return distributions across multiple time steps, a challenge highlighted by Enda Howley in Expected scalarised returns dominance: a new solution concept for multi-objective decision making.
Bridging the Gap via Multi-Step Updates
To overcome these limitations, reinforcement learning algorithms must explicitly transition from single-step updates to multi-step trajectory evaluations. However, this transition introduces its own mathematical complexities.
Historically, proving the convergence of single-step on-policy temporal difference (TD) updates, such as SARSA, was a major milestone achieved by Satinder Singh et al. in Convergence Results for Single-Step On-Policy Reinforcement-Learning Algorithms. Yet, single-step TD updates learn slowly because they only propagate information one step at a time. To accelerate learning, algorithms use multi-step returns or eligibility traces to bridge the gap between immediate actions and long-term outcomes.
When we combine multi-step returns with function approximation and off-policy data, we encounter the "deadly triad"—a recipe for algorithmic divergence. If we use standard importance sampling over multiple steps to correct for off-policy data, the variance explodes. If we truncate the corrections too aggressively, we introduce severe bias.
To resolve this tension, algorithms must mathematically guarantee stability while preserving multi-step credit assignment. For example, Xingguo Chen developed Modified Retrace in Modified Retrace for Off-Policy Temporal Difference Learning, proving that ensuring the positive definiteness of the update matrix allows an algorithm to safely leverage long-range dependencies without risking instability.
Similarly, optimization frameworks must adapt their underlying geometry to handle sequential dependencies. While advanced optimization techniques like quantum natural gradients can drastically improve sample efficiency in single-step tasks (Daniel D. Scherer et al. in Quantum Natural Policy Gradients: Towards Sample-Efficient Reinforcement Learning), their extension to multi-step environments requires accounting for how policy changes alter long-term state distributions.
Ultimately, moving from single-step decisions to multi-step trajectories requires shifting from static regression and independent optimization toward frameworks that explicitly model how actions, rewards, and uncertainties propagate over time. This transition—pioneered by early hybrid approaches like the reward-directed value fitting proposed by Yi-Hao Kao in Directed Regression and cost-averse variational policy searches developed by Gerhard Neumann in Variational Inference for Policy Search in changing situations—remains the central mechanism for building robust, long-horizon sequential decision-making agents.
Key Foundational Work
Directed Regression (2009) — contributed 1 concept elements to this direction.
Convergence Results for Single-Step On-Policy Reinforcement-Learning Algorithms (2000) — contributed 1 concept elements to this direction.