Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning
We introduce SCAL, an algorithm designed to perform efficient exploration-exploitation in any unknown weakly-communicating Markov decision process (MDP) for which an upper bound $c$ on the span of the optimal bias function is known. For an MDP with $S$ states, $A$ actions and $\Gamma \leq S$ possible next states, we prove a regret bound of $\widetilde{O}(c\sqrt{\Gamma SAT})$, which significantly improves over existing algorithms (e.g., UCRL and PSRL), whose regret scales linearly with the MDP diameter $D$. In fact, the optimal bias span is finite and often much smaller than $D$ (e.g., $D=\infty$ in non-communicating MDPs). A similar result was originally derived by Bartlett and Tewari (2009) for REGAL.C, for which no tractable algorithm is available. In this paper, we relax the optimization problem at the core of REGAL.C, we carefully analyze its properties, and we provide the first computationally efficient algorithm to solve it. Finally, we report numerical simulations supporting our theoretical findings and showing how SCAL significantly outperforms UCRL in MDPs with large diameter and small span.
Code (1)
Tasks
Efficient Explorationreinforcement-learningReinforcement LearningReinforcement Learning (RL)Similar Papers 제목 키워드 기반
Group Entropy-Controlled Policy Optimization
Entropy control has become an effective tool in reinforcement learning (RL) of large language models (LLMs), helping balance exploration-exploitation trade-off during alignment process. Such RL paradigm is often conducte…
Reinforcement LearningInstruction FollowingCode GenerationToken Hidden Reward: Steering Exploration-Exploitation in Group Relative Deep Reinforcement Learning
Reinforcement learning with verifiable rewards has significantly advanced the reasoning capabilities of large language models, yet how to explicitly steer training toward exploration or exploitation remains an open probl…
Reinforcement LearningDecoupled Exploration and Exploitation Policies for Sample-Efficient Reinforcement Learning
Despite the close connection between exploration and sample efficiency, most state of the art reinforcement learning algorithms include no considerations for exploration beyond maximizing the entropy of the policy. In th…
continuous-controlContinuous Controlreinforcement-learningReinforcement Learning+1In-context Exploration-Exploitation for Reinforcement Learning
In-context learning is a promising approach for online policy learning of offline reinforcement learning (RL) methods, which can be achieved at inference time without gradient optimization. However, this method is hinder…
Bayesian InferenceBayesian OptimizationIn-Context Learningreinforcement-learning+2Exploration vs Exploitation: Rethinking RLVR through Clipping, Entropy, and Spurious Reward
This paper examines the exploration-exploitation trade-off in reinforcement learning with verifiable rewards (RLVR), a framework for improving the reasoning of Large Language Models (LLMs). Recent studies suggest that RL…
Reinforcement LearningMathematical Reasoning