Scalable Bilinear π Learning Using State and Action Features

By Yichen Chen, Lihong Li, Mengdi Wang. 2018

47 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Nan Jiang
2. Sergey Levine
3. Ofir Nachum
4. Lihong Li
5. Bo Dai
6. Alekh Agarwal
7. Dale Schuurmans
8. Qiang Liu

In Computer Networks and Communications

1. Nan Jiang
2. Alekh Agarwal
3. Bo Dai
4. Ofir Nachum
5. Lin F. Yang
6. Lihong Li
7. J. Langford
8. Gergely Neu

In Management Science and Operations Research

1. Ofir Nachum
2. Nan Jiang
3. Lihong Li
4. Bo Dai
5. Nathan Kallus
6. Alekh Agarwal
7. Masatoshi Uehara
8. Sergey Levine

Citations in the corpus

• AlgaeDICE: Policy Gradient from Arbitrary Experience (2019, background): “Several recent works (e.g., Chen and Wang, 2016; Wang, 2017; Dai et al., 2018a,b; Chen et al., 2018; Lee and He, 2018) also considered saddle-point formulations for policy improvement, derived from fundamentally different perspectives.”
• Information-Theoretic Considerations in Batch Reinforcement Learning (2019, background): “, that T̂F being a contraction (Gordon, 1995; Szepesvári & Smart, 2004; Lizotte, 2011; Pires & Szepesvári, 2016)), and can instead take the form of requiring another function class to realize other objects of interest, such as state distributions (Chen et al., 2018; Liu et al., 2018).”
• A Kernel Loss for Solving the Bellman Equation (2019, background): “Note that there exist other saddle-point formulations for RL, which so far have focused on finite-state MDPs or linear value function approximation (Chen et al., 2018; Wang, 2017).”
• Sample-Optimal Parametric Q-Learning Using Linearly Additive Features (2019, methodology): “Chen et al. (2018) proposes a primal-dual method for policy learning that uses linear models and state-action features for both the value and state-action distribution.”
• Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches (2018, background): “There are model-free algorithms that elude our definition (for example, ones that approximate the state-action distributions (Chen et al., 2018; Liu et al., 2018)), although these algorithms do not address the exploration setting.”
• Faster saddle-point optimization for solving large-scale Markov decision processes (2019, methodology): “These conditions enable us to optimize y over the probability simplex ∆ = ∆ [ M ] and to formulate our relaxed saddle-point problem as e e The relaxed optimization problem above has been studied before by Lakshminarayanan and Bhatnagar (2015); Lakshminarayanan et al. (2018), and Chen et al. (2018).”
• Off-Policy Evaluation via the Regularized Lagrangian (2020, background): “Another line of work, more similar to the present paper, is to optimize the Lagrangian of the linear program that characterizes the value function [2, 4, 29].”