RL Theory & Markov Decision Processes
Reinforcement Learning Algorithms Without Generative Model and Reset Oracles
Generated automatically from the limitations stated in 7 papers (ICML, ALT, ICLR), listed under Evidence. It is not a paper, and it does not come from papers submitted to CSPaper.
The problem
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.
Why it matters
Enables theoretical RL algorithms and model-based planners to operate directly on physical hardware and uncontrollable streaming processes without requiring handcrafted simulation resets or arbitrary state sampling.
Ways to approach it
Prior-work checks are free with an account. Results someone already ran are shown to everyone.
- 1
Trajectory-constrained dynamic programming: Implement algorithms that currently require generative query access (such as robust MDP solvers or value-iteration variants) using forward-reachable state buffers collected via online exploration, measuring sample efficiency, regret, and Bellman error against generative-oracle baselines.
- 2
Optimistic exploratory exploration without resets: Develop and evaluate exploration bonuses (e.g., count-based or variance-based intrinsic rewards) to replace arbitrary state sampling in policy gradient and value estimation routines, measuring the degradation in policy return when reset access is systematically removed in standard continuous control environments.
- 3
Relaxing reset assumptions via reachability regularization: Formulate policy updates that account for state-visitation distribution shift under single-trajectory execution without unichain assumptions, measuring convergence rates and policy optimality gaps on weakly communicating environments.
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
Strictly online single-trajectory learning in non-communicating environments faces known exponential worst-case sample complexity lower bounds, which could force the method to reintroduce restrictive mixing or reachability assumptions that limit empirical novelty.
Evidence
Each paper's own statement of the limitation, verbatim.
- Sample Complexity Bounds for Linear Constrained MDPs with a Generative ModelALT 2026
Requires a generative model (simulator) capable of querying arbitrary state-action pairs in the coreset, excluding strictly online or reward-free exploration settings.
- Reinforcement Learning for Reachability: Guaranteeing Asymptotic OptimalityICML 2026
Requires a generative simulator with reset capabilities rather than learning strictly from an uncontrollable online trajectory.
- Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPsICLR 2026
Requires access to a generative model simulator that can query arbitrary state-action pairs, failing in purely online or trajectory-based exploration settings.
- Near-Optimal Sample Complexities of Divergence-based S-rectangular Distributionally Robust Reinforcement LearningAISTATS 2026
Requires access to a generative model (simulator) that can independently sample next states for any arbitrary state-action pair.
- Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity AnalysisICML 2026
Requires access to a generative model (sampling oracle from nominal transition kernels) rather than handling online exploration or fixed offline datasets.
- Beyond the Bellman Recursion: A Pontryagin-Guided Framework for Non-Exponential DiscountingICML 2026
Requires a differentiable simulator or learned differentiable dynamics model capable of reverse-mode pathwise differentiation (BPTT).
- Offline Actor-Critic for Average Reward MDPsNeurIPS 2025
Requires the 'unichain' assumption where every stationary policy must induce a single recurrent class.
Nearest existing work
- Model-Based Reinforcement Learning with a Generative Model is Minimax OptimalCOLT 2020
- Necessary and Sufficient Oracles: Toward a Computational Taxonomy for Reinforcement LearningCOLT 2025
- Replicable Reinforcement LearningNeurIPS 2023
- Provably Efficient Maximum Entropy ExplorationICML 2019
- Predictable MDP Abstraction for Unsupervised Model-Based RLICML 2023
- Optimistic Exploration in Reinforcement Learning Using Symbolic Model EstimatesNeurIPS 2023
- Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation LearningCOLT 2025
- Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation LearningCOLT 2025
- Replicability in Reinforcement LearningNeurIPS 2023
- Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited RevisitingNeurIPS 2021
- Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value FunctionsCOLT 2025
- The Role of Environment Access in Agnostic Reinforcement Learning (Extended Abstract)COLT 2025
- Efficient Model-Based Reinforcement Learning Through Optimistic Thompson SamplingICLR 2025
- Efficiently Solving Discounted MDPs via Predictions with Unknown Prediction ErrorsICML 2026
- Blending Imitation and Reinforcement Learning for Robust Policy ImprovementICLR 2024
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
Sample-Efficient Reinforcement Learning Under Markovian Trajectory Sampling Without a Generative Model
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.
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.