# State-free Reinforcement Learning

arXiv: https://arxiv.org/abs/2409.18439 · HTML: https://mlsanity.com/paper/2409.18439/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 39 of its 49 references that are in the map.
- First posted on arXiv 27 Sep 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 39)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [Learning-Rate-Free Learning by D-Adaptation](https://mlsanity.com/paper/2301.07733/) (2023)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon](https://mlsanity.com/paper/2009.13503/) (2020)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule](https://mlsanity.com/paper/2302.12022/) (2023)
- [Provably Efficient Q-Learning with Low Switching Cost](https://mlsanity.com/paper/1905.12849/) (2019)
- [Model Selection in Contextual Stochastic Bandit Problems](https://mlsanity.com/paper/2003.01704/) (2020)
- [Follow the Leader If You Can, Hedge If You Must](https://mlsanity.com/paper/1301.0534/) (2013)
- [Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning](https://mlsanity.com/paper/1802.04020/) (2018)
- [Model selection for contextual bandits](https://mlsanity.com/paper/1906.00531/) (2019)
- [Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning](https://mlsanity.com/paper/2110.04645/) (2021)
- [Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses](https://mlsanity.com/paper/2107.08346/) (2021)
- [Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs](https://mlsanity.com/paper/2006.08040/) (2020)
- [Making SGD Parameter-Free](https://mlsanity.com/paper/2205.02160/) (2022)
- [Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap](https://mlsanity.com/paper/2102.04692/) (2021)
- [UCB Momentum Q-learning: Correcting the bias without forgetting](https://mlsanity.com/paper/2103.01312/) (2021)
- [Settling the Sample Complexity of Online Reinforcement Learning](https://mlsanity.com/paper/2307.13586/) (2023)
- [Beyond No Regret: Instance-Dependent PAC Reinforcement Learning](https://mlsanity.com/paper/2108.02717/) (2021)
- [Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency](https://mlsanity.com/paper/2302.10371/) (2023)
- [Parameter-free online learning via model selection](https://mlsanity.com/paper/1801.00101/) (2017)
- [Planning in Markov Decision Processes with Gap-Dependent Sample Complexity](https://mlsanity.com/paper/2006.05879/) (2020)
- [Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/2107.01264/) (2021)

## Abstract (arXiv)

In this work, we study the textitstate-free RL problem, where the algorithm does not have the states information before interacting with the environment. Specifically, denote the reachable state set by S^Pi :=  s|maxπ∈ PiqP, π(s)>0 , we design an algorithm which requires no information on the state space S while having a regret that is completely independent of S and only depend on S^Pi. We view this as a concrete first step towards textitparameter-free RL, with the goal of designing RL algorithms that require no hyper-parameter tuning.