PaperlayerView exact revision on arXiv

Source-linked AI summary

On Reward-Free Reinforcement Learning with Linear Function Approximation

Ruosong Wang, Simon S. Du, Lin F. Yang, Ruslan Salakhutdinov

arXiv:2006.11274v1cs.LGcs.AImath.OCstat.ML

TL;DR

Reward-free RL separates exploration from planning for a specified reward, but tabular guarantees depend on state and action counts, motivating function approximation. This paper studies linear representations and finds polynomial sample complexity under linear MDP assumptions but an exponential lower bound under the weaker linear Q* assumption.

  • Problem

    Tabular reward-free RL guarantees depend on the numbers of states and actions, motivating the question of provably efficient algorithms with linear function approximation.

    Source: §1 · p. 2

  • Method

    The paper analyzes reward-free RL under linear MDP assumptions, where transitions and rewards are linear in features, and under the weaker linear Q* assumption.

    Source: §1 · p. 2, §2.2 · p. 5

  • Results

    The linear MDP algorithm has sample complexity polynomial in feature dimension and horizon and independent of state and action counts, while linear Q* reward-free RL has an exponential sample lower bound.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    The results establish exponential sample-complexity separations between linear MDP and linear Q* assumptions, and between standard and reward-free RL.

    Source: §1 · p. 3, §5 · p. 11

    The positive result assumes linear representations of both transitions and rewards; the hardness result concerns the weaker linear optimal-Q setting.

    Source: §1 · p. 2, §2.2 · p. 5

Abstract

from arXiv · show

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.

1 Introduction

The paper studies whether reward-free RL can be provably efficient with linear function approximation, motivated by the state-space dependence of tabular guarantees. It gives positive and negative results under different linearity assumptions, including exponential separations in sample complexity.

1 Introduction

  • Reward-free RL separates exploration without a prespecified reward from later planning for a given reward, a setup suited to batch RL and multiple reward functions.Jin et al. [2020] established polynomial sample complexity in the tabular setting, with dependence on states, actions, and horizon.Source: §1 · pp. 1–2
  • The paper addresses the state-space dependence of tabular guarantees by studying linear function approximation, which is needed to generalize in large-state environments.The introduction poses whether provably efficient algorithms are possible in this setting.Source: §1 · p. 2
  • Under the linear MDP assumption, the algorithm outputs ε-optimal policies for an arbitrary number of reward functions using exploration trajectories, with sample complexity polynomial in feature dimension and horizon and independent of states and actions.The assumption requires linear representations of both transitions and rewards.Source: §1 · p. 2
  • Under the weaker linear Q* assumption, reward-free RL requires exponentially many exploration samples, even for deterministic MDPs.By contrast, the paper reports a polynomial sample-complexity upper bound for the linear MDP setting.Source: §1 · pp. 2–3
  • With simulator access, deterministic reward-free RL under the linear Q* assumption has a polynomial sample-complexity upper bound, contrasting with the exponential lower bound without a simulator.The paper presents this as an exponential separation between the generative-model and standard RL settings.Source: §1 · pp. 2–3

1.1 Related Work

  • Earlier work established tabular reward-free guarantees, while standard-RL results for linear Q* required additional assumptions such as nearly deterministic transitions.Jin et al. [2020] asked whether tabular results could extend to function approximation; cited standard-RL bounds included Wen and Van Roy [2013] and Du et al. [2019b, 2020b].Source: §1.1 · pp. 3–4

2 Preliminaries

The preliminaries establish episodic MDP notation, distinguish model-based and value-based linear assumptions, and define reward-free RL as exploration followed by planning from collected data.

2 Preliminaries

  • The notation [N] denotes the set {1, 2, . . . , N}.Source: §2 · p. 4

2.1 Episodic Reinforcement Learning

  • An episodic MDP specifies state and action spaces, stagewise transitions and rewards, and a planning horizon.A policy maps states and time steps to actions and induces a trajectory.Source: §2.1 · p. 4

2.2 Linear Function Approximation

  • Linear MDPs require both transition operators and rewards to be linear in the supplied features, whereas linear Q* requires only the optimal Q-function to be linear.The paper states that the linear Q* assumption is strictly weaker and makes reward-free RL exponentially harder than under the linear MDP assumption.Source: §2.2 · p. 5

2.3 Reward-Free RL

  • Reward-free RL separates reward-independent exploration from planning, where collected data is used to produce an ε-optimal policy for a subsequently supplied reward function.Sample complexity is measured by the number of exploration episodes required.Source: §2.3 · pp. 5–6

3 Reward-Free RL for Linear MDPs

The algorithm uses uncertainty-driven exploration under a linear MDP assumption, then plans from the collected dataset. Its analysis combines a bound on average bonus reward with optimistic Q-function estimates to guarantee near-optimal policies for arbitrary reward functions.

3.1 The Algorithm

  • An exploration-driven reward equal to the UCB bonus divided by H directs sampling toward state-action pairs with greater uncertainty.Dividing by H keeps the reward in [0, 1]; planning fits least-squares Q-function predictors and adds a UCB bonus before choosing the greedy policy.Source: §3.1 · pp. 6–7

3.2 Analysis

  • With probability 1 − δ, the algorithm outputs an ε-optimal policy for an arbitrary number of reward functions satisfying Assumption 2.1 after collecting the specified exploration trajectories.The analysis combines a bound on average cumulative bonus reward with optimistic Q-function estimates.Source: §3.2 · pp. 7–8
  • The analysis bounds the average cumulative reward from using the bonus function divided by H, supporting the claim that exploration reduces uncertainty across state-action pairs.Source: §3.2 · p. 8

4 Lower Bound for Reward-Free RL under Linear Q∗Assumption

The section proves an exponential exploration lower bound for reward-free RL under a linear Q* assumption, even when the feature dimension is polynomial in the horizon. Its hard instance makes the optimal trajectory difficult to identify from exploration data.

Theorem 4.1

  • At least Ω(2^H) exploration samples are required to find a 0.1-optimal policy with probability at least 0.9, even for deterministic systems with d = poly(H).The result also applies to general MDPs because deterministic systems are a special case.Source: §4 · p. 9

Hard instance

  • The instance has H levels, two actions, and a unique optimal trajectory; the feature extractor assigns near-orthogonal unit features to state-action pairs.The construction’s optimal Q-function is exactly linear, unlike the approximately linear construction in Du et al. [2020a].Source: §4 · pp. 9–10

Proof sketch

  • With at most 2^H/100 sampled trajectories, the algorithm misses the special state-action path with probability at least 0.9.Before reaching the special state, the fixed feature extractor gives the algorithm the same feedback across the hard instances.Source: §4 · p. 11
  • Conditioned on missing the special state, the algorithm identifies the required final action with probability at most 0.5, leaving success at most 0.6.Thus it cannot meet the theorem’s 0.9 success requirement for a 0.1-optimal policy.Source: §4 · p. 11

5 Conclusion

The paper establishes positive and negative results for reward-free RL with linear function approximation, yielding three exponential sample-complexity separations.

Conclusion

  • The results imply exponential separations between linear MDPs and linear Q*, standard RL and reward-free RL, and simulator and non-simulator queries.The paper identifies generalization to broader function classes as a future direction.Source: §5 · p. 11

A Missing Proofs in Section 3

The passage indicates that the proof uses suitable choices of two constants.

Missing proofs

A.1 Proof of Lemma 3.1

The appendix proves Lemma 3.1 using concentration events and an induction argument. It adapts a prior proof to episode-dependent rewards while retaining the same value-function class.

Proof of Lemma 3.1

  • A concentration event E holds with probability at least 1 − δ/4 under Assumption 2.1.The proof also uses an Azuma–Hoeffding event E′ with probability at least 1 − δ/4.Source: §A.1 · pp. 15, 18
  • The argument adapts Jin et al. [2019] because rewards differ across episodes, while the value function remains in the same function class.The proof states that the remaining steps follow similarly to the cited work.Source: §A.1 · p. 15

First Part

  • The first part of the lemma is proved by induction on h.The induction begins at h = H + 1.Source: §A.1 · p. 17

A.2 Proof of Lemma 3.2

The proof treats the episode-wise deviations as a bounded martingale difference sequence and applies Azuma–Hoeffding concentration.

  • The deviations form a martingale difference sequence because each reward function depends only on data from earlier episodes.Source: §A.2 · p. 18
  • Each deviation has absolute value at most H almost surely.Source: §A.2 · p. 18
  • Azuma–Hoeffding then yields a high-probability concentration bound for the sequence.The stated probability is at least 1 − δ/8.Source: §A.2 · p. 18

A.3 Proof of Lemma 3.3

The proof establishes an upper bound on the optimal Q-values by combining a transition-value confidence bound with backward induction.

  • A transition-value estimate is bounded using a confidence term of 2u_h(s, a).Source: §A.3 · p. 19
  • The proof uses backward induction over the horizon to show that the optimal Q-value is no greater than the constructed Q-value.The induction assumes the bound at step h+1 and proceeds to step h.Source: §A.3 · p. 19
  • At step h, h+1(s,a,r) is bounded above by (w_h)^Tφ(s,a) + r_h(s,a) + β·||φ(s,a)||_(Λ_h)^−1, combining the three displayed terms.Source: §A.3 · p. 19

A.4 Proof of Theorem 3.1

The theorem proof shows that the linear-MDP algorithm returns an ε-optimal policy with a polynomial episode count. The following simulator result gives exact planning under a linear optimal-Q assumption in deterministic systems.

A.4 Proof of Theorem 3.1

  • The proof bounds the policy's value gap by a term proportional to H times the expected optimal value under a scaled reward.Source: §A.4 · p. 20
  • K = c_K d^3H^6 log(dHδ^-1ε^-1)/ε^2 episodes suffices for an ε-optimal policy.The passage specifies a sufficiently large constant c_K.Source: §A.4 · p. 20

B Reward-Free RL under Linear Q∗Assumption with a Simulator

C Missing Proofs in Section 4

The proof constructs a hard instance with nearly orthogonal features and shows that limited exploration can leave the algorithm unable to identify an optimal action.

Related papers

Loading 2006.11274v1…