Branching Reinforcement Learning
Not on the map. Why?
Abstract (arXiv)
In this paper, we propose a novel Branching Reinforcement Learning (Branching RL) model, and investigate both Regret Minimization (RM) and Reward-Free Exploration (RFE) metrics for this model. Unlike standard RL where the trajectory of each episode is a single H-step path, branching RL allows an agent to take multiple base actions in a state such that transitions branch out to multiple successor states correspondingly, and thus it generates a tree-structured trajectory. This model finds important applications in hierarchical recommendation systems and online advertising. For branching RL, we establish new Bellman equations and key lemmas, i.e., branching value difference lemma and branching law of total variance, and also bound the total variance by only O(H2) under an exponentially-large trajectory. For RM and RFE metrics, we propose computationally efficient algorithms BranchVI and BranchRFE, respectively, and derive nearly matching upper and lower bounds. Our results are only polynomial in problem parameters despite exponentially-large trajectories.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 14 of its 22 references that are in the map. First posted on arXiv 16 Feb 2022.
Builds on
14 of 22 references.
References · 14
- 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
- 2018Is Q-learning Provably Efficient?cited by 485
- 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
- 2020Reward-Free Exploration for Reinforcement Learningcited by 177
- 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
- 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
- 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
- 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
- 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
- 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
- 2020Fast active learning for pure exploration in reinforcement learningcited by 92
- 2020Adaptive Reward-Free Explorationcited by 77
2 more
- 2016On Lower Bounds for Regret in Reinforcement Learningcited by 39
- 2020Nearly Minimax Optimal Reward-free Reinforcement Learningcited by 26
Built on by
Citing papers per year: 2025: 1.
1 paper.