Vanessa Kosoy comments on The Credit Assignment Problem

[Vanessa Kosoy]

Actually I was somewhat confused about what the right update rule for fuzzy beliefs is when I wrote that comment. But I think I got it figured out now.

First, background about fuzzy beliefs:

Let $E$ be the space of environments (defined as the space of instrumental states in Definition 9 here). A fuzzy belief is a concave function $\varphi :E\to [0,1]$ s.t. $sup\varphi =1$. We can think of it as the membership function of a fuzzy set. For an incomplete model $\Phi \subseteq E$, the corresponding $\varphi$ is the concave hull of the characteristic function of $\Phi$ (i.e. the minimal concave $\varphi$ s.t. $\varphi \ge {\chi }_{\Phi }$).

Let $\gamma$ be the geometric discount parameter and $U\left(\gamma \right):=(1-\gamma ){\sum }_{n=0}^{\infty }{\gamma }^n{r}_n$ be the utility function. Given a policy $\pi$ (EDIT: in general, we allow our policies to explicitly depend on $\gamma$), the value of $\pi$ at $\varphi$ is defined by

$$V_{\pi }(\varphi ,\gamma ):=1+\underset{\mu \in E}{inf}(E_{\mu \pi }\left[U\right(\gamma \left)\right]-\varphi (\mu \left)\right)$$

The optimal policy and the optimal value for $\varphi$ are defined by

$${\pi }_{\varphi ,\gamma }^{\ast }:=\arg \underset{\pi }{max}{V}_{\pi }(\varphi ,\gamma )$$ $$V(\varphi ,\gamma ):=\underset{\pi }{max}{V}_{\pi }(\varphi ,\gamma )$$

Given a policy $\pi$, the regret of $\pi$ at $\varphi$ is defined by

$${Rg}_{\pi }(\varphi ,\gamma ):=V(\varphi ,\gamma )-V_{\pi }(\varphi ,\gamma )$$

$\pi$ is said to learn $\varphi$ when it is asymptotically optimal for $\varphi$ when $\gamma \to 1$, that is

$$\underset{\gamma \to 1}{lim}{Rg}_{\pi }(\varphi ,\gamma )=0$$

Given $\zeta$ a probability measure over the space fuzzy hypotheses, the Bayesian regret of $\pi$ at $\zeta$ is defined by

$${BRg}_{\pi }(\zeta ,\gamma ):=E_{\varphi \sim \zeta }\left[{Rg}_{\pi }\right(\varphi ,\gamma \left)\right]$$

$\pi$ is said to learn $\zeta$ when

$$\underset{\gamma \to 1}{lim}{BRg}_{\pi }(\zeta ,\gamma )=0$$

If such a $\pi$ exists, $\zeta$ is said to be learnable. Analogously to Bayesian RL, $\zeta$ is learnable if and only if it is learned by a specific policy ${\pi }_{\zeta }^{\ast }$ (the Bayes-optimal policy). To define it, we define the fuzzy belief ${\varphi }_{\zeta }$ by

$${\varphi }_{\zeta }\left(\mu \right):=\underset{(\sigma :supp\zeta \to E):E_{\varphi \sim \zeta }\left[\sigma \right(\varphi \left)\right]=\mu }{sup}{E}_{\varphi \sim \zeta }\left[\varphi \left(\sigma \right(\varphi \left)\right)\right]$$

We now define ${\pi }_{\zeta }^{\ast }:={\varphi }_{{\varphi }_{\zeta }}^{\ast }$.

Now, updating: (EDIT: the definition was needlessly complicated, simplified)

Consider a history $h\in {(A\times O)}^{\ast }$ or $h\in {(A\times O)}^{\ast }\times A$. Here $A$ is the set of actions and $O$ is the set of observations. Define ${\mu }_{\varphi }^{\ast }$ by

$${\mu }_{\varphi }^{\ast }:=\arg \underset{\mu \in E}{max}\underset{\pi }{min}\left(\varphi \right(\mu )-E_{\mu \pi }[U\left]\right)$$

Let $E^{\prime }$ be the space of “environments starting from $h$”. That is, if $h\in {(A\times O)}^{\ast }$ then $E^{\prime }=E$ and if $h\in {(A\times O)}^{\ast }\times A$ then $E^{\prime }$ is slightly different because the history now begins with an observation instead of with an action.

For any $\mu \in E,\nu \in E^{\prime }$ we define ${\left[\nu \right]}_h\mu \in E$ by

$${\left[\nu \right]}_h\mu (o\mid h^{\prime }):=\{\begin{array}{c}\nu (o\mid h^{\prime \prime })\text{if}{h}^{\prime }=h{h}^{\prime \prime }\\ \mu (o\mid h^{\prime })\text{otherwise}\end{array}$$

Then, the updated fuzzy belief is

$$(\varphi \mid h)\left(\nu \right):=\varphi \left({\left[\nu \right]}_h{\mu }_{\varphi }^{\ast }\right)+\text{constant}$$