On Reward-Free Reinforcement Learning with Linear Function Approximation

By Ruosong Wang, Simon Shaolei Du, Lin F. Yang, Ruslan Salakhutdinov. 2020

119 citations recorded by the source corpus.

Reward-free reinforcement learning (RL) is a framework which is suitable for both the batch RL setting and the setting where there are many reward functions of interest. During the exploration phase, an agent collects samples without using a pre-specified reward function. After the exploration phase, a reward function is given, and the agent uses samples collected during the exploration phase to compute a near-optimal policy. Jin et al. [2020] showed that in the tabular setting, the agent only needs to collect polynomial number of samples (in terms of the number states, the number of actions, and the planning horizon) for reward-free RL. However, in practice, the number of states and actions can be large, and thus function approximation schemes are required for generalization. In this work, we give both positive and negative results for reward-free RL with linear function approximation. We give an algorithm for reward-free RL in the linear Markov decision process setting where both the transition and the reward admit linear representations. The sample complexity of our algorithm is polynomial in the feature dimension and the planning horizon, and is completely independent of the number of states and actions. We further give an exponential lower bound for reward-free RL in the setting where only the optimal $Q$-function admits a linear representation. Our results imply several interesting exponential separations on the sample complexity of reward-free RL.

Subfields: Artificial Intelligence, Computer Networks and Communications, 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 Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

A Sharp Analysis of Model-based Reinforcement Learning with Self-Play (2020, result): “Since MDPs are special cases of Markov games, our algorithm VI-Zero directly applies to the single-agent setting, and yields a sample complexity similar to existing results (Zhang et al., 2020b; Wang et al., 2020).”
What are the Statistical Limits of Offline RL with Linear Function Approximation? (2020, background): “The condition that the optimal Q -function is only approximately linear is crucial for the correctness of the hardness result in Du et al. [2020] The techniques in [Du et al., 2020] are later generalized to other settings, including [Kumar et al., 2020, Wang et al., 2020, Mou et al., 2020].”
Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation (2021, methodology): “…φ i ( s (cid:48) | s, a ) , i.e., P ( s (cid:48) | s, a ) A similar but notably different deﬁnition (i.e., linear MDPs [21, 10]) has been used in [18], which assumes that P ( s (cid:48) | s, a ) = (cid:104) φ ( s, a ) , µ ( s (cid:48) ) (cid:105) and r h = (cid:104) φ ( s, a ) , θ h (cid:105) ,…”