HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Performance Bounds in $L_p$ norm for Approximate Value Iteration

Rémi Munos 1
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
Abstract : Approximate Value Iteration (AVI) is a method for solving large Markov Decision Problems by approximating the optimal value function with a sequence of value function representations $V_n$ processed according to the iterations $V{n+1} = \mathcal{ATV}_n$ where $\mathcal{T}$ is the so-called Bellman operator and $\mathcal{A}$ an approximation operator, which may be implemented by a Supervised Learning (SL) algorithm. Usual bounds on the asymptotic performance of AVI are established in terms of the $L\infty$-norm approximation errors induced by the SL algorithm. However, most widely used SL algorithms (such as least squares regression) return a function (the best fit) that minimizes an empirical approximation error in $L_p$-norm $(p\geq1)$. In this paper, we extend the performance bounds of AVI to weighted $L_p$-norms, which enables to directly relate the performance of AVI to the approximation power of the SL algorithm, hence assuring the tightness and pratical relevance of these bounds. The main result is a performance bound of the resulting policies expressed in terms of the $L_p$-norm errors introduced by the successive approximations. The new bound takes into account a concentration coefficient that estimates how much the discounted future-state distributions starting from a probability measure used to assess the performance of AVI can possibly differ from the distribution used in the regression operation. We illustrate the tightness of the bounds on an optimal replacement problem.
Document type :
Journal articles
Complete list of metadata

Contributor : Rémi Munos Connect in order to contact the contributor
Submitted on : Monday, January 15, 2007 - 5:46:28 PM
Last modification on : Thursday, January 20, 2022 - 4:17:14 PM
Long-term archiving on: : Wednesday, April 7, 2010 - 2:12:09 AM


Files produced by the author(s)




Rémi Munos. Performance Bounds in $L_p$ norm for Approximate Value Iteration. SIAM Journal on Control and Optimization, Society for Industrial and Applied Mathematics, 2007, 46 (2), pp.541-561. ⟨10.1137/040614384⟩. ⟨inria-00124685⟩



Record views


Files downloads