Strong Polynomiality of the Value Iteration Algorithm for Computing Nearly Optimal Policies for Discounted Dynamic Programming

Value and policy iteration algorithms are the major tools for solving infinite-horizon discounted Markov decision processes (MDPs). Policy iteration algorithms also can be viewed as implementations of specific versions of the simplex method applied to linear programming problems corresponding to discounted MDPs [6, 17]. Ye [17] proved that for a given discount factor the policy iteration algorithm is strongly polynomial as a function of the total number of state-action pairs. Kitahara and Mizuno[7] extended Ye’s [17] results by providing sufficient conditions for strong polynomiality of a simplex method for linear programming, and Scherrer [13] improved Ye’s [17] bound for MDPs. For deterministic MDPs Post and Ye [10] proved that for policy iterations there is a polynomial upper bound on the number of operations, which does not depend on the value of the discount factor. Feinberg and Huang [4] showed that value iterations are not strongly polynomial for discounted MDPs. Earlier Tseng [16] proved weak polynomiality of value iterations.

In this note we show that the value iteration algorithm computes $\epsilon$-optimal policies in strongly polynomial time. This is an important observation because value iterations are broadly used in applications, including reinforcement learning [1, 2, 15], for computing nearly optimal policies.

Let us consider an MDP with a finite state space $\mathbb{X}=\{1,2,\ldots,m\}$ and with a finite nonempty sets of actions $A(x)$ available at each state $x\in\mathbb{X}.$ Each action set $A(x)$ consists of $k_{x}$ actions. Thus, the total number of actions is $k=\sum_{x=1}^{m}k_{x},$ and this number can be interpreted as the total number of state-action pairs. Let $\alpha\in[0,1)$ be the discount factor. According to [13], the policy iteration algorithm finds an optimal policy within $N^{PI}_{I}(\alpha)$ iterations, and each iterations requires at most $N^{PI}_{O}$ operations with

$$N^{PI}_{I}(\alpha):=O\left(\frac{k}{1-\alpha}\log\frac{1}{1-\alpha}\right),\qquad\qquad N^{PI}_{O}:=O\left(m^{3}+mk\right).$$

(1.1)

This paper shows that for each $\epsilon>0$, the value iteration algorithm finds an $\epsilon$-optimal policy within $N^{VI}_{I}(\epsilon)$ iterations, and each iterations requires at most $N^{VI}_{O}$ operations, where

$$N^{VI(\epsilon)}_{I}(\alpha):=\max\left\{\left\lceil\frac{\log\frac{\left(1-\alpha\right)\epsilon}{\left[R+(1+\alpha)V\right]}}{\log\alpha}\right\rceil,1\right\},\qquad\qquad N^{VI}_{O}:=O\left(mk\right),$$

(1.2)

where $R$ and $V$ are the constants defined by a one-step cost function $r$ and a function of terminal rewards $v^{0}$. In addition, $N^{VI(\epsilon)}_{I}(\alpha)$ is non-decreasing in $\alpha\in[0,1)$.

To define the values of $R$ and $V,$ let us denote by $sp(u)$ the span seminorm of $u\in\mathbb{R}^{m},$ where $\mathbb{R}^{m}$ is an $m$-dimensional Euclidean space,

$$sp(u):=\max_{x\in\mathbb{X}}u(x)-\min_{x\in\mathbb{X}}u(x).$$

The properties of this seminorm can be found in [11, pp. 196].

Let $r(x,a)$ be the reward collected if the system is at the state $x\in\mathbb{X}$ and the action $a\in A(x)$ is chosen. Let $v^{0}(x)$ be the reward collected at the final state $x\in\mathbb{X}.$ Then

$$R:=sp(v^{0}).$$

(1.3)

We denote by

$$v^{1}(x):=\max_{a\in A(x)}r(x,a),\qquad x\in\mathbb{X},$$

(1.4)

the maximal one-step reward that can be collected at the state $x.$ Then

$$V:=sp(v^{1})=\max_{x\in\mathbb{X}}\max_{a\in A(x)}r(x,a)-\min_{x\in\mathbb{X}}\max_{a\in A(x)}r(x,a).$$

(1.5)

Observe that

$$V\leq sp(r):=\max_{x\in\mathbb{X}}\max_{a\in A(x)}r(x,a)-\min_{x\in\mathbb{X}}\min_{a\in A(x)}r(x,a).$$

Of course, the total number of operations to find an $\epsilon$-optimal policy is bounded above by $N^{VI(\epsilon)}_{I}(\alpha)\cdot N^{VI}_{O}$ for the value iteration algorithm. The total number of operations to find an optimal policy is bounded above by $N^{PI}_{I}(\alpha)\cdot N^{PI}_{O}$ for the policy iteration algorithm. Each iteration in the policy iteration algorithm requires solving a system of $m$ linear equations. This can be done by Gaussian elimination within $O(m^{3})$ operations. This is the reason the formula for $N^{PI}_{O}$ in (1.1) depends on the term $m^{3},$ which can be reduced to $m^{\omega}$ with $\omega<3$ by using contemporary methods. For example, $\omega=2.807$ for Strassen’s algorithm[14]. According to [8], the best currently available $\omega=2.37286,$ but this method of solving linear equations is impractical due to the large value of the constant in $O.$ In addition to (1.2), more accurate upper bounds on a number of iterations are presented in (3.5), (3.8), and (3.9), but they require additional definitions and calculations.

As well-known and clear from (1.1) and (1.2), the number of operations at each step is larger for the policy iteration algorithm than for the value iteration algorithm. If the number of states $m$ is large, then the difference $(N^{PI}_{O}-N^{VI}_{O})$ can be significant. In order to accelerate policy iterations, the method of modified policy iterations was introduced in [12]. This method uses value iterations to solve linear equations. As shown in Feinberg et al. [5], modified policy iterations and their versions are not strongly polynomial algorithms for finding optimal policies.

Let $\mathbb{N}$ and $\mathbb{R}$ be the sets of natural numbers and real numbers respectively. For a finite set $E$, let $\left|E\right|$ denote the number of elements in the set $E$. We consider an MDP with a finite state space $\mathbb{X}=\{1,2,\ldots,m\},$ where $m\in\mathbb{N}$ is the number of states, and nonempty finite action sets $A(x)$ available at states $x\in\mathbb{X}.$ Let $\mathbb{A}:=\bigcup_{x\in\mathbb{X}}A(x)$ be the action set. We recall that $k=\sum_{x\in\mathbb{X}}\left|A(x)\right|$ is the total number of actions at all states or, in slightly different terms, the number of all state-action pairs. For each $x\in\mathbb{X},$ if an action $a\in A(x)$ is selected at the state $x\in\mathbb{X},$ then a one-step reward $r(x,a)$ is collected and the process moves to the next state $y\in\mathbb{X}$ with the probability $p(y|x,a),$ where $r(x,a)$ is a real number and $\sum_{y\in\mathbb{X}}p(y|x,a)=1.$ The process continues over a finite or infinite planning horizon. For a finite-horizon problem, the terminal real-valued reward $v^{0}(x)$ is collected at the final state $x\in\mathbb{X}.$

A deterministic policy is a mapping $\phi:\mathbb{X}\mapsto\mathbb{A}$ such that $\phi(x)\in A(x)$ for each $x\in\mathbb{X},$ and, if the process is at a state $x\in\mathbb{X},$ then the action $\phi(x)$ is selected. A general policy can be randomized and history-dependent; see e.g., Puterman [11, p. 154] for definitions of various classes of policies. We denote by $\Pi$ the set of all policies.

Let $\alpha\in[0,1)$ be the discount factor. For a policy $\pi\in\Pi$ and for an initial state $x\in\mathbb{X},$ the expected total discounted reward for an $n$-horizon problem is

$$v_{n,\alpha}^{\pi}(x):=\mathbb{E}_{x}^{\pi}\left[\sum_{t=0}^{n-1}\alpha^{k}r(x_{t},a_{t})+\alpha^{n}v^{0}(x_{n})\right],\qquad n\in\mathbb{N},$$

and for the infinite-horizon problem it is

$$v_{\alpha}^{\pi}(x):=\mathbb{E}_{x}^{\pi}\sum_{t=0}^{\infty}\alpha^{k}r(x_{t},a_{t}),$$

where $\mathbb{E}_{x}^{\pi}$ is the expectation defined by the initial state $x$ and the policy $\pi,$ and where $x_{0}a_{0}\cdots x_{t}a_{t}\ldots$ is a trajectory of the process consisting of states $x_{t}\in\mathbb{X}$ and actions $a_{t}\in A(x_{t})$ at epochs $t=0,1,\ldots\ .$ The value functions are defined for initial states $x\in\mathbb{X}$ as

$$v_{n,\alpha}(x):=\sup_{\pi\in\Pi}v_{n,\alpha}^{\pi}(x),\qquad n\in\mathbb{N},$$

for $n$-horizon problems, and

$$v_{\alpha}(x):=\sup_{\phi\in\mathbb{F}}v_{\alpha}^{\phi}(x)$$

for infinite-horizon problems. Note that $v_{0,\alpha}^{\pi}=v_{0,\alpha}=v^{0}$ for all $\alpha\in[0,1)$ and $\pi\in\Pi$.

A policy $\pi$ is called optimal ($n$-horizon optimal for $n=1,2,\ldots$) if $v_{\alpha}^{\pi}(x)=\sup_{\pi\in\Pi}v_{\alpha}^{\pi}(x)$ ($v_{n,\alpha}^{\pi}(x)=\sup_{\pi\in\Pi}v_{n,\alpha}^{\pi}(x)$) for all $x\in\mathbb{X}$. It is well-known that, for discounted MDPs with finite action sets, finite horizon problems have optimal policies and infinite horizon problems have deterministic optimal policies; see [11, p. 154].

A policy $\pi$ is called $\epsilon$-optimal for $\epsilon\geq 0$ if $v_{\alpha}^{\pi}(x)\geq v_{\alpha}(x)-\epsilon$ for all $x\in\mathbb{X}.$ A $0$-optimal policy is optimal. The objective of this paper is to estimate the complexity of the value iteration algorithm for finding a deterministic $\epsilon$-optimal policy for $\epsilon>0$.

For a real-valued function $v:\mathbb{X}\to\mathbb{R},$ let us define

$$T_{\alpha}^{a}v(x):=r(x,a)+\alpha\sum_{y\in\mathbb{X}}p(y|x,a)v(y),\qquad x\in\mathbb{X},\ a\in A(x).$$

(3.1)

We shall use the notation $T_{\alpha}^{\phi}v(x):=T_{\alpha}^{\phi(x)}v(x)$ for a deterministic policy $\phi.$ For $v:\mathbb{X}\to\mathbb{R}$ we also define the optimality operator $T_{\alpha},$

$$T_{\alpha}v(x):=\max_{a\in A(x)}T_{\alpha}^{a}v(x),\qquad x\in\mathbb{X}.$$

(3.2)

Every real-valued function $v$ on $\mathbb{X}$ can be identified with a vector $v=(v(1),\ldots,v(m)).$ Therefore, all real-valued functions on $\mathbb{X}$ form the $m$-dimensional Euclidean space $\mathbb{R}^{m}.$

For each $n\in\mathbb{N}$ and all $v^{0}\in\mathbb{R}^{m}$, the expected total discounted rewards $v_{n,\alpha}^{\phi}$ and $v_{\alpha}^{\phi}$ satisfy the equations

$$v^{\phi}_{n,\alpha}=T^{\phi}_{\alpha}v^{\phi}_{n-1,\alpha},\quad v^{\phi}_{\alpha}=T^{\phi}_{\alpha}v^{\phi}_{\alpha},$$

the value functions $v_{n,\alpha},$ $v_{\alpha}$ satisfy the optimality equations

$$v_{n,\alpha}=T_{\alpha}v_{n-1,\alpha},\quad v_{\alpha}=T_{\alpha}v_{n-1,\alpha},$$

and value iterations converge to the infinite-horizon expected total rewards and optimal values

	$\displaystyle v_{\alpha}^{\phi}=$	$\displaystyle\lim_{n\to\infty}{\left(T_{\alpha}^{\phi}\right)}^{n}v^{0}=T_{\alpha}^{\phi}v_{\alpha}^{\phi},$		(3.3)
	$\displaystyle v_{\alpha}=\lim_{n\to\infty}{\left(T_{\alpha}\right)}^{n}$	$\displaystyle v^{0}=\lim_{n\to\infty}v_{n,\alpha}=T_{\alpha}v_{\alpha},$

and a deterministic policy $\phi$ is optimal if and only if $T^{\phi}_{\alpha}v_{\alpha}=T_{\alpha}v_{\alpha};$ see, e.g., [3], [11, pp. 146-151]. Therefore, if we consider the nonempty sets

$$A_{\alpha}(x)=\{a\in A(x):v_{\alpha}(x)=T^{a}_{\alpha}v_{\alpha}(x)\},$$

then a deterministic policy $\phi$ is optimal if and only if $\phi(x)\in A_{\alpha}(x)$ for all $x\in\mathbb{X}.$

For a given $\epsilon>0,$ the following value iteration algorithm computes a deterministic $\epsilon$-optimal policy. It uses a stopping rule based on the value of the span $sp(v_{n,\alpha}-v_{n-1,\alpha})$. As mentioned in [11, p. 205], this algorithm generates the same number of iterations as the relative value iteration algorithm originally introduced to accelerate value iterations.

If $\alpha=0,$ then a deterministic policy $\phi$ is optimal if and only if $r(x,\phi(x))=\max_{a\in A(x)}\{r(x,a)\}.$ As well-known, Algorithm 1 converges within a finite number of iterations (e.g., this follows from (3.3)) and returns an $\epsilon$-optimal policy $\phi$ (e.g., this follows from [11, Proposition 6.6.5]).

Following Puterman [11, Theorem 6.6.6], let us define

$$\gamma:=\max_{\begin{subarray}{c}x,y\in\mathbb{X}\\ a\in A(x),b\in A(y)\end{subarray}}\left[1-\sum_{z\in\mathbb{X}}\min\left\{p(z|x,a),p(z|y,b)\right\}\right].$$

(3.4)

We notice that $0\leq\gamma\leq 1$. We assume $\gamma>0$ since otherwise $p(z|x,a)=p(z|y,b)$ for any $x,y,z\in\mathbb{X}$ and $a\in A(x),b\in A(y).$ If $\gamma=0,$ then we have again that a deterministic policy $\phi$ is optimal if and only if $r(x,\phi(x))=\max_{a\in A(x)}\{r(x,a)\}.$ In this case Algorithm 1 stops at most after the second iteration and returns a deterministic optimal policy. If an MDP has deterministic probabilities and there are two or more deterministic policies with nonidentical stochastic matrices, then $\gamma=1$.

Computing the value of $\gamma$ requires computing the sum in (3.4) for all couples $\{(x,a),(y,b))\}$ of state-action pairs such that $(x,a)\neq(y,b).$ The identical pairs $(x,a)=(y,b)$ can be excluded since for such pairs the value of the function to be maximized in (3.4) is 0, which is the smallest possible value. The total number of such couples is $k(k-1)/2=O(k^{2})$. The number of arithmetic operations in (3.4), which are additions, is $m$ for each couple. Therefore, the straightforward computation of $\gamma$ requires $O(mk^{2})$ operations, which can be significantly larger than the complexity to compute an deterministic $\epsilon$-optimal policy, which is the product of $N^{VI(\epsilon)}_{I}(\alpha)$ and $N^{VI}_{O}$ defined in (1.2). Puterman [11, Eq. (6.6.16)] also provides an upper bound $\gamma^{\prime}\in[\gamma,1],$ where $\gamma^{\prime}:=1-\sum_{z\in\mathbb{X}}\min_{x\in\mathbb{X},a\in A(x)}p(z|x,a),$ whose computation requires $O(mk)$ operations.

Let us consider the vector $v^{1}\in\mathbb{R}^{m}$ defined in (1.4). Note that $v^{1}=v_{1,\alpha}$ if $v^{0}\equiv 0$. In the next corollary, we assume that $sp(v^{1})+sp(v^{0})>0$ and $\gamma>0$ since otherwise Algorithm 1 stops after the first iteration and returns a deterministic optimal policy.

As explained in the paragraph preceding Theorem 1, it may be time-consuming to find the actual value of $\gamma$ for an MDP. The following corollaries provide additional bounds.

We notice that, if the function $F$ from (3.8) is minimized in $v^{0}$, than the smallest value is attained when $sp(v^{0})=0,$ which is $v^{0}=const.$ The following corollary provides upper bounds for $v^{0}=const$ including $v^{0}\equiv 0.$

Lewis and Paul [9] provide examples of MDPs for which the numbers of iterations required for computing an optimal policy by value iterations can tend to infinity even for discount factor bounded away from $1$. Here we provide a significantly simpler example.