Non-Parametric Approximate Linear Programming for MDPs

By Jason Pazis, Ronald E. Parr. 2011

31 citations recorded by the source corpus.

The Approximate Linear Programming (ALP) approach to value function approximation for MDPs is a parametric value function approximation method, in that it represents the value function as a linear combination of features which are chosen a priori. Choosing these features can be a difficult challenge in itself. One recent effort, Regularized Approximate Linear Programming (RALP), uses L1 regularization to address this issue by combining a large initial set of features with a regularization penalty that favors a smooth value function with few non-zero weights. Rather than using smoothness as a backhanded way of addressing the feature selection problem, this paper starts with smoothness and develops a non-parametric approach to ALP that is consistent with the smoothness assumption. We show that this new approach has some favorable practical and analytical properties in comparison to (R)ALP.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Numerical Analysis

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. Sergey Levine
2. Bo Dai
3. Lihong Li
4. Scott Niekum
5. Ofir Nachum
6. Pieter Abbeel
7. Gerhard Neumann
8. Le Song

In Computational Theory and Mathematics

1. Gerhard Neumann
2. Herke Van Hoof
3. Bo Dai
4. Jan Peters
5. Lihong Li
6. Marek Petrik
7. Le Song
8. Scott Niekum

In Numerical Analysis

1. Bo Dai
2. Jan Peters
3. Marek Petrik
4. Le Song
5. Gerhard Neumann
6. Scott Niekum
7. Niao He
8. Albert Eaton Shaw

Citations in the corpus

• Boosting the Actor with Dual Critic (2017, methodology): “…of Bellman optimality equation and its duality have been utilized for (approximate) planning problem (de Farias and Roy, 2004; Wang et al., 2008; Pazis and Parr, 2011; O’Donoghue et al., 2011; Malek et al., 2014; Cogill, 2015), in which the transition probability of the MDP is known and the…”
• Active Reward Learning from Critiques (2018, methodology): “Therefore, we are exploring different methods for efficient MCMC sampling such as using Hamiltonian dynamics [16] and for fast approximation of an MDP’s value function such as Non-Parametric ALP [17].”
• Bayesian Robust Optimization for Imitation Learning (2020, methodology): “Future work also includes investigating natural extensions of our work to continuous state and action spaces such as optimizing the BROIL objective via policy gradient methods [50, 52] or approximate linear programming [17, 38, 39].”
• Learning of Non-Parametric Control Policies with High-Dimensional State Features (2015, methodology): “Another non-parametric method, proposed by Pazis and Parr [2011], assumes the value function is Lipschitz.”
• Non-parametric Policy Search with Limited Information Loss (2017, methodology): “The approximate linear programming algorithm, proposed by Pazis and Parr (2011), does not use kernels.”