AIL comments on Vanessa Kosoy’s Shortform

[AIL]

I am not sure I understand your use of $C\left(U\right)$ in the third from last paragraph where you define goal directed intelligence. As you define $C$ it is a complexity measure over programs $P$. I assume this was a typo and you mean $K\left(U\right)$? Or am I misunderstanding the definition of either $U$ or $C$?

[Vanessa Kosoy]

This is not a typo.

I’m imagining that we have a program $P$ that outputs (i) a time discount parameter $\gamma \in Q\cap [0,1)$, (ii) a circuit for the transition kernel of an automaton $T:S\times A\times O\to S$ and (iii) a circuit for a reward function $r:S\to Q$ (and, ii+iii are allowed to have a shared component to save computation time complexity). The utility function is $U:(A\times O{)}^{\omega }\to R$ defined by

$$U\left(x\right):=(1-\gamma )\sum _{n=0}^{\infty }{\gamma }^{n}r\left(s_n^x\right)$$

where $s^x\in S^{\omega }$ is defined recursively by

$$s_{n+1}^x=T(s,x_n)$$

[AIL]

Okay, I think this makes sense. The idea is trying to re-interpret the various functions in the utility function as a single function and asking about the notion of complexity on that function which combines the complexity of producing a circuit which computes that function and the complexity of the circuit itself.

But just to check: is T over $S\times A\times O\to S$? I thought T in utility functions only depended on states and actions $S\times A\to S$?

Maybe I am confused by what you mean by $S$. I thought it was the state space, but that isn’t consistent with $r$ in your post which was defined over $A\times O\to Q$? As a follow up: defining r as depending on actions and observations instead of actions and states (which e.g. the definition in POMDP on Wikipedia) seems like it changes things. So I’m not sure if you intended the rewards to correspond with the observations or ‘underlying’ states.

One more question, this one about the priors: what are they a prior over exactly? I will use the letters/​terms from https://​​en.wikipedia.org/​​wiki/​​Partially_observable_Markov_decision_process to try to be explicit. Is the prior capturing the “set of conditional observation probabilities” (O on Wikipedia)? Or is it capturing the “set of conditional transition probabilities between states” (T on Wikipedia)? Or is it capturing a distribution over all possible T and O? Or are you imaging that T is defined with U (and is non-random) and O is defined within the prior?
I ask because the term $D_{KL}\left({\zeta }_0||\zeta \right)$ will be positive infinity if $\zeta$ is zero for any value where ${\zeta }_0$ is non-zero. Which makes the interpretation that it is either O or T directly pretty strange (for example, in the case where there are two states $s_1$ and $s_2$ and two obersvations $o_1$ and $o_2$ an O where $P\left(s_i|o_i\right)=1$ and $P\left(s_i|o_j\right)=0$ if $i\ne j$ would have a KL divergence of infinity from the ${\zeta }_0$ if ${\zeta }_0$ had non-zero probability on $P\left(s_1|o_2\right)$). So, I assume this is a prior over what the conditional observation matrices might be. I am assuming that your comment above implies that T is defined in the utility function U instead, and is deterministic?

[Vanessa Kosoy]

Maybe I am confused by what you mean by $S$. I thought it was the state space, but that isn’t consistent with $r$ in your post which was defined over $A\times O\to Q$?

I’m not entirely sure what you mean by the state space.$S$ is a state space associated specifically with the utility function. It has nothing to do with the state space of the environment. The reward function in the OP is $(A\times O{)}^{\ast }\to R$, not $A\times O\to R$. I slightly abused notation by defining $r:S\to Q$ in the parent comment. Let’s say it’s $r^{\prime }:S\to Q$ and $r$ is defined by using $T$ to translate the history to the (last) state and then applying $r^{\prime }$.

One more question, this one about the priors: what are they a prior over exactly? …I ask because the term $D_{KL}\left({\zeta }_0||\zeta \right)$ will be positive infinity if $\zeta$ is zero for any value where ${\zeta }_0$ is non-zero.

The prior is just an environment i.e. a partial mapping $\zeta :(A\times O{)}^{\ast }\to \Delta O$ defined on every history to which it doesn’t itself assign probability $0$. The expression $D_{KL}\left(\xi ||\zeta \right)$ means that we consider all possible ways to choose a Polish space $X$, probability distributions $\mu ,\nu \in \Delta X$ and a mapping $f:X\times (A\times O{)}^{\ast }\to \Delta O$ s.t.$\zeta =E_{\mu }\left[f\right]$ and $\xi =E_{\nu }\left[f\right]$ (where the expected value is defined using the Bayes law and not pointwise, see also the definition of “instrumental states” here), and take the minimum over all of them of $D_{KL}\left(\nu ||\mu \right)$.