Open Problems

RL Theory & Markov Decision Processes

Empirical Robustness and Scalability Evaluation of Provably Efficient RL Algorithms

Scope to testOpen
Possible candidate · 3/5 runs10 papers report this30% from 2025+

Generated automatically from the limitations stated in 10 papers (ICML, AISTATS, NeurIPS), listed under Evidence. It is not a paper, and it does not come from papers submitted to CSPaper.

The problem

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.

Why it matters

Provides the first systematic empirical baseline determining whether theoretical RL algorithms retain their sample-efficiency guarantees in non-toy settings. Establishes empirical benchmarks that identify practical computational and statistical failure modes in theoretical algorithm design.

Ways to approach it

Prior-work checks are free with an account. Results someone already ran are shown to everyone.

  1. 1

    Implement a representative set of theoretical RL algorithms (such as reward-free exploration, low-rank MDP algorithms, and optimistic value iteration variants) and evaluate them across parameterized benchmark environments (e.g., scalable bsuite tasks and synthetic MDPs with state spaces varying from $10$ to $10^4$) to measure empirical sample efficiency and computational runtime as dimensions grow.

  2. 2

    Evaluate standard empirical relaxations (e.g., linear and kernel feature representations) of these theoretical methods against standard empirical RL baselines across continuous-state control benchmarks to measure policy performance and sample complexity gaps.

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.

Free · 3 checks per day

Why it might fail

Several theoretical algorithms rely on operations (such as optimal design over entire policy spaces) whose computational complexity is fundamentally exponential in the horizon or state size, making execution on larger benchmarks intractable without altering the underlying algorithms.

Evidence

Each paper's own statement of the limitation, verbatim.

Show all 10 papers

Nearest existing work

Related open problems

RL Theory & Markov Decision Processes

Barrier to removeOpen

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.

Strong candidate · 4/5 runs8 papers report this50% from 2025+

RL Theory & Markov Decision Processes

Barrier to removeOpen

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.

Possible candidate · 2/5 runs7 papers report this100% from 2025+

RL Theory & Markov Decision Processes

Effect to explainOpen

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.

Possible candidate · 1/2 runs7 papers report this25% from 2025+
Generated automatically, not curated by hand. Automated prior-work checks catch about a third of existing work, so treat this problem as a lead to investigate.