RL Theory & Markov Decision Processes
Sample-Efficient Reinforcement Learning Under Markovian Trajectory Sampling Without a Generative Model
Generated automatically from the limitations stated in 8 papers (AISTATS, ICML), listed under Evidence. It is not a paper, and it does not come from papers submitted to CSPaper.
The problem
Theoretical analysis in these MDP frameworks relies on a generative model that provides independent transition samples for arbitrary state-action queries. In real-world physical systems and streaming applications, arbitrary state resetting is impossible and data must be gathered along continuous online or episodic trajectories. As a result, existing sample complexity and convergence guarantees fail to hold under realistic Markovian data generation, leaving theoretical bounds disconnected from deployable online settings.
Why it matters
Provable convergence and sample efficiency guarantees for RL algorithms operating purely on continuous online trajectory data without simulator access. Enables practitioners to deploy these methods on physical systems where resetting to arbitrary states is physically impossible.
Ways to approach it
Prior-work checks are free with an account. Results someone already ran are shown to everyone.
- 1
Establish finite-sample error bounds by replacing independent batch bounds with martingale concentration inequalities (e.g., Freedman's inequality) and Markov chain mixing time arguments over single-trajectory rollouts.
- 2
Formulate an upper-confidence-bound (UCB) exploration wrapper around the base tabular algorithms to handle non-uniform state-action coverage induced by trajectory sampling, measuring cumulative regret and total sample complexity to reach $\epsilon$-optimality.
Have a different approach?
Describe how you would tackle this problem and we'll look for papers that already do it. Free; your text stays private.
Why it might fail
If lower bounds show that overcoming the distribution shift inherent to trajectory sampling introduces an unavoidable exponential dependence on problem horizon or mixing time without additional strong ergodicity assumptions.
Evidence
Each paper's own statement of the limitation, verbatim.
- Efficiently Solving Discounted MDPs via Predictions with Unknown Prediction ErrorsICML 2026
Restricted to tabular finite-state and finite-action DMDP settings with access to a generative model.
- Overcoming the Curse of Dimensionality in Reinforcement Learning Through Approximate FactorizationICML 2025
Analysis assumes a generative model allowing arbitrary state-action queries; extension to Markov sampling only sketched and requires a uniformly ergodic behavior policy per factor
- Near-Optimal Sample Complexity for MDPs via AnchoringICML 2025
Requires a generative model (independent samples from P(·|s,a) for all state-action pairs); episodic or online sampling settings are not analyzed
- MDP Geometry, Normalization and Reward Balancing SolversAISTATS 2025
The unknown-dynamics analysis assumes a generative model (free sampling of any action's transitions at any step), which does not cover single-trajectory or online RL settings
- Feasible $Q$-Learning for Average Reward Reinforcement LearningAISTATS 2024
Requires a synchronous generative model producing fresh independent samples for every state-action pair each iteration, not online trajectory data
- Distributionally Robust Model-based Reinforcement Learning with Large State SpacesAISTATS 2024
Requires a generative model (simulator) allowing arbitrary state-action queries, not trajectories from real environment interaction; the authors note extension to online and offline settings is open
- Improved Sample Complexity Bounds for Distributionally Robust Reinforcement LearningAISTATS 2023
Requires a generative model of the nominal environment and a tabular state-action space; cannot handle high-dimensional continuous control such as MuJoCo
- A Statistical Analysis of Polyak-Ruppert Averaged Q-LearningAISTATS 2023
Requires a synchronous generative model producing independent samples for every state-action pair each iteration — not applicable to online/async sampling
Nearest existing work
- Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited RevisitingNeurIPS 2021
- Efficiently Solving Discounted MDPs via Predictions with Unknown Prediction ErrorsICML 2026
- Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative ModelNeurIPS 2021
- The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity AnalysisALT 2025
- Model-based Reinforcement Learning for Continuous Control with Posterior SamplingICML 2021
- Distributionally Robust Model-based Reinforcement Learning with Large State SpacesAISTATS 2024
- ATraDiff: Accelerating Online Reinforcement Learning with Imaginary TrajectoriesICML 2024
- Is Long Horizon RL More Difficult Than Short Horizon RL?NeurIPS 2020
- Sample-efficient and Scalable Exploration in Continuous-Time RLICLR 2026
- Scalable Policy-Based RL Algorithms for POMDPsNeurIPS 2025
- Planning in Markov Decision Processes with Gap-Dependent Sample ComplexityNeurIPS 2020
- Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative ModelNeurIPS 2020
- Nearly Horizon-Free Offline Reinforcement LearningNeurIPS 2021
- The Sample Complexity of Online Reinforcement Learning: A Multi-model PerspectiveICLR 2026
- Offline Reinforcement Learning with Generative Trajectory PoliciesICML 2026
Related open problems
RL Theory & Markov Decision Processes
Empirical Robustness and Scalability Evaluation of Provably Efficient RL Algorithms
A wide range of theoretical reinforcement learning algorithms offer provable sample-complexity guarantees, yet their empirical validation is almost exclusively restricted to synthetic tabular MDPs with fewer than 30 states. Because these methods have not been evaluated across larger, standardized, or higher-dimensional environments, it remains unknown whether their theoretical efficiency properties hold in practice. Without systematic cross-domain testing, the community lacks evidence on whether provably efficient exploration and representation mechanisms scale beyond toy sandbox problems.
RL Theory & Markov Decision Processes
Reinforcement Learning Algorithms Without Generative Model and Reset Oracles
A wide class of theoretical and model-based RL methods rely on access to a generative model or simulator capable of querying arbitrary state-action pairs and performing instant resets. In physical systems, streaming data settings, and non-resettable environments, arbitrary state querying is impossible, restricting these algorithms to synthetic simulations. Consequently, the theoretical guarantees and policy optimization mechanisms derived under generative oracle assumptions fail completely when deployed in realistic single-trajectory or trajectory-constrained online environments.
RL Theory & Markov Decision Processes
Regret Bounds with Problem-Dependent Constants Removed: Minimax Characterization of the Gap Between Instance-Independent and Instance-Dependent Guarantees
Every one of these bounds is technically instance-independent, but each carries a "constant" — κ, exponential variation budgets, hitting-time factors, (1−γ)^−6, K^n, binomial coefficients — that is itself an instance-dependent quantity scaling exponentially or polynomially-huge on exactly the instances practitioners care about. The result is that published algorithms are provably efficient only on benign instances, and no one knows which of these constants are artifacts of analysis versus intrinsic hardness. Without a theory of which dependence is real, practitioners cannot tell whether a tight-constraint CMDP or a large-state bandit is fundamentally hard or merely badly analyzed.