### Abstract

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.

Original language | English (US) |
---|---|

Title of host publication | 35th International Conference on Machine Learning, ICML 2018 |

Editors | Jennifer Dy, Andreas Krause |

Publisher | International Machine Learning Society (IMLS) |

Pages | 1305-1319 |

Number of pages | 15 |

ISBN (Electronic) | 9781510867963 |

State | Published - Jan 1 2018 |

Event | 35th International Conference on Machine Learning, ICML 2018 - Stockholm, Sweden Duration: Jul 10 2018 → Jul 15 2018 |

### Publication series

Name | 35th International Conference on Machine Learning, ICML 2018 |
---|---|

Volume | 2 |

### Other

Other | 35th International Conference on Machine Learning, ICML 2018 |
---|---|

Country | Sweden |

City | Stockholm |

Period | 7/10/18 → 7/15/18 |

### All Science Journal Classification (ASJC) codes

- Computational Theory and Mathematics
- Human-Computer Interaction
- Software

## Fingerprint Dive into the research topics of 'Scalable bilinear π learning using state and action features'. Together they form a unique fingerprint.

## Cite this

*35th International Conference on Machine Learning, ICML 2018*(pp. 1305-1319). (35th International Conference on Machine Learning, ICML 2018; Vol. 2). International Machine Learning Society (IMLS).