Approximate Fixed Point Iteration with an Application to Infinite Horizon Markov Decision Processes
Author:
- Anthony AlmudevarAAAnthony Almudevar
- 1 January 2008
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Control and Optimization
- Vol. 47 (5) , 2303-2347
Abstract
Many approximate iterative algorithms can be represented by the form $V_n=TV_{n-1}+U_n$, $n\geq1$, where $V_{n-1},U_n$, $n\geq1$, are elements of a seminormed linear space $(\mathcal{V},\|\cdot\|)$ and T is a contractive operator. The objective is usually to calculate a fixed point $V^*$ of T. Here, the quantities $U_n$ may be interpreted as the errors obtained when the operator T can be evaluated only approximately. As is well known, in the absence of such an approximation error, the algorithm converges to a fixed point with a geometric rate under general conditions. In this article the convergence properties of such algorithms in the presence of an approximation error $U_n$ are studied. It is shown that the error $\|V_n-V^*\|$ is dominated by $\|U_n\|$, so that convergence of $\|U_n\|$ to zero implies the convergence of $\|V_n-V^*\|$ to zero, at a rate determined by $\|U_n\|$. The results are naturally extended to a relative error of the form $\|U_n\|/\|V_{n-1}\|$, as well as to J-stage contractions. The utility of this general theory is then demonstrated by an extended application to the problem of model-based approximate and adaptive control of Markov decision processes. The theory is shown to permit a sharpening of known convergence rates under more general conditions. Additionally, bounds on regret for adaptive controls with forced exploration are calculated in terms of a stagewise exploration rate. This permits the determination of an optimal choice of exploration rate within the class of certainty-equivalence adaptive control policies.
Keywords
This publication has 24 references indexed in Scilit:
- Sequential Monte Carlo Techniques for Solving Non-Linear SystemsMonte Carlo Methods and Applications, 2006
- Near-Optimal Reinforcement Learning in Polynomial TimeMachine Learning, 2002
- A Dynamic Programming Algorithm for the Optimal Control of Piecewise Deterministic Markov ProcessesSIAM Journal on Control and Optimization, 2001
- Sequential monte carlo techniques for the solution of linear systemsJournal of Scientific Computing, 1994
- Analysis of an adaptive control scheme for a partially observed controlled Markov chainIEEE Transactions on Automatic Control, 1993
- Discrete-Time Controlled Markov Processes with Average Cost Criterion: A SurveySIAM Journal on Control and Optimization, 1993
- Controlled semi-markov models - the discounted caseJournal of Statistical Planning and Inference, 1989
- Adaptive control of discounted Markov decision chainsJournal of Optimization Theory and Applications, 1985
- Nonstationary Markov decision problems with converging parametersJournal of Optimization Theory and Applications, 1981
- A Sharper Form of the Borel-Cantelli Lemma and the Strong LawThe Annals of Mathematical Statistics, 1965