TY - GEN

T1 - Scalable bilinear π learning using state and action features

AU - Chen, Yichen

AU - Li, Lihong

AU - Wang, Mengdi

PY - 2018/1/1

Y1 - 2018/1/1

N2 - AApproximate linear programming (ALP) represents one of the major algorithmic families to solve large-scale Markov decision processes (MDP). In this work, we study a primal-dual formulation of the ALP, and develop a scalable, model-free algorithm called bilinear π learning for reinforcement learning when a sampling oracle is provided. This algorithm enjoys a number of advantages. First, it adopts (bi)linear models to represent the high-dimensional value function and state-action distributions, using given state and action features. Its run-time complexity depends on the number of features, not the size of the underlying MDPs. Second, it operates in a fully online fashion without having to store any sample, thus having minimal memory footprint. Third, we prove that it is sample-efficient, solving for the optimal policy to high precision with a sample complexity linear in the dimension of the parameter space.

AB - AApproximate linear programming (ALP) represents one of the major algorithmic families to solve large-scale Markov decision processes (MDP). In this work, we study a primal-dual formulation of the ALP, and develop a scalable, model-free algorithm called bilinear π learning for reinforcement learning when a sampling oracle is provided. This algorithm enjoys a number of advantages. First, it adopts (bi)linear models to represent the high-dimensional value function and state-action distributions, using given state and action features. Its run-time complexity depends on the number of features, not the size of the underlying MDPs. Second, it operates in a fully online fashion without having to store any sample, thus having minimal memory footprint. Third, we prove that it is sample-efficient, solving for the optimal policy to high precision with a sample complexity linear in the dimension of the parameter space.

UR - http://www.scopus.com/inward/record.url?scp=85057236822&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85057236822&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85057236822

T3 - 35th International Conference on Machine Learning, ICML 2018

SP - 1305

EP - 1319

BT - 35th International Conference on Machine Learning, ICML 2018

A2 - Dy, Jennifer

A2 - Krause, Andreas

PB - International Machine Learning Society (IMLS)

T2 - 35th International Conference on Machine Learning, ICML 2018

Y2 - 10 July 2018 through 15 July 2018

ER -