The Linear Programming Approach to Approximate Dynamic Programming

By D. Farias, Benjamin Van Roy. 2003

812 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Management Information Systems, Management Science and Operations Research, Mathematical Optimization

How researchers see this paper

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

In Computer Networks and Communications

In Management Information Systems

In Management Science and Operations Research

In Mathematical Optimization

Citations in the corpus

Reinforcement Learning via Fenchel-Rockafellar Duality (2020, background): “…for its potential ability to circumvent the optimization challenges of DP-based approaches in exchange for more mature and well-studied techniques associated with convex optimization (De Farias and Van Roy, 2003; Wang et al., 2007; Chen and Wang, 2016; Wang, 2017; Bas-Serrano and Neu, 2019).”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, methodology): “This is a dimensionality reduction and generalization strategy that, in the no uncertainty case, has theoretical guarantees [25, 82], and has been used successfully in continuous control [109, 110, 66, 67, 60].”
Algorithm-Directed Exploration for Model-Based Reinforcement Learning in Factored MDPs (2002, background): “In general, there is no guarantee of the quality of the approximation ∑k j=1 wjhj obtained by such approach, but recent work [9] on the discounted reward case provides some analysis of the error relative to that of the best possible approximation in the subspace.”
Interpretable Optimal Stopping (2018, methodology): “We use 500 inner samples, as in Desai et al. (2012b). We vary the number of stocks as n= 4,8,16 and the initial price of all assets as p̄= 90,100,110.”
Reinforcement learning for control: Performance, stability, and deep approximators (2018, background): “The works of de Farias and Roy (2003); Wang et al. (2014); Beuchat et al. (2016) devise LP approaches to ADP by formulating linear optimization problems whose solution corresponds to the solution of the optimal control problem (2)-(3) for γ ∈ (0 , 1).”
Offline Policy Selection under Uncertainty (2020, background): “…= 0 can be understood as matching the two distributions (1 − γ ) µ 0 ( s ) π ( a | s ) + γ · P π ∗ d ( s, a ) and d ( s, a ) in terms of their embeddings (Smola et al., 2007), which is a generalization of the approximation methods in (De Farias and Van Roy, 2003; Lakshminarayanan et al., 2017).”
Multiagent Planning with Factored MDPs (2001, result): “There is, in general, no guarantee as to the quality of the approximation : ;D * , but recent work of de Farias and Van Roy [3] provides some analysis of the error relative to that of the best possible approximation in the subspace, and some guidance as to selecting the 2 ’s so as to improve the qua”
Efficient Sequential Decision Making (2017, methodology): “The first theoretical analysis of ALP methods, Farias and Van Roy [19], analyzed the discounted primal LP (4.”
Dynamic Multipriority Patient Scheduling for a Diagnostic Resource (2008, background): “However, in approximate DP, it is well known (see Adelman (2004), de Farias and Roy (2003)) that this is not the case but the nature of the dependence of the optimal solution on α is not very well understood.”
Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time (2017, methodology): “The nonlinear Bellman equation is equivalent to the following |S|× ( ) linear programming problem (see [26] Section 6.9 and the paper [12]): where q ∈ ℜ |S| is an arbitrary vector of probability distribution satisfying e ⊤ q = 1 and q > 0, P a ∈ ℜ |S|×|S| is matrix whose ( i, j )-th entry equals to…”