We introduce a variant of the concept of a "quantilizer" for the setting of choosing a policy for a finite Markov decision process (MDP), where the generic unknown cost is replaced by an unknown penalty term in the reward function. This is essentially a generalization of quantilization in repeated games with a cost independence assumption. We show that the "quantilal" policy shares some properties with the ordinary optimal policy, namely that (i) it can always be chosen to be Markov (ii) it can be chosen to be stationary when time discount is geometric (iii) the "quantilum" value of an MDP with geometric time discount is a continuous piecewise rational function of the parameters, and it converges when the discount parameter $\lambda$ approaches 1. Finally, we demonstrate a polynomial-time algorithm for computing the quantilal policy, showing that quantilization is not qualitatively harder than ordinary optimization.

---

Background

Quantilization (introduced in Taylor 2015) is a method of dealing with "Extremal Goodhart's Law". According to Extremal Goodhart, when we attempt to optimize a utility function $U^{\ast }:A\to R$ by aggressively optimizing a proxy $U:A\to R$, we are likely to land outside of the domain where the proxy is useful. Quantilization addresses this by assuming an unknown cost function $C:A\to [0,\infty )$ whose expectation $\underset{\zeta }{E}\left[C\right]$ w.r.t. some reference probability measure $\zeta \in \Delta A$ is bounded by 1. $\zeta$ can be thought of as defining the "domain" within which $U$ is well-behaved (for example it can be the probability measure of choices made by humans). We can then seek to maximize $\underset{}{E}\left[U\right]$ while constraining $\underset{}{E}\left[C\right]$ by a fixed bound $C_{max}$:

$${\tilde{\xi }}^{\ast }:\in \underset{\xi \in \Delta A}{argmax}\left\{\underset{\xi }{E}\left[U\right]\right|\forall C:A\to [0,\infty ):\underset{\zeta }{E}\left[C\right]\le 1⟹\underset{\xi }{E}\left[C\right]\le C_{max}\}$$

Alternatively, we can choose some parameter $\eta \in (0,\infty )$ and maximize the minimal guaranteed expectation of $U-\eta C$:

$${\xi }^{\ast }:\in \underset{\xi \in \Delta A}{argmax}\underset{C:A\to [0,\infty )}{inf}\left\{\underset{\xi }{E}[U-\eta C]\right|\underset{\zeta }{E}\left[C\right]\le 1\}$$

These two formulations are almost equivalent since both amount to finding a strategy that is Pareto efficient w.r.t. to the two objectives $\underset{}{E}\left[U\right]$ and $-\underset{}{E}\left[C\right]$. For ${\tilde{\xi }}^{\ast }$ the tradeoff is governed by the parameter $C_{max}$ and for ${\xi }^{\ast }$ the tradeoff is governed by the parameter $\eta$. Indeed, it is easy to see that any ${\xi }^{\ast }$ is also optimal for the first criterion if we take $C_{max}=\underset{{\xi }^{\ast }}{E}\left[C\right]$, and any ${\tilde{\xi }}^{\ast }$ is also optimal for the latter criterion for an appropriate choice of $\eta$ (it needs to be a subderivative of the Pareto frontier).

In the following, we will use as our starting point the second formulation, which can be thought of as a zero-sum game in which $U-\eta C$ is the utility function of an agent whose strategy set is $A$, and $C$ is chosen by the adversary. The quantilal strategy ${\xi }^{\ast }$ is the Nash equilibrium of the game.

This formulation seems natural if we take $\eta :=\underset{\zeta }{E}[max(U-U^{\ast },0)]$ (a measure of how "optimistic" is $U$ in the domain $\zeta$) and $C:={\eta }^{-1}max(U-U^{\ast },0)$. In particular, the quantilum value (the value of the game) is a lower bound on the expectation of $U^{\ast }$.

In principle, this formalism can be applied to sequential interaction between an agent and an environment, if we replace $A$ by the set of policies. However, if it is possible to make structural assumptions about $U$ and $C$, we can do better. Taylor explores one such structural assumption, namely a sequence of independent games in which both $U$ and $C$ are additive across the games. We consider a more general setting, namely that of a finite Markov decision process (MDP).

Notation

Given a set $A$, the notation $A^{\ast }$ will denote the set of finite strings over alphabet $A$, i.e.

$$A^{\ast }:=\underset{n=0}{\overset{\infty }{⨆}}{A}^n$$

$A^{\omega }$ denotes the space of infinite strings over alphabet $A$, equipped with the product topology and the corresponding Borel sigma-algebra. Given $x\in A^{\omega }$ and $n\in N$, $x_n\in A$ is the $n$-th symbol of the string $x$ (in our conventions, $0\in N$ so the string begins from the 0th symbol.) Given $h\in A^{\ast }$ and $x\in A^{\omega }$, the notation $h⊏x$ means that $h$ is a prefix of $x$.

Given a set $A$, $x\in A^{\omega }$ and $n\in N$, the notation $x_{:n}$ will indicate the prefix of $x$ of length $n$. That is, $x_{:n}\in A^n$ and $x_{:n}⊏x$.

Given a measurable space $X$, we denote $\Delta X$ the space of probability measures on $X$.

Given measurable spaces $X$ and $Y$, the notation $K:X\stackrel{\text{k}}{\to }Y$ means that $K$ is a Markov kernel from $X$ to $Y$. Given $x\in X$, $K\left(x\right)$ is the corresponding probability measure on $Y$. Given $A\subseteq Y$ measurable, $K(A\mid x):=K\left(x\right)\left(A\right)$. Given $y\in Y$, $K(y\mid x):=K\left(\right\{y\left\}\right|x)$. Given $J:Y\stackrel{\text{k}}{\to }Z$, $JK:X\stackrel{\text{k}}{\to }Z$ is the composition of $J$ and $K$, and when $Y=X$, $K^n$ is the $n$-th composition power.

Results

A finite MDP is defined by a non-empty finite set of states $S$, a non-empty finite set of actions $A$, a transition kernel $T:S\times A\stackrel{\text{k}}{\to }S$ and a reward function $R:S\to R$. To specify the utility function, we also need to fix a time discount function $\gamma \in \Delta N$. This allows defining $U:S^{\omega }\to R$ by

$$U\left(x\right):=\underset{n\sim \gamma }{E}\left[R\left(x_n\right)\right]$$

We also fix an initial distribution over states ${\zeta }_0\in \Delta S$. In "classical" MDP theory, it is sufficient to consider a deterministic initial state $s_0\in S$, since the optimal policy doesn't depend on the initial state anyway. However, quantilization is different since the worst-case cost function depends on the initial conditions.

We now assume that the cost function $C:S^{\omega }\to R$ (or, the true utility function $U^{\ast }$) has the same form. That is, there is some penalty function $P:S\to [0,\infty )$ s.t.

$$C\left(x\right)=\underset{n\sim \gamma }{E}\left[P\left(x_n\right)\right]$$

Given a policy $\pi :S^{\ast }\times S\stackrel{\text{k}}{\to }A$ (where the $S^{\ast }$ factor represents the past history the factor $S$ represents the current state), we define $H\pi \in \Delta S^{\omega }$ in the usual way (the distribution over histories resulting from $\pi$). Finally, we fix $\eta \in (0,\infty )$. We are now ready to define quantilization in this setting

Definition 1

${\pi }^{\ast }:S^{\ast }\times S\stackrel{\text{k}}{\to }A$ is said to be quantilal relatively to reference policy $\sigma :S^{\ast }\times S\stackrel{\text{k}}{\to }A$ when

$${\pi }^{\ast }:\in \underset{\pi :S^{\ast }\times S\stackrel{\text{k}}{\to }A}{argmax}\underset{P:S\to [0,\infty )}{inf}\left\{\underset{\begin{array}{c}x\sim H\pi \\ n\sim \gamma \end{array}}{E}[R\left(x_n\right)-\eta P\left(x_n\right)]\right|\underset{\begin{array}{c}x\sim H\sigma \\ n\sim \gamma \end{array}}{E}\left[P\left(x_n\right)\right]\le 1\}$$

We also define the quantilum value $\mathrm{QV}\in R$ by

$$\mathrm{QV}:=\underset{\pi :S^{\ast }\times S\stackrel{\text{k}}{\to }A}{sup}\underset{P:S\to [0,\infty )}{inf}\left\{\underset{\begin{array}{c}x\sim H\pi \\ n\sim \gamma \end{array}}{E}[R\left(x_n\right)-\eta P\left(x_n\right)]\right|\underset{\begin{array}{c}x\sim H\sigma \\ n\sim \gamma \end{array}}{E}\left[P\left(x_n\right)\right]\le 1\}$$

($\mathrm{QV}$ cannot be $-\infty$ since taking $\pi =\sigma$ yields a lower bound of $\underset{\begin{array}{c}x\sim H\sigma \\ n\sim \gamma \end{array}}{E}\left[R\left(x_n\right)\right]-\eta$.)

---

In the original quantilization formalism, the quantilal strategy can be described more explicitly, as sampling according to the reference measure $\zeta$ from some top fraction of actions ranked by expected utility. Here, we don't have an analogous description, but we can in some sense evaluate the infimum over $P$.

For any $\pi :S^{\ast }\times S\stackrel{\text{k}}{\to }A$, define $Z\pi \in \Delta S$ by

$$Z\pi \left(s\right):=\underset{\begin{array}{c}x\sim H\pi \\ n\sim \gamma \end{array}}{\mathrm{Pr}}[x_n=s]$$

For any $\mu ,\nu \in \Delta S$, the notation $D_{\infty }\left(\mu \right|\left|\nu \right)$ signifies the Renyi divergence of order $\infty$:

$$D_{\infty }\left(\mu \right|\left|\nu \right):=\ln \underset{\begin{array}{c}s\in S\\ \mu \left(s\right)>0\end{array}}{max}\frac{\mu \left(s\right)}{\nu \left(s\right)}$$

In general, $D_{\infty }\left(\mu \right|\left|\nu \right)\in [0,\infty ]$.

Proposition 1

${\pi }^{\ast }:S^{\ast }\times S\stackrel{\text{k}}{\to }A$ is quantilal relatively to reference policy $\sigma :S^{\ast }\times S\stackrel{\text{k}}{\to }A$ if and only if

$${\pi }^{\ast }\in \underset{\pi :S^{\ast }\times S\stackrel{\text{k}}{\to }A}{argmax}(\underset{Z\pi }{E}\left[R\right]-\eta \exp D_{\infty }\left(Z\pi \right|\left|Z\sigma \right))$$

Also, we have

$$\mathrm{QV}=\underset{\pi :S^{\ast }\times S\stackrel{\text{k}}{\to }A}{sup}(\underset{Z\pi }{E}\left[R\right]-\eta \exp D_{\infty }\left(Z\pi \right|\left|Z\sigma \right))$$

---

If the maximization in Proposition 1 was over arbitrary $\xi \in \Delta S$ rather than $\xi$ of the form $Z\pi$, we would get ordinary quantilization and sampling $\xi$ would be equivalent to sampling some top fraction of $\zeta :=Z\sigma$. However, in general, the image of the $Z$ operator is some closed convex set which is not the entire $\Delta S$.

So far we considered arbitrary (non-stationary) policies. From classical MDP theory, we know that an optimal policy can always be chosen to be Markov:

Definition 2

$\pi :S^{\ast }\times S\stackrel{\text{k}}{\to }A$ is said to be a Markov policy, when there is some ${\pi }_{\text{M}}:N\times S\stackrel{\text{k}}{\to }A$ s.t. $\pi (h,s)={\pi }_{\text{M}}(\left|h\right|,s)$.

---

Note that a priori it might be unclear whether there is even a non-stationary quantilal policy. However, we have

Proposition 2

For any $\sigma :S^{\ast }\times S\stackrel{\text{k}}{\to }A$, there exists a Markov policy which is quantilal relatively to $\sigma$.

---

Now assume that our time discount function is geometric, i.e. there exists $\lambda \in [0,1)$ s.t. $\gamma \left(n\right)=(1-\lambda ){\lambda }^n$. Then it is known than an optimal policy can be chosen to be stationary:

Definition 3

$\pi :S^{\ast }\times S\stackrel{\text{k}}{\to }A$ is said to be a stationary policy, when there is some ${\pi }_{\text{T}}:S\stackrel{\text{k}}{\to }A$ s.t. $\pi (h,s)={\pi }_{\text{T}}\left(s\right)$.

---

Once again, the situation for quantilal policies is analogous:

Proposition 3

If $\gamma$ is geometric, then for any $\sigma :S^{\ast }\times S\stackrel{\text{k}}{\to }A$, there exists a stationary policy which is quantilal relatively to $\sigma$.

---

What is not analogous is that an optimal policy can be chosen to be deterministic whereas, of course, this is not the case for quantilal policies.

It is known that the value of an optimal policy depends on the parameters as a piecewise rational function, and in particular it converges as $\lambda \to 1$ and has a Taylor expansion at $\lambda =1$. The quantilum value has the same property.

Proposition 4

$\mathrm{QV}$ is a piecewise rational continuous function of $\lambda$, $\eta$, the matrix elements of $T$, the values of $R$, the values of ${\zeta }_0$ and the values of $Z\sigma$, with a final number of "pieces".

Corollary 1

Assume that $\sigma$ is a stationary policy. Then, $\mathrm{QV}$ converges as $\lambda \to 1$, holding all other parameters fixed (in the sense that, $\sigma$ is fixed whereas $Z\sigma$ changes as a function of $\lambda$). It is analytic in $\lambda$ for some interval $[{\lambda }_0,1]$ and therefore can be described by a Taylor expansion around $\lambda =1$ inside this interval.

---

Note that for optimal policies, Proposition 4 holds for a simpler reason. Specifically, the optimal policy is piecewise constant (since it's deterministic) and there is a Blackwell policy i.e. a fixed policy which is optimal for any $\lambda$ sufficiently close to 1. And, it is easy to see that for a constant policy, the value is a rational function of $\lambda$. On the other hand, the quantilal policy is not guaranteed to be locally constant anywhere. Nevertheless the quantilum value is still piecewise rational.

Finally, we address the question of the computational complexity of quantilization. We prove the following

Proposition 5

Assume geometric time discount. Assume further that $R\left(s\right)$, $T\left(t\right|s,a)$, ${\zeta }_0\left(s\right)$, $\lambda$, $Z\sigma \left(s\right)$ and $\eta$ are rational numbers. Then:

a. There is an algorithm for computing $\mathrm{QV}$ which runs in time polynomial in the size of the input $R$, $T$, ${\zeta }_0$, $\lambda$, $Z\sigma$ and $\eta$. Also, if $\sigma$ is stationary and $\sigma \left(t\right|s,a)$ are rational, then $Z\sigma \left(s\right)$ are also rational and can be computed from $\sigma$, $T$, ${\zeta }_0$ and $\lambda$ in polynomial time.

b. Given an additional rational input parameter $ϵ\in (0,1)$, there is an algorithm for computing a stationary policy which is an $ϵ$-equilibrium in the zero-sum game associated with quantilization, which runs in time polynomial in the size of the input and $\ln \frac{1}{ϵ}$.

---

EDIT: In fact, it is possible to do better and compute an exact quantilal policy in polynomial time.

Future Directions

To tease a little, here are some developments of this work that I'm planning:

• Apply quantilization to reinforcement learning, i.e. when we don't know the MDP in advance. In particular, I believe that the principles of quantilization can be used not only to deal with misspecified rewards, but also to deal with traps to some extent (assuming it a priori known that the reference policy has at most a small probability of falling into a trap). This has some philosophical implications on how humans avoid traps.

• Unify that formalism with DRL. The role of the reference policy will be played by the advisor (thus the reference policy is not known in advance but is learned online). This means we can drop the sanity condition for the advisor, at the price of (i) having a regret bound defined w.r.t. some kind of quantilum value rather than optimal value (ii) having a term in the regret bound proportional to the (presumably small) rate of falling into traps when following the reference (advisor) policy. It should be possible to further develop that by unifying it with the ideas of catastrophe DRL.

• Deal with more general environments, e.g. POMDPs and continuous state spaces.

Proofs

Proposition A.1

$$\underset{P:S\to [0,\infty )}{inf}\left\{\underset{\begin{array}{c}x\sim H\pi \\ n\sim \gamma \end{array}}{E}[R\left(x_n\right)-\eta P\left(x_n\right)]\right|\underset{\begin{array}{c}x\sim H\sigma \\ n\sim \gamma \end{array}}{E}\left[P\left(x_n\right)\right]\le 1\}=\underset{Z\pi }{E}\left[R\right]-\eta \exp D_{\infty }\left(Z\pi \right|\left|Z\sigma \right)$$

Proof of Proposition A.1

The definition of $Z$ implies that

$$\underset{\begin{array}{c}x\sim H\pi \\ n\sim \gamma \end{array}}{E}[R\left(x_n\right)-\eta P\left(x_n\right)]=\underset{Z\pi }{E}[R-\eta P]$$

Also

$$\underset{\begin{array}{c}x\sim H\sigma \\ n\sim \gamma \end{array}}{E}\left[P\left(x_n\right)\right]=\underset{Z\sigma }{E}\left[P\right]$$

Observe that

$$\underset{Z\pi }{E}\left[P\right]=\sum _{s\in S}Z\pi \left(s\right)P\left(s\right)\le \underset{\begin{array}{c}s\in S\\ Z\pi \left(s\right)>0\end{array}}{max}\frac{Z\pi \left(s\right)}{Z\sigma \left(s\right)}\cdot \sum _{s\in S}Z\sigma \left(s\right)P\left(s\right)=\exp D_{\infty }\left(Z\pi \right|\left|Z\sigma \right)\cdot \underset{Z\sigma }{E}\left[P\right]$$

It follows that for any $P$ that satisfies the constraint $\underset{\begin{array}{c}x\sim H\sigma \\ n\sim \gamma \end{array}}{E}\left[P\left(x_n\right)\right]\le 1$, we have $\underset{Z\sigma }{E}\left[P\right]\le 1$ and therefore

$$\underset{\begin{array}{c}x\sim H\pi \\ n\sim \gamma \end{array}}{E}[R\left(x_n\right)-\eta P\left(x_n\right)]=\underset{Z\pi }{E}\left[R\right]-\eta \underset{Z\pi }{E}\left[P\right]\ge \underset{Z\pi }{E}\left[R\right]-\eta \exp D_{\infty }\left(Z\pi \right|\left|Z\sigma \right)$$

To show that the inequality can be arbitrarily close to equality, choose $s^{\ast }\in S$ s.t. $Z\pi \left(s^{\ast }\right)>0$ and $\frac{Z\pi \left(s^{\ast }\right)}{Z\sigma \left(s^{\ast }\right)}=\exp D_{\infty }\left(Z\pi \right|\left|Z\sigma \right)$. If $Z\sigma \left(s^{\ast }\right)>0$, we can define $P^{\ast }$ by

$$P^{\ast }\left(s\right):=\{\begin{array}{c}Z\sigma (s^{\ast }{)}^{-1}\text{if}s=s^{\ast }\\ 0\text{otherwise}\end{array}$$

Clearly $\underset{Z\sigma }{E}\left[P^{\ast }\right]=1$ and $\underset{Z\pi }{E}\left[P^{\ast }\right]=\exp D_{\infty }\left(Z\pi \right|\left|Z\sigma \right)$. We get

$$\underset{\begin{array}{c}x\sim H\pi \\ n\sim \gamma \end{array}}{E}[R\left(x_n\right)-\eta P^{\ast }\left(x_n\right)]=\underset{Z\pi }{E}\left[R\right]-\eta \underset{Z\pi }{E}\left[P^{\ast }\right]=\underset{Z\pi }{E}\left[R\right]-\eta \exp D_{\infty }\left(Z\pi \right|\left|Z\sigma \right)$$

In the case $Z\sigma \left(s^{\ast }\right)>0$, we can take any $M>0$ and define $P^M$ by

$$P^M\left(s\right):=\{\begin{array}{c}M\text{if}s=s^{\ast }\\ 0\text{otherwise}\end{array}$$

Clearly $\underset{Z\sigma }{E}\left[P^M\right]=0\le 1$ and $\underset{Z\pi }{E}\left[P^M\right]=M\cdot Z\pi \left(s^{\ast }\right)$. We get

$$\underset{\begin{array}{c}x\sim H\pi \\ n\sim \gamma \end{array}}{E}[R\left(x_n\right)-\eta P^M\left(x_n\right)]=\underset{Z\pi }{E}\left[R\right]-\eta \underset{Z\pi }{E}\left[P^M\right]=\underset{Z\pi }{E}\left[R\right]-M\cdot Z\pi \left(s^{\ast }\right)$$

Since $Z\pi \left(s^{\ast }\right)>0$, we can make this expression arbitrarily low and therefore the infimum is $-\infty$ which is what we need since in this case $D_{\infty }\left(Z\pi \right|\left|Z\sigma \right)=\infty$.

---

Proposition 1 now follows immediately from Proposition A.1.

We will use the notation $\Pi :=\{S^{\ast }\times S\stackrel{\text{k}}{\to }A\}$ (the space of all policies). We also have ${\Pi }_{\text{M}}:=\{N\times S\stackrel{\text{k}}{\to }A\}$ (the space of Markov policies) and ${\Pi }_{\text{T}}:=\left\{S\stackrel{\text{k}}{\to }A\right\}$ (the space of stationary policies). Mildly abusing notation, we will view ${\Pi }_{\text{M}}$ as a subspace of $\Pi$ and ${\Pi }_{\text{T}}$ as a subspace of ${\Pi }_{\text{M}}$.

Proposition A.2

For any $\sigma :S^{\ast }\times S\stackrel{\text{k}}{\to }A$, there exists some policy which is quantilal relatively to $\sigma$.

Proof of Proposition A.2

$\Pi$ is the product of a countable number of copies of $\Delta A$ (indexed by $S^{\ast }\times S$). $\Delta A$ is naturally a topological space (a simplex), and we can thereby equip $\Pi$ by the product topology. By Tychonoff's theorem, $\Pi$ is compact. Moreover, it is easy to see that $Z:\Pi \to \Delta S$ is a continuous mapping. Finally, observe that $D_{\infty }\left(\xi \right|\left|Z\sigma \right)$ is lower semicontinuous in $\xi$ (since it is the maximum of a number of continuous functions) and therefore $\underset{\xi }{E}\left[R\right]-\eta \exp D_{\infty }\left(\xi \right|\left|Z\sigma \right)$ is upper semicontinuous in $\xi$. By the extreme value theorem, it follows that a quantilal policy exists.

---

For any $n\in N$, we define $Z_n:\Pi \stackrel{\text{k}}{\to }S$ by

$$Z_n\pi \left(s\right):=\underset{x\sim H\pi }{\mathrm{Pr}}[x_n=s]$$

Proof of Proposition 2

By Proposition A.2, there is a quantilal policy ${\pi }^{\ast }:S^{\ast }\times S\stackrel{\text{k}}{\to }A$. We define ${\pi }^{†}:N\times S\stackrel{\text{k}}{\to }A$ by

$${\pi }^{†}(n,s):=\underset{x\sim H{\pi }^{\ast }}{E}\left[{\pi }^{\ast }\right(x_{:n},s\left)\right|x_n=s]$$

We now prove by induction that for any $n\in N$, $Z_n{\pi }^{\ast }=Z_n{\pi }^{†}$.

For $n=0$, we have $Z_0{\pi }^{\ast }=Z_0{\pi }^{†}={\zeta }_0$.

For any $n\in N$ and any $\pi :S^{\ast }\times S\stackrel{\text{k}}{\to }A$, we have

$$Z_{n+1}\pi \left(t\right)=\underset{x\sim H\pi }{\mathrm{Pr}}[x_{n+1}=t]=\underset{s\sim Z_n\pi }{E}\left[\underset{x\sim H\pi }{\mathrm{Pr}}[x_{n+1}=t|x_n=s]\right]=\underset{s\sim Z_n\pi }{E}\left[\underset{\begin{array}{c}x\sim H\pi \\ a\sim \pi (x_{:n},s)\end{array}}{E}\left[T\left(t\right|s,a)\right|x_n=s]\right]$$

To complete the induction step, observe that, by definition of ${\pi }^{†}$

$$\underset{\begin{array}{c}x\sim H\pi \\ a\sim {\pi }^{\ast }(x_{:n},s)\end{array}}{E}\left[T\left(t\right|s,a)\right|x_n=s]=\underset{a\sim {\pi }^{†}(n,s)}{E}\left[T\left(t\right|s,a)\right]=\underset{\begin{array}{c}x\sim H\pi \\ a\sim {\pi }^{†}(n,s)\end{array}}{E}\left[T\left(t\right|s,a)\right|x_n=s]$$

Now, for any $\pi$, $Z\pi =\underset{n\sim \gamma }{E}\left[Z_n\pi \right]$ and therefore $Z{\pi }^{†}=Z{\pi }^{\ast }$. We conclude that ${\pi }^{†}$ is also quantilal.

Proof of Proposition 3

By Proposition 2, there is ${\pi }^{\ast }:N\times S\stackrel{\text{k}}{\to }A$ which is a Markov quantilal policy. We have

$$Z_{n+1}{\pi }^{\ast }\left(t\right)=\underset{x\sim H{\pi }^{\ast }}{\mathrm{Pr}}[x_{n+1}=t]=\underset{s\sim Z_n{\pi }^{\ast }}{E}\left[\underset{x\sim H{\pi }^{\ast }}{\mathrm{Pr}}[x_{n+1}=t|x_n=s]\right]=\underset{\begin{array}{c}s\sim Z_n{\pi }^{\ast }\\ a\sim {\pi }^{\ast }(n,s)\end{array}}{E}\left[T\left(t\right|s,a)\right]$$

Taking the expected value of this equation w.r.t. $n\sim \gamma$ we get

$$\underset{n\sim \gamma }{E}\left[Z_{n+1}{\pi }^{\ast }\right]=\underset{\begin{array}{c}n\sim \gamma \\ s\sim Z_n{\pi }^{\ast }\\ a\sim {\pi }^{\ast }(n,s)\end{array}}{E}\left[T\right(s,a\left)\right]$$

Also, we have

$$Z{\pi }^{\ast }=\underset{n\sim \gamma }{E}\left[Z_n{\pi }^{\ast }\right]=(1-\lambda )\sum _{n=0}^{\infty }{\lambda }^n{Z}_n{\pi }^{\ast }=(1-\lambda )({\zeta }_0+\lambda \sum _{n=0}^{\infty }{\lambda }^n{Z}_{n+1}{\pi }^{\ast })=(1-\lambda ){\zeta }_0+\lambda \underset{n\sim \gamma }{E}\left[Z_{n+1}{\pi }^{\ast }\right]$$

It follows that

$$Z{\pi }^{\ast }=(1-\lambda ){\zeta }_0+\lambda \underset{\begin{array}{c}n\sim \gamma \\ s\sim Z_n{\pi }^{\ast }\\ a\sim {\pi }^{\ast }(n,s)\end{array}}{E}\left[T\right(s,a\left)\right]$$

$$Z{\pi }^{\ast }=(1-\lambda ){\zeta }_0+\lambda \underset{s\sim Z{\pi }^{\ast }}{E}\left[\underset{\begin{array}{c}n\sim \gamma \\ t\sim Z_n{\pi }^{\ast }\\ a\sim {\pi }^{\ast }(n,s)\end{array}}{E}\left[T\right(s,a\left)\right|t=s]\right]$$

Define ${\pi }^{†}:S\stackrel{\text{k}}{\to }A$ by

$${\pi }^{†}\left(s\right):=\underset{\begin{array}{c}n\sim \gamma \\ t\sim Z_n{\pi }^{\ast }\end{array}}{E}\left[{\pi }^{\ast }\right(n,s\left)\right|t=s]$$

We get

$$Z{\pi }^{\ast }=(1-\lambda ){\zeta }_0+\lambda \underset{s\sim Z{\pi }^{\ast }}{E}\left[\underset{a\sim {\pi }^{†}\left(s\right)}{E}\left[T\right(s,a\left)\right]\right]$$

Define the linear operator $T^{†}:R^S\to R^S$ by the matrix

$$T_{ts}^{†}:=\underset{a\sim {\pi }^{†}\left(s\right)}{E}\left[T\left(t\right|s,a)\right]$$

Viewing $\Delta S$ as a subset of $R^S$, we get

$$Z{\pi }^{\ast }=(1-\lambda ){\zeta }_0+\lambda T^{†}Z{\pi }^{\ast }$$

$$Z{\pi }^{\ast }=(1-\lambda ){(1-\lambda T^{†})}^{-1}{\zeta }_0$$

On the other hand, we have

$$Z{\pi }^{†}=(1-\lambda )\sum _{n=0}^{\infty }{\lambda }^n{T}^{†n}{\zeta }_0=(1-\lambda ){(1-\lambda T^{†})}^{-1}{\zeta }_0$$

Therefore, $Z{\pi }^{†}=Z{\pi }^{\ast }$ and ${\pi }^{†}$ is also quantilal.

Proposition A.3

Assume geometric time discount. Consider any $\zeta \in \Delta S$. Define the linear operators $I:R^S\to R^{S\times A}$ and $T:R^S\to R^{S\times A}$ by the matrices

$$I_{sa,t}:=\left[\right[t=s\left]\right]$$

$$T_{sa,t}:=T\left(t\right|s,a)$$

Define the linear operator $A:R^S\oplus R^S\to R^{S\times A}\oplus R^S\oplus R$ by

$$A(V,P):=((I-\lambda T)V+\eta (1-\lambda )IP,P,-\underset{\zeta }{E}\left[P\right])$$

Define $B\in R^{S\times A}\oplus R^S\oplus R$ by

$$B:=\left(\right(1-\lambda )IR,0,-1)$$

Define $D\subseteq R^S\oplus R^S$ as follows

$$D:=\{X\in R^S\oplus R^S|AX\ge B\}$$

Here, vector inequalities are understood to be componentwise.

Then,

$${\mathrm{QV}}^{\zeta }:=\underset{\pi :S^{\ast }\times S\stackrel{\text{k}}{\to }A}{sup}(\underset{Z\pi }{E}\left[R\right]-\eta \exp D_{\infty }\left(Z\pi \right|\left|\zeta \right))=\underset{(V,P)\in D}{inf}\underset{{\zeta }_0}{E}\left[V\right]$$

In particular, if $\zeta =Z\sigma$, the above expression describes $\mathrm{QV}$

Proof of Proposition A.3

Denote ${\Pi }_{det}:=\{S^{\ast }\times S\to A\}$. As usual in extensive-form games, behavioral strategies are equivalent to mixed strategies and therefore the image of the pushforward operator $Z_{\ast }:\Delta {\Pi }_{det}\to \Delta S$ is the same as the image of $Z:\Pi \to \Delta S$. It follows that

$$\mathrm{QV}=\underset{\mu \in \Delta {\Pi }_{det}}{sup}\underset{P:S\to [0,\infty )}{inf}\left\{\underset{Z_{\ast }\mu }{E}[R-\eta P]\right|\underset{\zeta }{E}\left[P\right]\le 1\}$$

${\Pi }_{det}$ is a compact Polish space (in the sense of the product topology) and therefore $\Delta {\Pi }_{det}$ is compact in the weak topology. By Sion's minimax theorem

$$\mathrm{QV}=\underset{P:S\to [0,\infty )}{inf}\underset{\pi \in {\Pi }_{det}}{max}\left\{\underset{Z\pi }{E}[R-\eta P]\right|\underset{\zeta }{E}\left[P\right]\le 1\}$$

Now consider any $X=(V,P)\in D$. $AX\ge B$ implies (looking at the $R^{S\times A}$ component) that

$$(I-\lambda T)V+\eta (1-\lambda )IP\ge (1-\lambda )IR$$

$$(I-\lambda T)V\ge (1-\lambda )I(R-\eta P)$$

$$V\left(s\right)-\lambda \sum _{t\in S}T\left(t\right|s,a)V\left(t\right)\ge (1-\lambda )\left(R\right(s)-\eta P(s\left)\right)$$

$$V\left(s\right)\ge (1-\lambda )\left(R\right(s)-\eta P(s\left)\right)+\lambda \underset{a\in A}{max}\sum _{t\in S}T\left(t\right|s,a)V\left(t\right)$$

Therefore, there is some $R^{\prime }\ge R$ s.t.

$$V\left(s\right)=(1-\lambda )\left(R^{\prime }\right(s)-\eta P(s\left)\right)+\lambda \underset{a\in A}{max}\sum _{t\in S}T\left(t\right|s,a)V\left(t\right)$$

The above is the Bellman equation for a modified MDP with reward function $R^{\prime }-\eta P$. Denote $Z_s$ the version of the $Z$ operator for the initial state $s$ (instead of ${\zeta }_0$). We get

$$V\left(s\right)=\underset{\pi \in {\Pi }_{det}}{max}\underset{Z_s\pi }{E}[R^{\prime }-\eta P]\ge \underset{\pi \in {\Pi }_{det}}{max}\underset{Z_s\pi }{E}[R-\eta P]$$

Observing that $\underset{s\sim {\zeta }_0}{E}\left[Z_s\pi \right]=Z\pi$, we get

$$\underset{{\zeta }_0}{E}\left[V\right]\ge \underset{s\sim {\zeta }_0}{E}\left[\underset{\pi \in {\Pi }_{det}}{max}\underset{Z_s\pi }{E}[R-\eta P]\right]\ge \underset{\pi \in {\Pi }_{det}}{max}\underset{Z\pi }{E}[R-\eta P]$$

On the other hand, for any $P\in R^S$ s.t. $P\ge 0$ and $\underset{Z\sigma }{E}\left[P\right]\le 1$ (these inequalities correspond to the $R^S\oplus R$ component of $AX\ge B$), there is $(V,P)\in D$ s.t.

$$\underset{{\zeta }_0}{E}\left[V\right]=\underset{\pi \in {\Pi }_{det}}{max}\underset{Z\pi }{E}[R-\eta P]$$

Namely, this $V$ is the solution of the Bellman equation for the reward function $R-\eta P$. Therefore, we have

$$\underset{\pi \in {\Pi }_{det}}{max}\underset{Z\pi }{E}[R-\eta P]=\underset{V\in R^S}{min}\left\{\underset{{\zeta }_0}{E}\left[V\right]\right|(V,P)\in D\}$$

Taking the infimum of both sides over $P$ inside the domain $\{P\ge 0,\underset{\zeta }{E}\left[P\right]\le 1\}$ we get

$${\mathrm{QV}}^{\zeta }=\underset{P:S\to [0,\infty )}{inf}\underset{\pi \in {\Pi }_{det}}{max}\left\{\underset{Z\pi }{E}[R-\eta P]\right|\underset{\zeta }{E}\left[P\right]\le 1\}=\underset{(V,P)\in D}{inf}\underset{{\zeta }_0}{E}\left[V\right]$$

Proof of Proposition 4

Consider the characterization of $\mathrm{QV}$ in Proposition A.3. By general properties of systems of linear inequalities, there is some $J\subseteq (S\times A)\bigsqcup S\bigsqcup \{\bullet \}$ s.t.

$$D_J^{♯}:=\{X\in R^S\oplus R^S|A_{J}X=B_J\}\subseteq \underset{(V,P)\in D}{argmin}\underset{{\zeta }_0}{E}\left[V\right]$$

Here, the notation $A_J$ means taking the submatrix of $A$ consisting of the rows corresponding to $J$. Similarly, $B_J$ is the subvector of $B$ consisting of the components corresponding to $J$.

(To see this, use the fact that the minimum of a linear function on a convex set is always attained on the boundary, and apply induction by dimension.)

Moreover, $D_J^{♯}$ has to be a single point $X_J\in R^S\oplus R^S$. Indeed, if it has more than one point then it contains a straight line $L$. The projection of $L$ on the second $R^S$ has to be a single point $P_0$, otherwise some point in $L$ violates the inequality $P\ge 0$ which would contradict $L\subseteq D$. Therefore, the projection of $L$ on the first $R^S$ is also a straight line $L^{\prime }$. As in the proof of Proposition A.3, for any $(V,P)\in D$, $V\left(s\right)$ is an upper bound on the value of state $s$ in the MDP with reward function $R-\eta P$. In particular, if $(V,P_0)\in D$ then $V\left(s\right)\ge {min}_{t\in S}\left(R\right(t)-\eta P_0(t\left)\right)$. However, since $L^{\prime }$ is a line, there must be some $s^{\ast }\in S$ s.t. $V\left(s^{\ast }\right)$ can be any real number for some $(V,P_0)\in L$. This is a contradiction.

Denote $Q:R^S\oplus R^S\to R^S$ the projection operator on the first direct summand. It follows that we can always choose $J$ s.t. $\left|J\right|=2\left|S\right|$ and we have

$$X_J=A_J^{-1}{B}_J$$

$$\mathrm{QV}=\underset{{\zeta }_0}{E}\left[Q{A}_J^{-1}{B}_J\right]$$

For each $J$, the expression on the right hand side is a rational function of ${\zeta }_0$ and the matrix elements of $A$ and $B$ which, in turn, are polynomials in the parameters the dependence on which we are trying to establish. Therefore, this expression is a rational function in those parameters (unless $det{A}_J$ vanishes identically, in which case this $J$ can ignored). So, $\mathrm{QV}$ always equals one of a finite set of rational functions (corresponding to difference choices of $J$). The continuity of $\mathrm{QV}$ also easily follows from its characterization as ${min}_{(V,P)\in D}\underset{{\zeta }_0}{E}\left[V\right]$.

Proposition A.4

Assume geometric time discount and stationary $\sigma$. Then, $Z\sigma$ is a rational function of $\sigma$, $T$, ${\zeta }_0$ and $\lambda$ with rational coefficients.

Proof of Proposition A.4

Define the linear operator $T^{\sigma }:R^S\to R^S$ by the matrix

$$T_{ts}^{\sigma }=\underset{a\sim \sigma \left(s\right)}{E}\left[T\left(t\right|s,a)\right]$$

We have

$$Z\sigma =(1-\lambda )\sum _{n=0}^{\infty }{\lambda }^n{T}^{\sigma n}{\zeta }_0=(1-\lambda ){(1-\lambda T^{\sigma })}^{-1}{\zeta }_0$$

Proof of Corollary 1

By Propositions 4 and A.4, $\mathrm{QV}$ is a continuous piecewise rational function of $\lambda$ with a finite number of pieces. Two rational functions can only coincide at a finite number of points (since a polynomial can only have a finite number of roots), therefore there is only a finite number of values of $\lambda$ in which $\mathrm{QV}$ "switches" from one rational function to another. It follows that there is some ${\lambda }_0\in [0,1)$ s.t. $\mathrm{QV}$ is a fixed rational function of $\lambda$ in the interval $[{\lambda }_0,1)$.

Moreover, it always holds that

$$\underset{s\in S}{min}R\left(s\right)-\eta \le \mathrm{QV}\le \underset{s\in S}{max}R\left(s\right)$$

The first inequality holds since, the guaranteed performance of the quantilal policy is at least as good as the guaranteed performance of $\sigma$. The second inequality is a consequence of the requirement that $P$ is non-negative.

It follows that $\mathrm{QV}$ cannot have a pole at $\lambda =1$ and therefore must converge to a finite value there.

Proof of Proposition 5

The algorithm for $\mathrm{QV}$ is obtained from Proposition A.3 using linear programming.

The claim regarding $Z\sigma$ for stationary $\sigma$ follows from Proposition A.4.

We now describe the algorithm for computing an $ϵ$-equilibrium.

For any $a\in A$, define $d_a:A\bigsqcup \left\{\perp \right\}\to A$ by

$$d_a\left(b\right):=\{\begin{array}{c}a\text{if}b=\perp \\ b\text{otherwise}\end{array}$$

Consider any $\beta :S\stackrel{\text{k}}{\to }A\bigsqcup \left\{\perp \right\}$. We define $T_{\beta }:S\times A\stackrel{\text{k}}{\to }S$ by

$$T_{\beta }(s,a):=\underset{b\sim \beta \left(s\right)}{E}\left[T(s,d_a(b\left)\right)\right]$$

Let $Z_{\beta }:\Pi \stackrel{\text{k}}{\to }S$ be the $Z$-operator for the MDP with transition kernel $T_{\beta }$, and define

$${\mathrm{QV}}_{\beta }:=\underset{\pi :S^{\ast }\times S\stackrel{\text{k}}{\to }A}{sup}(\underset{Z_{\beta }\pi }{E}\left[R\right]-\eta \exp D_{\infty }\left(Z_{\beta }\pi \right|\left|Z\sigma \right))$$

It is easy to see that ${\mathrm{QV}}_{\beta }=\mathrm{QV}$ if an only if there is $\pi :S\stackrel{\text{k}}{\to }A$ quantilal s.t. $\pi \left(a\right|s)\ge \beta \left(a\right|s)$. Indeed, the MDP with kernel $T_{\beta }$ is equivalent to the original MDP under the constraint that, when in state $s$, any action $a$ has to be taken with the minimal probability $\beta \left(a\right|s)$. In particular ${\mathrm{QV}}_{\beta }\le \mathrm{QV}$ (since we constrained the possible policies but not the possible penalties). So, if $\pi$ as above exists, then we can use it to construct a stationary policy for the new MDP with guaranteed value $\mathrm{QV}$. Conversely, if the new MDP has a stationary policy with guaranteed value $\mathrm{QV}$ then it can be used to construct the necessary $\pi$.

Using Proposition A.3, we can compute ${\mathrm{QV}}_{\beta }$ for any rational $\beta$ by linear programming. This allows us to find the desired policy by binary search on $\beta$, one (state,action) pair at a time.