Nearly Minimax Optimal Reward-free Reinforcement Learning

Abstract

We study the reward-free reinforcement learning framework, which is particularly suitable for batch reinforcement learning and scenarios where one needs policies for multiple reward functions. This framework has two phases. In the exploration phase, the agent collects trajectories by interacting with the environment without using any reward signal. In the planning phase, the agent needs to return a near-optimal policy for arbitrary reward functions. We give a new efficient algorithm, \textbf{S}taged \textbf{S}ampling + \textbf{T}runcated \textbf{P}lanning (\algoname), which interacts with the environment at most $O\left(\frac{S^{2}A}{{\epsilon }^2}\text{poly}\log \left(\frac{SAH}{\epsilon }\right)\right)$ episodes in the exploration phase, and guarantees to output a near-optimal policy for arbitrary reward functions in the planning phase. Here, $S$ is the size of state space, $A$ is the size of action space, $H$ is the planning horizon, and $\epsilon$ is the target accuracy relative to the total reward. Notably, our sample complexity scales only \emph{logarithmically} with $H$, in contrast to all existing results which scale \emph{polynomially} with $H$. Furthermore, this bound matches the minimax lower bound $\Omega \left(\frac{S^{2}A}{{\epsilon }^2}\right)$ up to logarithmic factors. Our results rely on three new techniques : 1) A new sufficient condition for the dataset to plan for an $\epsilon$-suboptimal policy; 2) A new way to plan efficiently under the proposed condition using soft-truncated planning; 3) Constructing extended MDP to maximize the truncated accumulative rewards efficiently.

References in corpus (19)

• Reward Constrained Policy Optimization
• Empirical Bernstein Bounds and Sample Variance Penalization
• Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
• Constrained Policy Optimization
• Provably Efficient Maximum Entropy Exploration
• Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning
• Reinforcement Learning with Convex Constraints
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• On Reward-Free Reinforcement Learning with Linear Function Approximation
• Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal
• Fast active learning for pure exploration in reinforcement learning
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• Reward-Free Exploration for Reinforcement Learning
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Task-agnostic Exploration in Reinforcement Learning
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
• Adaptive Reward-Free Exploration

Cited by in corpus (7)

• Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation
• Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning
• Beyond No Regret: Instance-Dependent PAC Reinforcement Learning
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning
• Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings
• Adaptive Multi-Goal Exploration