Research map / Reinforcement learning / MDPs and planning
State-free Reinforcement Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces state-free RL in tabular episodic MDPs, a black-box reduction (SF-RL) that prunes unreachable states without knowing the state space, plus an improved confidence-set design that removes the sqrt(|S^Pi|) restart overhead for adversarial MDPs.
Problem
Standard RL algorithms need the state space size as a hyperparameter for exploration bonuses and confidence sets, and their regret scales with |S|; the paper asks whether regret can depend only on the reachable state set S^Pi without knowing S.
Approach
Maintain a dynamically pruned state space of identified epsilon-reachable states plus H absorbing auxiliary states, run any black-box MDP algorithm on it (restarting when the pruned space grows), and for adversarial MDPs use per-state-visit-time confidence intervals so that restarts do not discard transition information.
Key results
- SF-RL achieves regret O(reg(|S^{Pi,eps}|+H, |A|, H, log(...)) sqrt(|S^{Pi,eps}| T) + eps H |S^Pi| T) for any black-box ALG, with no knowledge of S.
- With UOB-REPS as ALG and the new confidence sets, the adversarial-MDP regret is O(H|S^{Pi,eps}| sqrt(|A| T log(...)) + eps H |S^Pi| T), which matches the best known non-state-free bound.
- UCBVI can be made fully state-free by allocating confidence per state by arrival index, giving regret O(H sqrt(|S^Pi||A|T log(...))) without knowledge of S.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply the SF-RL black-box reduction with epsilon-pruned states | Black-box RL algorithm ALG · State-free RL, general stochastic or adversarial MDP | regret upper bound: reg\left(|\mathcal{S}^{\Pi, \epsilon}|+H, |\mathcal{A}|, H , \log\left( { H|\mathcal{S}^{\Pi, \epsilon}||\mathcal{A}|T}/ | Mixed |
| Retain transition information across restarts with the new confidence-set design | SF-RL with UOB-REPS · State-free adversarial MDP | regret upper bound: improves the regret guarantee of SF-RL by a $\sqrt{|\mathcal{S}^{\Pi, \epsilon}|}$ term | Helped |
| Use UCBVI without knowing the reachable state set | UCBVI · Stochastic MDP | regret upper bound: \sqrt{{\log(|\mathcal{S}|)} /{\log(|\mathcal{S}^\pi|)}} | Hurt |
| Allocate UCBVI confidence sequentially by state arrival time | UCBVI · Stochastic MDP | regret upper bound | Helped |
Surprising findings
- Standard adversarial MDP analyses cannot avoid polynomial dependence on |S| even when only |S^Pi| states are reachable.
Limitations
- Restarting the black-box algorithm when the pruned space grows costs a sqrt(|S^{Pi,eps}|) factor in the basic SF-RL bound.
- Results are for tabular MDPs; extension to function approximation is left open.
- Regret bound with epsilon > 0 includes an additional term eps H |S^Pi| T that requires tuning or a choice of epsilon.
Experimental setup
Metrics: regret bound
Baselines: UCBVI UOB-REPS
Builds on: UCBVI UOB-REPS SF-RL
Closest papers by meaning
- NeoRL: Efficient Exploration for Nonepisodic RL (NeurIPS 2024 · similarity 0.87)
- Towards General-Purpose Model-Free Reinforcement Learning (ICLR 2025 · similarity 0.86)
- Regret-Free Reinforcement Learning for Temporal Logic Specifications (ICML 2025 · similarity 0.86)
- How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approach (NeurIPS 2024 · similarity 0.86)
- Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds (ICLR 2025 · similarity 0.86)
- Computational Hardness of Reinforcement Learning with Partial $q^{\pi}$-Realizability (NeurIPS 2025 · similarity 0.85)
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.