Research map / Reinforcement learning / MDPs and planning
Contextual Decision Processes with low Bellman rank are PAC-Learnable
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Exploit low Bellman rank with optimistic exploration and Bellman-error-based elimination | OLIVE on CDPs with Bellman factorization · CDPs with Bellman factorization | episodes: \tilde O\left(\frac{M^2H^3K}{\epsilon^2}\log(N\zeta/\delta)\right) | Helped |
| Allow approximate validity and approximate Bellman factorization | OLIVER · CDPs with approximation errors θ and η | suboptimality: \epsilon + 8H\sqrt{M}(\theta+\eta) | Mixed |
| Use infinite policy and value-function classes with finite combinatorial dimensions | OLIVE · CDPs with infinite hypothesis classes | episodes: \tilde O\left(\frac{M^2H^3K^2}{\epsilon^2}\Big(d_{\Pi} + d_{\Gcal} + \log(\zeta/\delta)\Big)\right) | Mixed |
| Use a doubling schedule to guess the Bellman rank | GuessM · CDPs with unknown Bellman rank | episodes: \tilde O\left(\frac{M^2H^3K}{\epsilon^2}\log(N\zeta/\delta)\right) | No clear effect |
| Apply OLIVE to layered MDPs with M states per layer, H layers, and K actions | PAC learning of layered episodic MDPs · Layered episodic MDPs | episodes: n \le cMKH/\epsilon^2 | Mixed |
| Use a tabular MDP model with Bellman rank bounded by the number of states | CDP representation of tabular MDPs · Tabular MDPs | Bellman rank: M = |S| | Helped |
| Use low-rank transition dynamics | CDP representation of low-rank MDPs · Low-rank MDPs | Bellman rank: M | Helped |
| Use reactive value functions in a POMDP with hidden states | CDP representation of reactive POMDPs · Reactive POMDPs | Bellman rank: M = |S| | Helped |
| Use reactive value functions for a system with PSR linear dimension L | CDP representation of PSRs · Predictive State Representations | Bellman rank: LK | Helped |
Closest papers by meaning
- Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics (ICLR 2025 · similarity 0.88)
- Zero-Shot Context Generalization in Reinforcement Learning from Few Training Contexts (NeurIPS 2025 · similarity 0.88)
- Gradual Transition from Bellman Optimality Operator to Bellman Operator in Online Reinforcement Learning (ICML 2025 · similarity 0.88)
- Bayesian Exploration Networks (ICML 2024 · similarity 0.88)
- Enhancing Value Function Estimation through First-Order State-Action Dynamics in Offline Reinforcement Learning (ICML 2024 · similarity 0.87)
- NeoRL: Efficient Exploration for Nonepisodic RL (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.