Scalable Bilinear $\pi$ Learning Using State and Action Features

Abstract

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.

References in corpus (5)

• Trust Region Policy Optimization
• Stochastic Variance Reduction Methods for Policy Evaluation
• Proximal Reinforcement Learning: A New Theory of Sequential Decision Making in Primal-Dual Spaces
• Linear Programming for Large-Scale Markov Decision Problems
• Value Function Approximation in Noisy Environments Using Locally Smoothed Regularized Approximate Linear Programs

Cited by in corpus (17)

• AlgaeDICE: Policy Gradient from Arbitrary Experience
• Information-Theoretic Considerations in Batch Reinforcement Learning
• Sample-Optimal Parametric Q-Learning Using Linearly Additive Features
• Reinforcement Learning via Fenchel-Rockafellar Duality
• Feature-Based Q-Learning for Two-Player Stochastic Games
• Off-Policy Evaluation via the Regularized Lagrangian
• State Aggregation Learning from Markov Transition Data
• Efficient Planning in Large MDPs with Weak Linear Function Approximation
• Large-Scale Markov Decision Problems via the Linear Programming Dual
• Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• Faster saddle-point optimization for solving large-scale Markov decision processes
• Unknown mixing times in apprenticeship and reinforcement learning
• A Reduction from Reinforcement Learning to No-Regret Online Learning
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning
• Near Optimal Policy Optimization via REPS
• On Sample Complexity of Projection-Free Primal-Dual Methods for Learning Mixture Policies in Markov Decision Processes
• Voting-Based Multi-Agent Reinforcement Learning for Intelligent IoT