Timezone: »

 
Poster
Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?
Qiwen Cui · Lin Yang

Tue Dec 08 09:00 PM -- 11:00 PM (PST) @ Poster Session 2 #704
in Poster Session 3 »
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 $\epsilon$-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 $\epsilon$-optimal policy in a $\gamma$-discounted MDP is $O(K/(1-\gamma)^3\epsilon^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.
Keywords: Variational Inference · Generative Models · Probabilistic Methods · Algorithms -> Semi-Supervised Learning; Deep Learning -> Deep Autoencoders; Deep Learning

Author Information

Qiwen Cui (Peking University)
Lin Yang (UCLA)

More from the Same Authors