Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?
This provides a sample-efficient model-based reinforcement learning method for problems with linear features, addressing a key bottleneck in RL theory, though it is incremental in extending existing plug-in approaches.
The paper tackles the sample complexity of finding an ε-optimal policy in Markov decision processes with linear additive features, proving that a plug-in solver approach achieves a minimax sample complexity of O(K/(1-γ)^3ε^2), which depends only on feature dimensionality K and not on state or action spaces, under an anchor-state assumption and extended to relaxed settings.
It is believed that a model-based approach for reinforcement learning (RL) is the key to reduce sample complexity. However, the understanding of the sample optimality of model-based RL is still largely missing, even for the linear case. This work considers sample complexity of finding an $ε$-optimal policy in a Markov decision process (MDP) that admits a linear additive feature representation, given only access to a generative model. We solve this problem via a plug-in solver approach, which builds an empirical model and plans in this empirical model via an arbitrary plug-in solver. We prove that under the anchor-state assumption, which implies implicit non-negativity in the feature space, the minimax sample complexity of finding an $ε$-optimal policy in a $γ$-discounted MDP is $O(K/(1-γ)^3ε^2)$, which only depends on the dimensionality $K$ of the feature space and has no dependence on the state or action space. We further extend our results to a relaxed setting where anchor-states may not exist and show that a plug-in approach can be sample efficient as well, providing a flexible approach to design model-based algorithms for RL.