Approximate 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 $\pi$ 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.

本文介绍了一种基于 Approximate linear programming (APL) 的算法 ——bilinear pi learning，在采样 oracle 下用于强化学习，并证明了它具有可扩展性、在线实时性和样本效率等多种优势。