Subagent perfect minimax

post by Vanessa Kosoy (vanessa-kosoy) · 2017-01-06T13:47:12.000Z · LW · GW · 0 comments

% operators that are separated from the operand by a space

% operators that require brackets

% operators that require parentheses

% Paper specific

This post continues the study of minimax forecasting.

The minimax decision rule has the pathology that, when events are sufficiently "optimistic", behavior can become highly suboptimal. This is analogous to off-policy irrational behavior in Nash equilibria of games in extensive form. In order to remedy the problem, we introduce a refinement called "subagent perfect minimax," somewhat analogous to subgame perfect equilibria and other related solution concepts. It is possible to prove existence and, when the model factorizes, dynamic consistency.

The proofs are omitted, but we can easily provide them if necessary.

##Motivation

Consider the following class of environments: during the first step, the agent gains 1$ or action $b$ which leads to gaining $$0$.

The minimax payoff of this class is 0$ in the first step, choose $b$ if you gained 1$,whichisthesameastheworst-case($p=0$) payoff of ${\pi }^{\ast }$.

Note that the minimax environment has $p=0$ and $\pi$ only differs from ${\pi }^{\ast }$ on histories which are impossible in that environment. Moreover, if we considered the class $p\in [ϵ,1]$ for some $ϵ>0$, the minimax payoff would be $$(1+\epsilon)$, and \(\pi^*\) would be the sole minimax policy. Therefore, in order to eliminate the pathology, we need to formulate a stability condition that ensures any admissible history is treated as occurring with at least infinitesimal probability.

##Results

Now consider the forecasting setting, with action set $A$, observation set $O$, time discount function $\gamma :N\to R^{\ge 0}$ and reward function $r:(A\times O{)}^{\ast }\to R$. As before, $\gamma$ and $r$ define the utility function $u:(O^{\ast }\to A)\times O^{\omega }\to R$.

Consider $\Phi \in P_C\left(O^{\omega }\right)$ and denote

$$O_{\Phi }^{+}:=\{x\in O^{+}\mid \exists \mu \in \Phi :\mu (x{O}^{\omega })>0\}$$

#Definition 1

Consider $X\subseteq O_{\Phi }^{+}$ finite. ${\pi }^{\ast }\in P(O^{\ast }\to A)$ is called an $X$-stable minimax policy for $\Phi$ when there are sequences $\{{ϵ}^{\left(n\right)}:X\to (0,1){\}}_{n\in N}$ and $\{{\pi }^{\left(n\right)}\in P(O^{\ast }\to A){\}}_{n\in N}$ s.t. ${ϵ}^{\left(n\right)}\to 0$, ${\pi }^{\left(n\right)}\to {\pi }^{\ast }$ and ${\pi }^{\left(n\right)}$ is a minimax policy for

$${\Phi }^{\left(n\right)}:=\{\mu \in \Phi \mid \forall x\in O^{\ast },o\in O:xo\in X⟹\mu (xo{O}^{\omega })\ge {ϵ}^{\left(n\right)}(xo\left)\mu \right(x{O}^{\omega }\left)\right\}$$

In particular, the definition assumes ${\Phi }^{\left(n\right)}$ is non-empty.

#Proposition 1

For any $X\subseteq O_{\Phi }^{+}$ finite, there exists ${\pi }^{\ast }\in P(O^{\ast }\to A)$ which is an $X$-stable minimax policy for $\Phi$.

#Proposition 2

For any $X\subseteq O_{\Phi }^{+}$ finite and ${\pi }^{\ast }\in P(O^{\ast }\to A)$ an $X$-stable minimax policy for $\Phi$, ${\pi }^{\ast }$ is in particular a minimax policy for $\Phi$.

#Proposition 3

Consider $X\subseteq O_{\Phi }^{+}$ finite, ${\pi }^{\ast }\in P(O^{\ast }\to A)$ an $X$-stable minimax policy for $\Phi$ and $x\in O^{\ast }$ s.t. $\forall y⊑x:y\in X\cup \left\{{\lambda }_O\right\}$. Assume $\Phi$ factorizes at $x$ into ${\Phi }_1,{\Phi }_2\in P_C\left(O^{\omega }\right)$. Denote ${\mathrm{pr}}_1:(O^{\ast }\to A)\to (\overline{x}{O}^{\ast }\to A)$ and ${\mathrm{pr}}_2:(O^{\ast }\to A)\to (x{O}^{\ast }\to A)$ the restriction mappings. Define ${\pi }_1^{\ast }:={\mathrm{pr}}_{1\ast }\pi$ and define ${\pi }_2^{\ast }:A^{\left|x\right|}\to (x{O}^{\ast }\to A)$ by

$${\pi }_2^{\ast }\left(t\right):={\mathrm{pr}}_{2\ast }({\pi }^{\ast }\mid \{s:O^{\ast }\to A\mid t_i=s\left(x_{<i}\right)\left\}\right)$$

Then

$${\pi }_2^{\ast }\in \underset{{\pi }_2:A^{\left|x\right|}\to (x{O}^{\ast }\to A)}{argmax}\underset{\mu \in {\Phi }_2}{min}{E}_{\left({\pi }_1^{\ast }{\otimes }_x{\pi }_2\right)\times \mu }\left[u_{>\left|x\right|}\right]$$

---

Note that, thanks to $X$-stability, Proposition 3 doesn't require the condition ${min}_{\mu \in {\Phi }_1}\mu \left(x{O}^{\omega }\right)>0$, as opposed to the case for arbitrary minimax policies (see Proposition 1 here).

#Definition 2

${\pi }^{\ast }\in P(O^{\ast }\to A)$ is called a subagent perfect minimax policy for $\Phi$ when there is a sequence $\{X^{\left(n\right)}\subseteq O_{\Phi }^{+}{\}}_{n\in N}$ s.t. each $X^{\left(n\right)}$ is finite, $X^{\left(n\right)}\subseteq X^{(n+1)}$ and ${\bigcup }_{n\in N}{X}^{\left(n\right)}=O_{\Phi }^{+}$, and a sequence ${\pi }^{\left(n\right)}\in P(O^{\ast }\to A)$ s.t. ${\pi }^{\left(n\right)}\to \pi$ and ${\pi }^{\left(n\right)}$ is an $X^{\left(n\right)}$-stable minimax policy for $\Phi$.

#Proposition 4

There exists ${\pi }^{\ast }\in P(O^{\ast }\to A)$ which is a subagent perfect minimax policy for $\Phi$.

#Proposition 5

For ${\pi }^{\ast }\in P(O^{\ast }\to A)$ a subagent perfect minimax policy for $\Phi$, ${\pi }^{\ast }$ is in particular a minimax policy for $\Phi$.

#Proposition 6

Consider ${\pi }^{\ast }\in P(O^{\ast }\to A)$ a subagent perfect minimax policy for $\Phi$ and $x\in O_{\Phi }^{+}$. Assume $\Phi$ factorizes at $x$ into ${\Phi }_1,{\Phi }_2\in P_C\left(O^{\omega }\right)$. Then

$${\pi }_2^{\ast }\in \underset{{\pi }_2:A^{\left|x\right|}\to (x{O}^{\ast }\to A)}{argmax}\underset{\mu \in {\Phi }_2}{min}{E}_{\left({\pi }_1^{\ast }{\otimes }_x{\pi }_2\right)\times \mu }\left[u_{>\left|x\right|}\right]$$

0 comments

Comments sorted by top scores.