Back in my first post about ADT, I conjectured that $ADT$ might achieve sublinear regret relative to argmaxing for the true embedder, if some extra condition was imposed.

The Problem:

In the form of $ADT$ stated in that post, the game of chicken is a counterexample to Conjecture 1. In short, the "delusion" embedder $F$ (where the opponent is an identical $ADT$ agent) has argmax converge to going straight (because it will, in expectation, yield $0.81$ utility, while other strategies yield less utility.) Further, if the agent uses the delusion embedder less than $10\%$ of the time, then $E\left(F\right(a{m}^F\left)\right)$ will start being greater than $E\left(E\right(a{m}^E\left)\right)$ (where $E$ is the embedder that plugs the chosen action into both your action and your opponent's action), so it will start using the delusion embedder more often. Therefore, $10\%$ of the time, the $ADT$ agent rams into itself because it uses the delusion embedder.

Now, the reason why this embedder can't be removed is interesting. We can consider the agent to be reasoning as follows: "I don't know whether I'll pick the delusion embedder or the copy embedder. There's a $90\%$ chance that an $ADT$ agent will pick the copy embedder $E$, in which case $F\left(a{m}^F\right)$ will score highly, because $a{m}^F$ will just go straight, and $a{m}^E$ picks swerving with $90\%$ probability. Also, $E\left(F\right(ADT\left)\right)$ is around $0.729$, because about $90\%$ of the time, my foe picks the copy embedder and so do I, and about $10\%$ of the time, my foe picks the delusion embedder and so do I, and we ram into each other."

However, note that $E\left(F\right(a{m}^F\left)\right)$ (approximately $0.81$) systematically deviates from $E\left(F\right(ADT)|ADT=a{m}^F)$ (approximately $0$). This is pretty much Abram's criterion for CDT and EDT diverging. Plugging an action into the embedder tends to give a different result than plugging yourself into the embedder and conditioning on you taking that action. The second quantity is a more accurate estimate of the utility you can expect to get. However, you can't just use it in place of $E\left(F\right(a{m}^F\left)\right)$ because the conditional may give nonsensical answers if you almost certainly don't take the action, because conditionals on improbable events are less accurate. To rephrase this, using the conditional is vulnerable to the futarchy hack, where a trader with a lot of wealth bets on conditional contracts driving down the value of $F\left(ADT\right)|ADT=a{m}^F$, so the $ADT$ agent doesn't use embedder $F$, so $0$ dollars are lost on the conditional contracts, and the wealthy trader can repeat the same move forevermore and unilaterally prevent ever trying out embedder $F$.

The Solution:

Is there some way to address this? Yes. As stated in the comments of the last post on ADT, it is possible to improve the reality filter by switching from $|E_t\left(E_t\right(AD{T}_t\left)\right)-E_t\left(U_t\right)|<{\delta }_t$ to (using $F_t^{\ast }$ as an abbreviation for $AD{T}_t=a{m}_t^F$, because this means that embedder $F$ was chosen)

${\sum }_{F\in E}{P}_t\left(F_t^{\ast }\right)\cdot |E_t\left(E_t\right(AD{T}_t\left)|F_t^{\ast }\right)-E_t\left(U_t|F_t^{\ast }\right)|<{\delta }_t$

In short, the conditionals may be inaccurate, but if they are inaccurate, then $P_t\left(F_t^{\ast }\right)$ must be low, so the expected values being inaccurate is compensated for by being multiplied by a number close to zero.

It is possible to use the same sort of trick on the divergence between plugging in an action and plugging in yourself and conditioning on an action, and require

$P_t\left(E_t^{\ast }\right)\cdot |E_t\left(E_t\right(a{m}_t^E\left)\right)-E_t\left(E_t\right(AD{T}_t\left)|E_t^{\ast }\right)|<{\delta }_t^{\prime }$

for the embedder to be considered. This is a $CDT=EDT$ filter. Note that this condition isn't a hard constraint on all embedders, it just applies to embedders that are chosen with non-negligible probability. If a particular embedder is definitely not taken, the multiplication by a near-zero term will make the embedder pass the filter, and $E_t\left(E_t\right(a{m}_t^E\left)\right)$ (the $CDT$ utility) will be used as the utility for the embedder, since there's no conditional utility to defer to. However, if an embedder has non-negligible probability of being taken, and passes this filter, then $E_t\left(E_t\right(a{m}_t^E\left)\right)\simeq E_t\left(E_t\right(AD{T}_t\left)|E_t^{\ast }\right)$, which is pretty much equivalent to using the $EDT$ utility.

With the improved reality-filter, and the $CDT=EDT$ filter, we can arrive at a proof of Conjecture 1, modulo some extra conditions.

Required Conditions:

First, we must assume that the hypothesis space contains a "true environment" $E$, which is defined as follows. First, it passes the reality-filter (ie, the reality-filter converges to $1$). Second, it passes the $CDT=EDT$ filter (that converges to $1$). Note that if the series of utilities seen is acquired by feeding $E$ with a uniformly random bitstring on each turn, it will pass the reality-filter by an adaptation of Theorem 1 from the last post, by Kelly-betting on the exploitable difference between $E_t\left(E_t\right(AD{T}_t\left)|F_t^{\ast }\right)$ and $E_t\left(U_t|F_t^{\ast }\right)$, where the timely appearance of $U_t$ and the actual action in the deductive process lets the conditional bets be resolved quickly. The second condition isn't acquired by default, but it appears that in the known toy examples games where $CDT\ne EDT$, there is another environment that is equally accurate where the choice of action influences the opponent and $CDT=EDT$ in that environment.

Second, it's possible that the environment could be a perverse environment with clustering behavior, so $\frac{1}{t}\cdot {\sum }_{i\le t}{E}_i\left(E_i\right(a{m}_i^E\left)\right)-E_i\left(a{m}_i^E\right)$ doesn't limit to $0$, because feedback on what $E\left(a{m}^E\right)$ is may be quite sparse. Therefore, we have to assume that the true environment (whatever it may happen to be) is sufficiently "nice", in the sense that the time-average of the difference between the expectation of $E\left(a{m}^E\right)$ and $E\left(a{m}^E\right)$ itself limits to zero.

The third condition is very similar, that $\frac{1}{t}{\sum }_{i\le t}{E}_i\left(U_i\right)-U_i$ limits to zero. It's more plausible than the first assumption, because (an interval containing) the true value of $U$ appears in the deductive process in a timely manner by assumption, but I haven't found a way to implement Kelly-betting to exploit this, because the traders don't necessarily have access to the deductive process, or know their own worst-case value. It should be noted that the traders not knowing their own worst-case value is the property that necessitates emulating the entire logical inductor to implement budgeting, in the key $ϵ$-ROI lemma of the logical induction paper. Therefore, it makes sense to stipulate that traders are given their own worst-case value as an advice string, to streamline budgeting, and if the logical inductor is augmented in this way, this condition is attained for free via a Kelly-betting argument.

Final Proof:

We will get a necessary and simple lemma out of the way first.

Lemma 1: When there is a finite set of sequences of events $E$, which are mutually exclusive, and a sequence of LUV's $U_t$, then $E_t\left(U_t\right){\simeq }_t{\sum }_{F\in E}{P}_t\left(F_t^{\ast }\right)\cdot E_t\left(U_t|F_t^{\ast }\right)$

Proof: By the definition of $E_t\left(U_t|F_t^{\ast }\right)$, this is equivalent to the statement that $E_t\left(U_t\right){\simeq }_t{\sum }_{F\in E}{E}_t(U_t\cdot [F_t^{\ast }\left]\right)$, where the brackets are the Iverson brackets, which is just the indicator function that is $1$ if the statement is true, and $0$ if the statement is false.

Now, notice that the bounded combination sequences ${\sum }_{0\le i<t}\frac{1}{t}┌U_t>\frac{i}{t}┐$ and ${\sum }_{0\le i<t}{\sum }_{F\in E}\frac{1}{t}┌U_t\cdot \left[F_t^{\ast }\right]>\frac{i}{t}┐$ have provably equal values for all $t$, so by Theorem 4.5.4 in the logical induction paper, Affine Provability Induction, the prices on these sequences will limit to being equal. By the definition of expected value, the prices on these sequences are the prices of $E_t\left(U_t\right)$ and ${\sum }_{F\in E}{E}_t(U_t\cdot [F_t^{\ast }\left]\right)$, respectively.

Now to prove sublinear regret.

Theorem 1: If there is an embedder $E$ in the hypothesis class of an $ADT$ agent which is up against an environment $U$ such that

1: $\frac{1}{t}{\sum }_{i\le t}{E}_t\left(U_t\right)-U_t{\simeq }_{t}0$ (utility is learned)

2: $\frac{1}{t}{\sum }_{i\le t}{E}_t\left(E_t\right(a{m}_t^E\left)\right)-E_t\left(a{m}_t^E\right){\simeq }_{t}0$ (argmax behavior of $E$ is learned)

3: $in{d}_{{\delta }_t}\left({\sum }_{F\in E}{P}_t\right(F_t^{\ast })\cdot |E_t(E_t\left(AD{T}_t\right)|F_t^{\ast })-E_t(U_t|F_t^{\ast })|<{\delta }_t){\simeq }_{t}1$

($E$ passes the reality filter)

4: $in{d}_{{\delta }_t^{\prime }}\left(P_t\right(E_t^{\ast })\cdot |E_t(E_t\left(a{m}_t^E\right))-E_t(E_t\left(AD{T}_t\right)|E_t^{\ast })|<{\delta }_t^{\prime }){\simeq }_{t}1$

($E$ passes the $EDT=CDT$ filter),

then the $ADT$ agent on the true environment $U$ has sublinear regret relative to the argmax agent on $E$, ie, ${limsup}_{t\to \infty }\frac{1}{t}{\sum }_{i\le t}{E}_t\left(a{m}_t^E\right)-U_t\le 0$.

Proof: To begin with, by applying assumptions 1 and 2, we only need to prove that ${limsup}_{t\to \infty }\frac{1}{t}{\sum }_{i\le t}{E}_t\left(E_t\right(a{m}_t^E\left)\right)-E_t\left(U_t\right)\le 0$. In fact, we will prove a stronger result, that $E_t\left(U_t\right){\ge }_t{E}_t\left(E_t\right(a{m}_t^E\left)\right)$ (which immediately implies the desired result).

Assume this is false, so infinitely often $E_t\left(E_t\right(a{m}_t^E\left)\right)-ϵ>E_t\left(U_t\right)$ for some $ϵ$. Also, let $D_t^{ϵ}$ be the set of embedders with greater than $\frac{ϵ}{3|E|}$ probability of being chosen on turn $t$. By Lemma 1,

$E_t\left(U_t\right){\simeq }_t\sum _{F\in E}{P}_t\left(F_t^{\ast }\right)\cdot E_t\left(U_t|F_t^{\ast }\right)$

$\sum _{F\in E}{P}_t\left(F_t^{\ast }\right)\cdot E_t\left(U_t|F_t^{\ast }\right)\ge \sum _{F\in D_t^{ϵ}}{P}_t\left(F_t^{\ast }\right)\cdot E_t\left(U_t|F_t^{\ast }\right)$

In case 1, $\exists F\in D_t^{ϵ}$ that clearly fails the filters (ie, one of the two filters has the quantity inside of the filter be above $3{\delta }_t$or $3{\delta }_t^{\prime }$, as the case may be). Also $E_t\left(E_t\right(a{m}_t^E\left)\right)>\frac{ϵ}{3}$. Then in this case, it is possible for a trader to bet against $F$ being selected, because clearly failing a filter can be picked out by a continuous indicator function. $F$ won't be selected because its value is $0$, due to failing both filters, and $E$ passes both filters by conditions 3 and 4, and claims that it can attain value bounded away from $0$. This bet allows the trader to pick up a free$\frac{ϵ}{3|E|}$ dollars or more (due to the probability of $F$ being selected being bounded away from $0$ due to being in $D_t^{ϵ}$). Because this is a logical inductor, this case can only occur finitely many times.

In case 2, $\exists F\in D_t^{ϵ}$ that clearly fails a filter, also $E_t\left(E_t\right(a{m}_t^E\left)\right)\le \frac{ϵ}{3}$. In that case the regret is at most $\frac{ϵ}{3}$. Therefore, all but finitely many of the times where$E_t\left(E_t\right(a{m}_t^E\left)\right)-ϵ>E_t\left(U_t\right)$ occur in case 3.

Now, let $D_t^{{}^{\prime }ϵ}\subseteq D_t^{ϵ}$ be the set of plausible environments that don't clearly fail a filter. In case 3, these two sets are equal. By the reality-filters not being clearly failed, and the reality-filters enforcing the approximate equality of $E_t\left(U_t|F_t^{\ast }\right)$ and $E_t\left(F_t\right(AD{T}_t\left)|F_t^{\ast }\right)$, for all $F\in D_t^{{}^{\prime }ϵ}$ and ${\delta }_t$ limiting to $0$, we get that

$\sum _{F\in D_t^{{}^{\prime }ϵ}}{P}_t\left(F_t^{\ast }\right)\cdot E_t\left(U_t|F_t^{\ast }\right){\simeq }_t\sum _{F\in D_t^{{}^{\prime }ϵ}}{P}_t\left(F_t^{\ast }\right)\cdot E_t\left(F_t\right(AD{T}_t\left)|F_t^{\ast }\right)$

Then, by the $CDT=EDT$ filters not being clearly failed, which enforce the approximate equality of $E_t\left(F_t\right(AD{T}_t\left)|F_t^{\ast }\right)$ and $E_t\left(F_t\right(a{m}_t^E\left)\right)$, we get that

$\sum _{F\in D_t^{{}^{\prime }ϵ}}{P}_t\left(F_t^{\ast }\right)\cdot E_t\left(F_t\right(AD{T}_t\left)|F_t^{\ast }\right){\simeq }_t\sum _{F\in D_t^{{}^{\prime }ϵ}}{P}_t\left(F_t^{\ast }\right)\cdot E_t\left(F_t\right(a{m}_t^F\left)\right)$

Now, by conditions 3 and 4, the filters for $E$ must limit to $1$, so on all but finitely many turns, for all $F\in D_t^{{}^{\prime }ϵ}$, $E_t\left(F_t\right(a{m}_t^F\left)\right)>E_t\left(E_t\right(a{m}_t^E\left)\right)-\frac{ϵ}{3}$ (otherwise it is possible to bet against $F$ being chosen and get free money by the argument from case 1). Thus, we get that

$\sum _{F\in D_t^{{}^{\prime }ϵ}}{P}_t\left(F_t^{\ast }\right)\cdot E_t\left(F_t\right(a{m}_t^F\left)\right){\ge }_t\sum _{F\in D_t^{{}^{\prime }ϵ}}{P}_t\left(F_t^{\ast }\right)\cdot E_t\left(E_t\right(a{m}_t^E\left)\right)-\frac{ϵ}{3}$

Because we are in case 3 where $D_t^{{}^{\prime }ϵ}=D_t^{ϵ}$, and the probabilities of the embedders being selected approximately add up to $1$, and the total probability mass outside of $D_t^{ϵ}$ is at most $\frac{ϵ}{3}$ by the definition of $D_t^{ϵ}$, we get that

$\sum _{F\in D_t^{{}^{\prime }ϵ}}{P}_t\left(F_t^{\ast }\right)\cdot E_t\left(E_t\right(a{m}_t^E\left)\right)-\frac{ϵ}{3}{\ge }_t{E}_t\left(E_t\right(a{m}_t^E\left)\right)-\frac{2ϵ}{3}$

And putting it all together, we get that $E_t\left(U_t\right){\ge }_t{E}_t\left(E_t\right(a{m}_t^E\left)\right)-\frac{2ϵ}{3}$ , which contradicts the assumption that $E_t\left(U_t\right)<E_t\left(E_t\right(a{m}_t^E\left)\right)-ϵ$ infinitely often.

Therefore, $E_t\left(U_t\right){\ge }_t{E}_t\left(E_t\right(a{m}_t^E\left)\right)$ holds, which implies the theorem by assumptions 1 and 2.

Additional Discussion and Generalizing to Expanding Hypothesis Spaces:

There's an interesting feature of this. In the proof, only part of the reality-filter was actually used, and the part that was used can be combined with the $CDT=EDT$ filter to yield a single filter that suffices to prove sublinear regret on the true environment, which is:

$P_t\left(E_t^{\ast }\right)\cdot |E_t\left(E_t\right(a{m}_t^E\left)\right)-E_t\left(U_t|E_t^{\ast }\right)|<{\delta }_t^{\prime }$

However, this doesn't enforce that embedders accurately predict what happens when other embedders are selected by $ADT$, so it glosses over important information which can be used to rule out an embedder.

The obvious next question is whether it's possible to generalize the proof to a space of hypotheses that expands over time. We might hope to get a result that, for all computable environments that are "sufficiently nice", there is an $ADT$ agent with a sufficiently slow-growing hypothesis space that will eventually learn to act in accordance with the true environment. This runs into several obstacles.

Obstacle 1: The proof of Lemma 1 fails because the batch of statements of the form ${\sum }_{0\le i<t}{\sum }_{F\in E}\frac{1}{t}┌U_t\cdot \left[F_t^{\ast }\right]>\frac{i}{t}┐$ stops being a bounded combination sequence (because, all in all, the combination is composed of $|E|$ shares in total, which isn't bounded when $E$ grows over time).

Obstacle 2: The argument for Case 1 occuring finitely often (that failure allows you to pump free money out and if this recurs infinitely often you get infinite money) fails, because the amount of money you can pump out is $\frac{ϵ}{3|E|}$, but when $|E|$ grows over time, the money you can pump out lessens over time, in a way that may force convergence. I suspect it's possible to address this by shooting for a proof that even when the hypothesis space grows over time, it's possible to exploit the market unless the total probability mass on embedders that clearly fail their filters limits to zero.

Obstacle 3: The asymptotic equality linking ${\sum }_{F\in D_t^{{}^{\prime }ϵ}}{P}_t\left(F_t^{\ast }\right)\cdot E_t\left(U_t|F_t^{\ast }\right)$ and ${\sum }_{F\in D_t^{{}^{\prime }ϵ}}{P}_t\left(F_t^{\ast }\right)\cdot E_t\left(F_t\right(a{m}_t^F\left)\right)$ occurs because the difference between those two is bounded by $|E|({\delta }_t+{\delta }_t^{\prime })$, which limits to zero because ${\delta }_t$ and ${\delta }_t^{\prime }$ limit to zero. When $|E|$ grows over time, it requires ${\delta }_t$ and ${\delta }_t^{\prime }$ to shrink faster to get this to work out. So if you're adding one new hypothesis each turn, then ${\delta }_t$ and ${\delta }_t^{\prime }$ must shrink faster than $\frac{1}{t}$. And if ${\delta }_t$ and ${\delta }_t^{\prime }$ shrink too fast, then the true environment can't pass the reality filter either. So this means $|E|$ can't grow too fast.

Obstacle 4: This appears to be the largest obstacle. It's really hard to guarantee that the true environment passes the reality-filter. Even with a finite hypothesis space, the reality-filter "score" does limit to zero (although I haven't checked the proof particularly well), but going for any result along the lines of "this rate of ${\delta }_t$ approaching zero/level of strictness for the reality-filter is passed by the true environment" causes the proof to fail. It might even be uncomputably slow for all I know. As far as I can tell, this problem gets even worse when the size of the hypothesis class grows over time, and it might cause a failure of the original proof of the reality-filter "score" limiting to zero. It seems like the hard part is being shoved into the true environment being able to pass the filters in the first place. And limits on how fast ${\delta }_t$ can converge to zero translate directly into limits on how fast $|E|$ can grow by the third obstacle.