Online RL in Linearly qπ-Realizable MDPs Is as Easy as in Linear MDPs If You Learn What to Ignore

We consider online reinforcement learning (RL) in episodic Markov decision processes (MDPs) under the linear -realizability assumption, where it is assumed that the action-values of all policies can be expressed as linear functions of stateaction features. This class is known to be more general than linear MDPs, where the transition kernel and the reward function are assumed to be linear functions of the feature vectors. As our first contribution, we show that the difference between the two classes is the presence of states in linearly -realizable MDPs where for any policy, all the actions have approximately equal values, and skipping over these states by following an arbitrarily fixed policy in those states transforms the problem to a linear MDP. Based on this observation, we derive a novel (computationally inefficient) learning algorithm for linearly -realizable MDPs that simultaneously learns what states should be skipped over and runs another learning algorithm on the linear MDP hidden in the problem. The method returns an -optimal policy after polylog( , )/ 2 interactions with the MDP, where is the time horizon and is the dimension of the feature vectors, giving the first polynomial-sample-complexity online RL algorithm for this setting. The results are proved for the misspecified case, where the sample complexity is shown to degrade gracefully with the misspecification error. any ∈ [A], P , , is the distribution over the histories when first action is used in state , after which policy is followed. E• is the expectation operator corresponding to a distribution P• (e.g., E , is the expectation with respect to P , ). The state-and action-value functions and are defined as the expected total reward within the first episode while is used: Let ★ ∈ Π be an optimal policy, satisfying ★ ( , ) = sup ∈Π ( , ) = sup ∈all policies ( , ) for all ( , ) ∈ S × [A]. Let ★ ( , ) = ★ ( , ) and ★ ( ) = sup ′ ∈ [ A ] ★ ( , ) for all ( , ).