Reward-Free Exploration for Reinforcement Learning

By Chi Jin, Akshay Krishnamurthy, Max Simchowitz, Tiancheng Yu. 2020

237 citations recorded by the source corpus.

Exploration is widely regarded as one of the most challenging aspects of reinforcement learning (RL), with many naive approaches succumbing to exponential sample complexity. To isolate the challenges of exploration, we propose a new "reward-free RL" framework. In the exploration phase, the agent first collects trajectories from an MDP $\mathcal{M}$ without a pre-specified reward function. After exploration, it is tasked with computing near-optimal policies under for $\mathcal{M}$ for a collection of given reward functions. This framework is particularly suitable when there are many reward functions of interest, or when the reward function is shaped by an external agent to elicit desired behavior. We give an efficient algorithm that conducts $\tilde{\mathcal{O}}(S^2A\mathrm{poly}(H)/\epsilon^2)$ episodes of exploration and returns $\epsilon$-suboptimal policies for an arbitrary number of reward functions. We achieve this by finding exploratory policies that visit each "significant" state with probability proportional to its maximum visitation probability under any possible policy. Moreover, our planning procedure can be instantiated by any black-box approximate planner, such as value iteration or natural policy gradient. We also give a nearly-matching $\Omega(S^2AH^2/\epsilon^2)$ lower bound, demonstrating the near-optimality of our algorithm in this setting.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Towards Continual Reinforcement Learning: A Review and Perspectives (2020, background): “An ambitious approach then is to discover general purpose goals without any reward signal as in unsupervised RL (Jin et al., 2020; Wang et al., 2020a; Zhang et al., 2021b).”
Provable Self-Play Algorithms for Competitive Reinforcement Learning (2020, methodology): “The proof is almost the same as the proof of Lemma 3.6 in Jin et al. (2020) except that there is no error in estimating r in Jin et al. (2020).”
On the Theory of Reinforcement Learning with Once-per-Episode Feedback (2021, background): “The following is a restatement of Lemma 3.4 from (Jin et al., 2020).”
A Sharp Analysis of Model-based Reinforcement Learning with Self-Play (2020, background): “Jin et al. (2020) study a new paradigm of learning MDPs called reward-free learning, which is also known as the task-agnostic (Zhang et al., 2020b) or reward-agnostic setting.”
Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation (2021, background): “[27] proposed SSTP algorithm in the time-homogeneous setting, which achieves Õ(S(2)AH(2) −2) sample complexity, and matches the minimax lower bound provided in [9] up to logarithmic factors.”
Model-based Adversarial Meta-Reinforcement Learning (2020, background): “[18] aims to compute the near-optimal policies for any reward function by sufficient exploration, while we search for the reward function with the worst suboptimality gap.”
Learning One Representation to Optimize All Rewards (2021, background): “However, policy learning on top of the options is still needed after the task is known.”
Preference-based Reinforcement Learning with Finite-Time Guarantees (2020, methodology): “Our method is based on a synthetic reward function similar to recent literature on RL with rich observations [14, 24] and reward-free RL [23].”
FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs (2020, background): “We focus on the problem of reward-free exploration (Hazan et al., 2019; Jin et al., 2020), where the agent interacts with the environment with no reward signal.”