A Lyapunov-based version of the value iteration algorithm formulated as a discrete-time switched affine system

Abstract

In this paper, we analyse the convergence properties of the Dynamic Programming Value Iteration algorithm by exploiting the stability theory of discrete-time switched affine systems. More specifically, by formulating the Value Iteration algorithm as a switched affine system, a Lyapunov-based optimal policy selection strategy is designed to guarantee the practical stabilisation of the resulting system towards an invariant set of attraction containing a given target value function. The switching control algorithm, referred to as Lyapunov-based Value Iteration algorithm, can be regarded as a convergence analysis tool and can be adopted to verify if and how such target value function can be approached by choosing from a subset of suitable stationary policies, at each time slot. The usage of the proposed algorithm in practice is also discussed. Finally, two different applications are provided to further illustrate and examine the key-aspects of the approach presented.

Keywords:

• Lyapunov function
• value iteration
• dynamic programming
• switched affine systems

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 $|r(x,u)|\le r_b$, $\mathrm{\forall }x\in X,\mathrm{\forall }u\in U(x)$, where $r_b$ is some positive real scalar.

2 Note that it is $A_{\lambda }=\gamma P_{\lambda }$, with $P_{\lambda }=\sum _{\sigma \in {\mathbb{M}}^{\mathrm{\prime }}}{\lambda }_{\sigma }P({\mu }^{\sigma })$ a stochastic matrix, being the convex combination of stochastic matrices. From $\gamma \in ]0,1[$, it follows $A_{\lambda }$ Schur stable for all $\lambda \in {\mathrm{\Lambda }}_{{\mathbb{M}}^{\mathrm{\prime }}}$.

3 A ‘bad’ policy is commonly defined as a policy which leads to low cumulative rewards, Bertsekas (2012).

4 http://cvxr.com/cvx

5 Note that it is an arrangement counting problem with constraints.