# When do discounted-optimal policies also optimize the gain?

Victor Boone

► To cite this version:

Victor Boone. When do discounted-optimal policies also optimize the gain?. 2023. hal-04068381

HAL Id: hal-04068381

https://inria.hal.science/hal-04068381

Preprint submitted on 14 Apr 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
When do discounted-optimal policies also
optimize the gain?

Victor Boone*

Univ. Grenoble-Alpes, Inria, CNRS, LIG, 38300 Grenoble, France

April 9, 2023

Abstract

In this technical note, we establish an upper-bound on the threshold on
the discount factor starting from which all discounted-optimal deterministic
policies are gain-optimal, that we prove to be tight on an example. To address
computability issues of that theoretical threshold, we provide a weaker bound
which is tractable on ergodic MDPs in polynomial time.

# 1 Concepts and main result

We consider Markov decision processes (MDPs) with finitely many states and actions, whose sets are respectively denoted $\mathcal{X}$ and $\mathcal{A} = \bigcup_{x \in \mathcal{X}} \mathcal{A}(x)$. A MDP is given by a tuple $M = (\mathcal{X}, \mathcal{A}, p, q)$ where $p$ and $q$ are respectively the transition kernel and reward distributions. The mean reward associated to $(x, a)$ is denoted $r(x, a)$, viz., $r(x, a) := \mathbb{E}_{R \sim q(x,a)}[R]$.

A policy $\pi \in \Pi$ is any deterministic stationary decision rule. Upon iterating a policy $\pi$ on $M$ starting from $x \in \mathcal{X}$, we obtain a sequence of states, actions, and rewards $\{(X_t, A_t, R_t) : t \ge 0\}$ whose probability measure will be denoted $\mathbb{P}_x^{\pi}(-)$ and expectation operator $\mathbb{E}_x^{\pi}[-]$. We will write $Z_t$ for the pair $(X_t, A_t)$. The iterates of a policy also define a Markov reward process (MRP) $\{(X_t, R_t)\}$ whose transition kernel will be denoted $P^{\pi}$ and mean reward vector $r^{\pi}$, i.e., $r^{\pi}(x) := r(x, \pi(x))$. To each policy are associated various notions of scores:

* the finite-horizon score $J_T^\pi(x) := \mathbb{E}_x^\pi[\sum_{t=0}^{T-1} r(Z_t)];$

• the $\beta$-discounted score $V_{\beta}^{\pi}(x) := \mathbb{E}_{x}^{\pi}[\sum_{t=0}^{\infty} r(Z_t)\beta^t]$ for $\beta \in [0, 1)$;

• the gain $g^{\pi}(x) := \lim_{T \to \infty} \mathbb{E}_{x}^{\pi}[\frac{1}{T} \sum_{t=0}^{T-1} r(Z_t)];$

* the bias $h^\pi(x) := \lim_{T \to \infty} \mathbb{E}_x^\pi[\sum_{t=0}^\infty (r(Z_t) - g^\pi(X_t))],$ or the Cesáro-limit when the limit doesn't exist.

<footnote>*victor.boone@univ-grenoble-alpes.fr</footnote>
Note that those quantities depend of the underlying MDP M – this M will sometimes be added to notations to avoid ambiguities.

A policy that achieves maximal $\beta$-discounted score from all state is said $\beta$-discounted optimal and we write $\pi \in \Pi_{\beta}^*$. A policy that achieves maximal gain from all state is said gain-optimal and we write $\pi \in \Pi_{-1}^*$; if in addition it achieves maximal bias from all state, it is said bias-optimal and we write $\pi \in \Pi_{0}^*$. All these classes are non-empty [Puterman, 1994]. It is known [Blackwell, 1962] that when $\beta \uparrow 1$, $\Pi_{\beta}^*$ eventually converges to a single class of policies known as Blackwell-optimal policies, which is a non-trivial subset of bias-optimal policies [Puterman, 1994].

There are few explicit bounds on how large $\beta$ needs to be so that all $\beta$-discounted optimal policies are Blackwell-optimal [Grand-Clément and Petrik, 2023]. For a less demanding problem, and to the best of our knowledge, the question of finding a threshold on the discount factor $\beta_{-1}$ that guarantees that every $\beta$-discounted optimal policy is gain-optimal (i.e. in $\Pi_{-1}^*$) for all $\beta > \beta_{-1}$ has not been addressed so far. This threshold is formally given by:

$$ \beta_{-1} := \inf \{ \beta^* \ge 1 : \forall \beta \in (\beta^*, 1], \Pi_{\beta}^* \subseteq \Pi_{-1}^* \}. \quad (1) $$

**Theorem 1** establishes an upper-bound on $\beta_{-1}$.

If $u$ is a vector (e.g., $g^{\pi}$, $h^{\pi}$, ...), its span is $\text{sp}(u) := \max_x u(x) - \min_x u(x)$. We denote $g^*$ and $h^*$ the respective optimal gain and bias vectors, equal to $g^{\pi^*}$ and $h^{\pi^*}$ respectively, where $\pi^*$ is any bias-optimal policy.

**Theorem 1.** For all MDP with finitely many states $\mathcal{X}$ and actions,

$$ \beta_{-1} \le 1 - \inf \left\{ \frac{g^*(x) - g^{\pi}(x)}{\text{sp}(h^*) + \text{sp}(h^{\pi})} : x \in \mathcal{X} \text{ and } \pi \in \Pi \text{ s.t. } g^{\pi}(x) < g^*(x) \right\}. \quad (2) $$

This result underlines a trade-off to be found between how close to gain-optimal $\pi$ is and how large its bias tends to be. This result follows from relatively folklore identities linking the gain and the discounted score. A complete proof is provided later in this note.

The bound (2) is tight. Consider the MDP with deterministic transitions pictured in Figure 1. There is a single action from states 2, 3 and two from 1 (left or right). The associated mean rewards are represented as arc weights.

<figure><img src="image_2.png" /><figcaption>Figure 1: A deterministic MDP achieving the bound of Theorem 1 ($\epsilon_g, \epsilon_h > 0$).</figcaption></figure>

The policy going to $i \in \{1, 2\}$ from 0 is denoted $\pi_i$. Only $\pi_1$ is gain-optimal.

$$ \pi_1: V_{\beta}^{\pi_1}(0) = (1 - \beta)^{-1}, \qquad g^{\pi_1}(0) = 1, \qquad h^{\pi_1} = (0, 0, 0); $$

$$ \pi_2: V_{\beta}^{\pi_2}(0) = (1 - \epsilon_g)(1 - \beta)^{-1} + \epsilon_h, \qquad g^{\pi_1}(0) = 1 - \epsilon_g, \qquad h^{\pi_2} = (0, \epsilon_h, 0). $$
From the values above, we derive that

$$V_{\beta}^{\pi_1}(0) > V_{\beta}^{\pi_2}(0) \iff \beta > 1 - \frac{\epsilon_g}{\epsilon_h} = 1 - \frac{g^{\pi_1}(0) - g^{\pi_2}(0)}{\text{sp}(h^{\pi_1}) + \text{sp}(h^{\pi_2})}.$$

## 2 A tractable lower bound for ergodic MDPs

The inf-bound in Theorem 1 is hard to compute because one needs to check all suboptimal policies. Our second result is a weaker version of (2) for ergodic MDPs that can be computed in polynomial time. Recall that a MDP is ergodic if $P^\pi$ is ergodic for all $\pi$ – this condition is not easy to check in general, and is usually decided by the problem that the MDP models.

**Theorem 2.** For all ergodic MDP with finitely many states $\mathcal{X}$ and actions,

$$\beta_{-1} \le 1 - \frac{\Delta_g}{2\text{sp}(r)\bar{D}} \qquad (3)$$

where $\Delta_g := \inf\{g^*(x) - g^\pi(x) : x \in \mathcal{X} \text{ and } g^\pi(x) < g^*(x)\} > 0$ is the gain-gap of the MDP and $\bar{D} := \max_\pi \max_{x \neq y} \mathbb{E}_x^\pi[\tau_y]^l < \infty$ is the worst diameter.

We later show that $\Delta_g$ and $\bar{D}$ are both computable in polynomial time.

*Proof.* We only have to show that for all policy $\pi$, $\text{sp}(h^\pi) \le \bar{D}\text{sp}(r)$. This result is variation on [Bartlett and Tewari, 2009, Theorem 4] that we prove using a different technique. Consider the Markov chain $\{X_t : t \ge 1\}$ induced by the iterations of $\pi$. Let $x, y \in \mathcal{X}$ such that $\text{sp}(h^\pi) = h^\pi(x) - h^\pi(y)$. Because $r^\pi - g^\pi = (I - P^\pi)h^\pi$, the quantity

$$(r^\pi(X_t) - g^\pi(X_t)) - (h^\pi(X_t) - h^\pi(X_{t+1}))$$

is a martingale difference sequence. Its differences are a.s. bounded by $\text{sp}(r) + \text{sp}(h^\pi) < \infty$ and $\tau_y$ is an a.s. finite stopping time. Hence:

$$\begin{aligned} h(x) - h(y) &= \mathbb{E}_x^\pi [h^\pi(X_0) - h^\pi(X_{\tau_y})] = \mathbb{E}_x^\pi \left[ \sum_{t=0}^{\tau_y-1} (r^\pi(X_t) - g^\pi(X_t)) \right] \\ &\le \mathbb{E}_x^\pi [\tau_y] \text{sp}(r) \\ &\le \bar{D} \text{sp}(r). \qquad \square \end{aligned}$$

*Remark 1.* We see from the definition that $\bar{D} < \infty$ if and only if $M$ is ergodic. If $M$ is not ergodic, then the bound of Theorem 2 is not informative.

### 2.1 Computation of $\Delta_g$

Define, for $(x, a)$ a state-action pair,

$$\Delta^*(x, a) := h^*(x) - [r(x, a) - g^*(x) + \langle p(x, a), h^* \rangle] \qquad (4)$$

the suboptimality gap of $(x, a)$, which is non-negative. For $\pi \in \Pi$, $\mu_x^\pi$ denotes the (empirical) invariant measure of $\pi$ achieved by iterating $\pi$ starting from $x \in \mathcal{X}$.

<footnote n="1">¹$\tau_y$ is the reaching time of $y$, starting from the initial state: $\tau_y = \inf\{t \ge 0 : X_t = y\}$.</footnote>
**Lemma 1.** For all policy $\pi$ and all $x \in S$, $g^\pi(x) \le g^*(x) - \sum_{y \in \mathcal{X}} \mu_x^\pi(y) \Delta^*(y, \pi(y))$.

*Proof.* This result can either be established algebraically or using the martingale technique used in Theorem 2. We go for the algebraic proof here. Denote $\Delta^\pi(x) := \Delta^*(x, \pi(x))$. By definition of $\Delta^*$, we have $r^\pi = g^* + (I - P^\pi)h^* + \Delta^\pi$. Multiplying by $(P^\pi)^t$ and summing over $t$, we obtain:

$$ \sum_{t=0}^{T-1} (P^\pi)^t r^\pi = \sum_{t=0}^{T-1} (P^\pi)^t g^* + (I - (P^\pi)^T) h^* + \sum_{t=0}^{T-1} (P^\pi)^t \Delta^\pi \\ \le T g^* + (I - (P^\pi)^T) h^* + \sum_{t=0}^{T-1} (P^\pi)^t \Delta^\pi. $$

Dividing by $T$ and making $T$ go to infinity, we obtain:

$$ g^\pi \le g^* + \left( \lim_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} (P^\pi)^t \right) \Delta^\pi $$

whose $x$-th line readily provides the result.

<figure><img src="image_3.png" /></figure>

Following Lemma 1, we deduce that for any policy $\pi$ such that $g^\pi(x) < g^*(x)$, there must be $y \in \mathcal{X}$ such that $\mu_x^\pi(y) \Delta^*(y, \pi(y)) > 0$. More precisely, since $\mu_x^\pi(y) > 0$ for all $\pi$ and all $y$ in the ergodic case, a policy is gain-suboptimal if and only if it uses a suboptimal action at some point, i.e., an action such that $\Delta^*(x, a) > 0$. Because, given a MDP $M$, the computation of $g^*(M)$ is polynomial time, we deduce that $\Delta_g$ is also computed in polynomial time with the following procedure:

**Algorithm 1** Computation of $\Delta_g$ for a MDP $M$

1: Construct $\{M_{xa} : (x, a) \in S \times A\}$ where $M_{xa}$ is the copy of $M$ whose only available action from $x$ is $a$;

2: Compute $\{g^*(M_{xa}) : (x, a) \in S \times A\}$ and $g^*(M)$;

3: **return** $\min \{g^*(M) - g^*(M_{xa}) : g^*(M_{xa}) < g^*(M)\}$.

## 2.2 Computation of $\overline{D}$

The computation of $\overline{D}$ follows the same idea than $\Delta_g$. Denote $M_y$ the copy of $M$ where (1) $y$ is zero-reward absorbing state and (2) all rewards, except from $y$, are set to 1. Because $y$ is recurrent under every policy $\pi$ (on $M$), the iterates of $\pi$ are eventually stationary to $y$ on $M_y$. In particular, $g^\pi(M_y) = 0$ for all $\pi$ and $y$. We deduce that $h^*(x; M_y) = \max_\pi \mathbb{E}_{x}^{\pi,M}[\tau_y]$, hence:

$$ \max_x h^*(x; M_y) = \max_\pi \max_x \mathbb{E}_{x}^{\pi,M}[\tau_y]. $$

But is the computation of $h^*(M_y)$ polytime? In general, Bellman's equations are not enough to compute $h^*$. We show that they are sufficient for $M_y$.
**Lemma 2.** Write $M_y = \langle S, A, p_{M_y}, q_{M_y} \rangle$. Let $\pi$ any policy that satisfies the Bellman equation:

$$ \forall x \in \mathcal{X}, \quad g^{\pi}(x; M_y) + h^{\pi}(x; M_y) = \max_{a \in \mathcal{A}(x)} \{r(x, a; M_y) + \langle p_{M_y}(x, a), h^{\pi}(M_y) \rangle\}. $$

Then $\pi$ is bias-optimal on $M_y$.

*Proof.* This result is a special case of a much more general result that says that, if all policies have the same recurrent states, Bellman equations automatically guarantee bias-optimality. We provide an ad-hoc proof for the special case of $M_y$ for self-containedness. For short, denote $g'^{\pi}$, $h'^{\pi}$, $r'^{\pi}$ and $P'^{\pi}$ the quantities related to $\pi$ on $M_y$. We know that $g'^{\pi} = 0$ automatically (all policies are gain-optimal on $M_y$). Let $\pi^*$ bias-optimal on $M_y$. By applying Bellman's equation iteratively, we get:

$$ \begin{aligned} h'^{\pi} &\ge r'^{\pi^*} + P'^{\pi^*} h'^{\pi} \\ &\ge r'^{\pi^*} + P'^{\pi^*} (r'^{\pi^*} + P'^{\pi^*} h'^{\pi}) \\ &\vdots \\ &\ge \sum_{t=0}^{T-1} P'^{\pi^*} r'^{\pi^*} + (P'^{\pi^*})^T h'^{\pi}. \end{aligned} $$

We know that the only recurrent state of $\pi^*$ is $y$, so when $T \to \infty$, $(P'^{\pi^*})^T h'^{\pi} \to h'^{\pi}(y) = 0$. So overall, when $T \to \infty$, we get $h'^{\pi} \ge h^*$. So $h'^{\pi} = h^*$. $\square$

In the end, $\bar{D}$ is computed in polynomial type as follows.

**Algorithm 2** Computation of $\bar{D}$ for ergodic MDPs.

1. Construct $\{M_y : y \in S\}$ where $M_y$ is the $y$-absorbing copy of $M$ with 0 reward on $y$ and 1 reward everywhere else;

2. For each $y$, compute $\pi_y$ a policy satisfying the Bellman's equations on $M_y$;

3. **return** $\max_y \max_x h^{\pi_y}(x; M_y)$.

# 3 Proof of Theorem 1

**Lemma 3.** Every policy $\pi$ satisfies: $g^{\pi}(x) - \frac{1}{T}\text{sp}(h^{\pi}) \le \frac{1}{T}J_T^{\pi}(x) \le g^{\pi}(x) + \frac{1}{T}\text{sp}(h^{\pi})$.

*Proof of Lemma 3.* Bias, gain and reward vectors are linked by the following Poisson equation: $r^{\pi} = g^{\pi} + (I - P^{\pi})h^{\pi}$. Multiplying by $(P^{\pi})^t$ and summing up, we obtain:

$$ \begin{aligned} J_T^{\pi} &:= \sum_{t=0}^{T-1} (P^{\pi})^t r^{\pi} = \sum_{t=0}^{T-1} (P^{\pi})^t g^{\pi} + \sum_{t=0}^{T-1} ((P^{\pi})^t - (P^{\pi})^{t+1}) h^{\pi} \\ &= T g^{\pi} + (I - (P^{\pi})^T) h^{\pi} \end{aligned} $$
where the last equality is obtained using $P^\pi g^\pi = g^\pi$. Now, because $I - (P^\pi)^T$ is a difference of line-stochastic matrices, all entries of $(I - (P^\pi))^T h^\pi$ are upper bounded by $\text{sp}(h^\pi)$ in absolute value. If $e$ denotes the vector whose entries are all 1s, we thus obtain

$$Tg^\pi - \text{sp}(h^\pi)e \leq J_T^\pi \leq Tg^\pi + \text{sp}(h^\pi)e$$

which is the claimed result.

<figure><img src="image_4.png" /></figure>

**Lemma 4.** For all policy $\pi$ and discount factor $\beta \in [0, 1)$, $|V_\beta^\pi(x) - \frac{g^\pi(x)}{1-\beta}| \leq \text{sp}(h^\pi)$.

*Proof of Lemma 4.* Denote $r_t := \mathbb{E}_x^\pi[r(Z_t)]$ the t-th expected reward. Let $F_\beta^\pi(x) := (1-\beta) \sum_{t=0}^\infty \beta^t r_t$ the normalized $\beta$-discounted reward of $\pi$ starting from $x$. Then for $|\beta| < 1$,

$$ (1-\beta)^{-2} F_{\beta}^{\pi}(x) = (1-\beta)^{-1} \sum_{t=0}^{\infty} r_t \beta^t \\ = \left( \sum_{t=0}^{\infty} \beta^t \right) \left( \sum_{t=0}^{\infty} r_t \beta^t \right) \\ = \sum_{t=0}^{\infty} J_{t+1}^{\pi}(x) \beta^t. $$

So $F_\beta^\pi(x) = (1-\beta)^2 \sum_{t=0}^\infty J_{t+1}^\pi(x) \beta^t$. Using $1 = (1-\beta)^2 \sum_{t=0}^\infty (t+1)\beta^t$, we also have $g^\pi = (1-\beta)^2 \sum_{t=0}^\infty g^\pi(t+1)\beta^t$, and

$$ \begin{aligned} |F_{\beta}^{\pi}(x) - g^{\pi}(x)| &\leq (1 - \beta)^2 \sum_{t=0}^{\infty} \left| \frac{1}{t+1} J_{t+1}^{\pi}(x) - g^{\pi}(x) \right| (t+1) \beta^t \\ &\leq (1 - \beta)^2 \sum_{t=0}^{\infty} \text{sp}(h^{\pi}) \beta^t \\ &= (1 - \beta) \text{sp}(h^{\pi}), \end{aligned} $$

where the second inequality is obtained by applying Lemma 3 for $J_{t+1}^\pi$.

<figure><img src="image_5.png" /></figure>

*Proof of Theorem 1.* Let $\beta^*$ the right-hand side of (2) and let $\beta > \beta^*$. Let $\pi^*$ a bias-optimal policy and $\pi$ such that $g^\pi(x) < g^*(x)$ for some $x \in \mathcal{X}$. From Lemma 4 follows that

$$V_{\beta}^{\pi}(x) \geq V_{\beta}^{\pi}(x) + \frac{g^{*}(x) - g^{\pi}(x)}{1 - \beta} - \text{sp}(h^{*}) - \text{sp}(h^{\pi}).$$

A sufficient condition for $V_{\beta}^\pi(x) > V_\beta^\pi(x)$ is thus

$$\frac{g^*(x) - g^\pi(x)}{1 - \beta} - \text{sp}(h^*) - \text{sp}(h^\pi) > 0.$$

Solving the above inequality in $\beta$, this sufficient condition is equivalent to:

$$\beta > 1 - \frac{g^*(x) - g^\pi(x)}{\text{sp}(h^*) + \text{sp}(h^\pi)}.$$

This holds by choice of $\beta^*$. So $V_\beta^\pi(x) > V_\beta^\pi(x)$ and $\pi$ is not $\beta$-discounted optimal.

<figure><img src="image_6.png" /></figure>
References

[Bartlett and Tewari, 2009] Bartlett, P. L. and Tewari, A. (2009). REGAL: a regularization based algorithm for reinforcement learning in weakly communicating MDPs. In *Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence*, UAI '09, pages 35-42, Arlington, Virginia, USA. AUAI Press.

[Blackwell, 1962] Blackwell, D. (1962). Discrete dynamic programming. *The Annals of Mathematical Statistics*, pages 719-726. Publisher: JSTOR.

[Grand-Clément and Petrik, 2023] Grand-Clément, J. and Petrik, M. (2023). Reducing blackwell and average optimality to discounted mdps via the blackwell discount factor.

[Puterman, 1994] Puterman, M. L. (1994). *Markov Decision Processes: Discrete Stochastic Dynamic Programming*. Wiley Series in Probability and Statistics. Wiley, 1 edition.