Logical Inductor Lemmas

The final lemma in this sequence will be necessary for use in an upcoming post about logical inductors and correlated equilibria, so it will be proved here in order to not clutter up that post.

Much of the notation in this is reused from the previous post, Two Notions of Best Response

Let $S_{1}$ be the set of actions available to player 1. $| S_{1} | = m$ . Given a matrix $M$ , $M_{j}$ refers to the $j$ -th row vector of $M$ . Given some vector $\to v$ , $| \to v |$ is defined in the usual way. In this post, $a_{j}$ is typically used to refer to some default action by player 1, and $a_{j^{'}}$ typically refers to some better action.

Consider the space $\prod_{i j} R$ . This would be a space of probabilities/prices assigned to the various joint outcomes, by some logical inductor. It’s possible to use expressible features to pick out fuzzy subsets of this space, by taking the prices of the various sentences as input and mapping them to $[0, 1]$ (in practice, the prices will always be in a hypercube, but it’ll be convenient to not have to deal with the special case where the prices are on an edge of the hypercube)

The infinite sequence ${p_{t}}_{t \in N^{+}}$ of points that lie in this space can be identified with the sequence of prices of the logical inductor on day $t$ .

Consider some fuzzy set/ $P$ -generable region in that space, bounded in [0,1], which we’ll denote by $C$ .

Let $α_{C} (k)$ be the number in [0,1] that the expressible feature $α$ which implements $C$ outputs when given the market prices of the day $k$ . By a slight abuse of notation, $α_{C} (p)$ refers to what the expressible feature would output if the market prices were given by the point $p$ .

$C \in B_{a_{j}}$ iff there’s a point $p \in s u p p (C)$ such that $p \in B_{a_{j}}$ . In words, there’s a point in $C$ where $a_{j}$ is an evidential best response.

Given some point $p$ , where some action $a_{j}$ has nonzero probability (for a well-defined expected utility), then an action $a_{j^{'}}$ dominates $a_{j}$ by $δ$ if $E U_{l o w e r} (a_{j^{'}}) = E U (a_{j}) + δ$ .

#Lemma 1:

When a point $p$ has $| P_{j} | \geq ϵ$ , all points $q$ in an $L_{1}$ -ball of size $δ$ around $p$ where $δ << ϵ$ will have $| E U_{q} (a_{j}) - E U_{p} (a_{j}) | \leq 2 δ$ . (approximately)

Proof:

$E U_{p} (a_{j}) = \frac{U_{j} \cdot P_{j}}{| P_{j} |} = \frac{U_{j} \cdot P_{j}}{ϵ} ≃ \frac{U_{j} \cdot P_{j} \pm δ}{ϵ \pm δ} = E U_{q} (a_{j})$

(here, $\pm δ$ should be interpreted to be any number in $[- δ, δ]$ , and it doesn’t necessarily have to be the same number on the top and bottom. Also, in the next line, $X$ will be used as an abbreviation for $U_{j} \cdot P_{j}$ , which is a number in $[0, ϵ]$ )

$\frac{U_{j} \cdot P_{j} \pm δ}{ϵ \pm δ} ≃ \frac{(X \pm δ) (ϵ \pm δ)}{ϵ^{2} - δ^{2}} ≃ \frac{ϵ X \pm δ X \pm ϵ δ}{ϵ^{2}} = \frac{X \pm δ \frac{X}{ϵ} \pm δ}{ϵ} ≃ E U_{p} (a_{j}) \pm 2 δ$

QED.

Now let ${max}_{n} (a_{j})$ be the n’th largest utility in the $j$ -th row of the utility matrix. ${max}_{2} (a_{j})$ refers to the highest utility less than the maximum utility, in the event that there are two actions with maximal utility. ${min}_{n}$ is defined similarly.

#Lemma 2:

For all points $p$ , there exists a change in probabilities by $ϵ$ (according to the $L_{1}$ -norm), for which the expected utility of the move $a_{j}$ can be increased by $({max}_{1} (a_{j}) - {max}_{2} (a_{j})) \frac{ϵ}{2}$ , or pushed to the highest attainable utility, whichever one is lower.

The same argument will also work to establish that the probabilities can be lowered by $({min}_{2} (a_{j}) - {max}_{2} (a_{j})) \frac{ϵ}{2}$ , or pushed to the lowest attainable utility, whichever one is higher.

Assume that the probability matrix $P$ has $P_{j} = \to 0$ Then there is an arbitrarily small change in probability that will have $a_{j}$ have the highest possible expected utility, and it is proved.

Assume that the probability matrix $P$ has $P_{j}$ have less than $\frac{ϵ}{2}$ probability, total, on the $i$ which correspond to non-maximal utilities in $U_{j}$ . Then there is an $ϵ$ -change in probabilities (take all the probability mass from non-optimal outcomes and put it on the best outcome) that makes $a_{j}$ have the highest possible expected utility, and it is proved.

Assume that the probability matrix $P$ has $P_{j}$ have $\frac{ϵ}{2}$ or greater probability, total, on the $i$ which correspond to non-maximal utilities in $U_{j}$ . Then by taking $\frac{ϵ}{2}$ probability mass from the non-optimal outcomes, and putting it on the optimal outcome, it is easy to verify from the expected utility equation that it will produce at least a $({max}_{1} (a_{j}) - {max}_{2} (a_{j})) \frac{ϵ}{2}$ increase in the expected utility.

#Lemma 3:

If there is a point $p$ for which no action $a_{j^{'}}$ dominates $a_{j}$ by a positive number, and there is a $P$ -generable fuzzy set $C \notin B_{a_{j}}$ , then $p$ must be on the boundary of $s u p p (C)$ , or on the exterior of $s u p p (C)$ .

Assume the opposite, that this point is on the interior of $C$ . Due to the continuity of the fuzzy set, and the fact that $a_{j}$ is not dominated by any positive number, then there is an arbitrarily small perturbation of the prices to make $a_{j}$ an evidential best response. Now there is a point where $a_{j}$ is an evidential best response in the support of $C$ . However, we assumed that the support of $C$ had no points where $a_{j}$ was an evidential best response. Therefore, there is a contradiction, and $p$ must either be on the boundary of $s u p p (C)$ , or the exterior of $s u p p (C)$ .

In both cases, due to continuity, this point must have $α_{c} (p) = 0$ .

#Lemma 4:

Given a $P$ -generable fuzzy set $C$ such that $C \notin M_{a_{j}}$ , and some $ϵ$ , then let . Then all points in $C^{'}$ have some action $a_{j^{'}}$ that dominates $a_{j}$ by $δ$ , for some positive constant $d e l t a$ .

To begin with, the function $α_{C}$ has some bounded lipschitz constant $L$ . Let $ϵ^{'} := \frac{ϵ}{2 L}$ .

Given a point $p \in C^{'}$ , associate each action with $E U_{l o w e r, p}$ for that action, and select an arbitrary highest-value action to be $a_{j^{'}}$ .

Consider the function $F (p)$ that uses the highest-value action for $p$ as $a_{j^{'}}$ , and then outputs $min ((max 1 (a_{j}) - max 2 (a_{j})) \frac{ϵ^{'}}{2}, (min 2 (a_{j^{'}}) - min 1 (a_{j^{'}})) \frac{ϵ^{'}}{2})$ when both of these terms are positive, and the term that is positive when the other term is 0. (we can ignore the case where both terms are 0, as we shall soon see)

To begin, assume that both terms are 0. That means that $E U (a_{j^{'}})$ and $E U (a_{j})$ are both constants. If $E U (a_{j^{'}}) > E U (a_{j})$ , then the theorem is proved. If they are equal, then one of two situations apply. In case 1, $a_{j^{'}}$ is never selected as one of the best actions, in which case we can ignore it. In case 2, $a_{j^{'}}$ is selected as one of the best actions somewhere in $C^{'}$ , and then no action would dominate $a_{j}$ by a positive number in the interior of $C$ , which is impossible by Lemma 3.

Therefore, assuming the theorem hasn’t been trivially proved yet, $F (p)$ is always defined for all $p \in C^{'}$ . Also, note that $F (p)$ is bounded below by a constant (because there are only finitely many actions, all of which have their corresponding term be a constant, or 0)

Select an arbitrary point $p$ , and the corresponding action, $a_{j^{'}}$ such that

$E U_{l o w e r, p} (a_{j^{'}}) - E U_{u p p e r, p} (a_{j}) < F (p)$

If there isn’t any, we’re done (and $δ = a r g m i n_{p} F (p)$ .

Otherwise, by Lemma 2, if we look at the $L_{1}$ ball of $ϵ^{'}$ -sized perturbations, one of two events will have occurred. In case 1, there’s a point in that ball where the “domination gap” given by $F (p)$ has been closed completely. In case 2, the maximum possible utility for $a_{j}$ is less than the minimum possible utility for $a_{j^{'}}$ , and the ball of size $ϵ^{'}$ has been ruled out, as all points in that ball have $a_{j^{'}}$ dominating $a_{j}$ by a fixed constant $δ$ .

In case 1, because the point $q$ where the utility gap closes is $ϵ^{'}$ -away from a point $p$ where $α_{C} (p) > ϵ$ , and $ϵ^{'} = \frac{ϵ}{2 L}$ , then $α_{C} (q) \geq \frac{ϵ}{2}$ (due to the bounded lipschitz constant of $α_{C}$ ) Then there’s a point where $a_{j}$ is not dominated on the interior of $C$ , which by Lemma 3, is impossible.

Therefore, case 2 must apply. However, because the worst-case utility of action $a_{j^{'}}$ dominates the best-case utility of action $a_{j}$ by $δ$ , our assumption that the theorem was false is false.

#Lemma 5:

Given some point $p$ where $a_{j^{'}}$ dominates $a_{j}$ by $δ$ or more, and $| P_{j} | > ϵ >> δ$ , and $p$ is more than $2 (m - 1) ϵ + \frac{δ}{3}$ from a point that is in $B_{a_{j}}$ (according to the $L_{1}$ norm), then the sequence of prices ${p_{t}}_{t \in N^{+}}$ will only finitely often be in the $L_{1}$ -ball of size ~ $\frac{δ}{6}$ around $p$ .

We will consider two cases, and prove them seperately.

In case 1, $| P_{j^{'}} | \geq ϵ$ .

By Lemma 1, the change in expected utility for $a_{j}$ and $a_{j^{'}}$ over the $\frac{δ}{6}$ $L_{1}$ ball will be about, or less than, $\frac{δ}{3}$ . Because $a_{j^{'}}$ dominates $a_{j}$ by $δ$ or more at $p$ , then in this ball, $a_{j^{'}}$ always dominates $a_{j}$ by $\frac{δ}{3}$ or more.

Now, there is a convex $P$ -generable fuzzy set $C$ which covers this ball (and a tiny region outside of it, due to the continuous indicator functions, but this doesn’t affect anything, because the support of that region still has $a_{j^{'}}$ dominating $a_{j}$ by about $\frac{δ}{3}$ or more). Assuming that there are infinitely many points in the ball (by contradiction), then by calibration, the empirical joint probabilities, summed over all time, will be within th support of $C$ .

To recap the definition of expected value for a logical inductor,

$E_{t} (U_{t} | a_{t} = j) = \frac{1}{t} i = t - 1 \sum i = 0 min ⎛ ⎝ \frac{P_{t} (" a_{t} = j " \land " U_{t} > \frac{i}{t} ")}{P_{t} (a_{t} = j)}, 1 ⎞ ⎠$

By assumption, $a_{t} = j$ has a positive probability around $ϵ$ or greater. By coherence, the logical inductor will eventually learn that the price on $a_{t} = j$ should equal the sum of the prices over all the other joint outcomes, so in the limit, $P_{t} (a_{t} = j) ≃_{t} | P_{j} |$ . A similar argument applies to learning the utilities of the various outcomes in the top of the fraction, so in the limit, $E_{t} (U_{t} | a_{t} = j) ≃_{t} E U (a_{j})$ .

Now, since $a_{j^{'}}$ also has probability bounded away from 0, then the same argument applies to it as well. The expected utilities will eventually be learned. Because there’s a $\frac{δ}{3}$ or larger difference in expected utilities, $a_{j}$ will be taken with limiting probability 0 when the prices are inside $C$ . However, due to calibration, the probability of $a_{j}$ must be bounded away from 0, so we have a contradiction, and the sequences of prices ${p_{t}}_{t \in N^{+}}$ must have only finitely many elements in the $L_{1}$ -ball.

Now for case 2. Assume case 1 is false, so for the point $p$ , for all $a_{j^{'}}$ which dominate $a_{j}$ by $δ$ or more, $| a_{j^{'}} | < ϵ$ .

Consider the $L_{1}$ -ball of size $\frac{δ}{6}$ around $p$ . There degree of improvement in $E U (a_{j})$ over the whole ball can be at most $\frac{δ}{3}$ , by Lemma 1. Let $δ^{'}$ be the maximum increase over $E U_{p} (a_{j})$ for $a_{j}$ , for the whole ball.

For each action $a_{j^{'}}$ that is not $a_{j}$ and has $E U_{l o w e r, p} (a_{j^{'}}) > E U_{u p p e r, p} (a_{j})$ , there is a perturbation of size $2 ϵ$ or less that will either drive their expected utility to $E U_{u p p e r, p} (a_{j}) + δ^{'}$ or below, or drive their expected utility to the minimum possible.

If $a_{j^{'}}$ has a probability less than $ϵ$ (as all the $a_{j^{'}}$ that $δ$ -dominate $a_{j}$ do), by taking $ϵ$ utility mass from that action (to drive it to probability 0) and putting it on $a_{j}$ in a way that preserves expected value, that $a_{j^{'}}$ will be counted as having the lowest possible expected utility in the dominance calculation. If $a_{j^{'}}$ has a probability $\geq ϵ$ (and has an expected utility within $δ$ of $a_{j}$ ) Lemma 2 works to either drive the expected utility of $a_{j^{'}}$ below that of $a_{j}$ , or drive it to the minimum possible expected utility.

If the worst-case utility for all those actions is equal to or less than $E U_{p} (a_{j}) + δ^{'}$ , then there’s a point in $B_{a_{j}}$ that’s within $2 (m - 1) ϵ + \frac{δ}{3}$ distance of $p$ (apply the perturbations mentioned above to make all other actions lose), which violates one of the starting assumptions. Therefore, there must be some action $a_{j^{'}}$ that dominates $a_{j}$ by more than $δ^{'}$ at $p$ , using the worst-case utility, so it dominates $a_{j}$ by a fixed amount over the whole $L_{1}$ ball.

Now, we shouldn’t necessarily assume that, over the whole ball, accurate utilities for $a_{j^{'}}$ will be learned, because the ball may have regions where the probability of $a_{j^{'}}$ is arbitrarily close to 0. However, density-zero exploration lets the inductor learn a lower bound on the utility of $a_{j^{'}}$ , as we’ll see.

Assume that the $L_{1}$ -ball has infinitely many price points in it (for a contradiction) Then, we can again make a $P$ -generable convex set $C$ with infinitely many points in it, and because of infinite exploration on divergent $P$ -generable subsequences (this is a slight strengthening of Scott’s density-zero exploration), the action $a_{j^{'}}$ will be taken infinitely often, and in finite time, the inductor will learn that $E_{t} (U_{t} | a_{t} = j)$ will be close to, or greater than, the worst-case utility for $a_{j^{'}}$ when the prices are in the set $C$ .

Again, we get the logical inductor learning to never take action $a_{j}$ , which produces a contradiction with the calibration property in the same way as before, because in this region, the price of $a_{j}$ is bounded away from 0.

Therefore, in case 2, there are still only finitely many points in the ball around $p$ , and the theorem has been proved.

#Lemma 6:

One of the following two properties applies to all convex $P$ -generable sets of prices over joint outcomes:

1: $C \in B_{a_{j}}$

2: ${lim}_{t \to \infty} \frac{1}{t} \sum_{k \leq t} α_{C} (k) \cdot i n d (a_{j}, k) = 0$

(I suspect it’s possible to strengthen condition 2 a little bit, but this more than suffices for the upcoming proof in the next post. Also, $i n d (a_{j}, k)$ is the function that is 0 when $a_{j}$ is not taken on turn $k$ , and 1 otherwise.)

Assume 1 is false. If it’s true, the proof is over. Also, assume there are infinitely many points in the interior of $C$ , because otherwise 2 is true and the proof is over. The space of prices is composed entirely of the following three disjoint sets of points. Set $Γ$ is composed of points where $α_{C} (p) < ϵ$ . in sets $Δ$ and $Θ$ , this doesn’t hold (and by Lemma 4, there must always be some action $a_{j^{'}}$ that dominates $a_{j}$ by $δ$ or more).

Set $Δ \cup Θ$ is convex, because $C$ is. Set $Δ$ is the (convex) set of points where $a_{j} < \frac{ϵ}{L}$ , and set $Θ$ is the (convex) set of points where $a_{j} \geq \frac{ϵ}{L}$ .

Set $Θ$ can have Lemma 5 applied to it to conclude that the sequence of prices will only be within it finitely often. Just identify $\frac{ϵ}{L}$ with $2 (m - 1) ϵ + \frac{δ}{3}$ in Lemma 5 to get the bounding away from $B_{a_{j}}$ , because that’s the minimum distance to travel to get outside of $s u p p (C)$ , and identify $δ$ or something sufficiently smaller with the $δ$ in Lemma 5 to get the domination condition.

We can split up $lim t \to \infty \frac{1}{t} \sum k \leq t α_{C} (k) \cdot i n d (a_{j}, k)$ into three sequences (with some overlap, but it won’t matter, because it produces an overestimate)

In the first sequence, the prices for the day are in set $Γ$ . In the second (fuzzy) sequence,the expected utility of $a_{j}$ is less than $\frac{ϵ}{L}$ (plus a little bit, so an expressible feature can capture this), and in particular, this fuzzy sequence is $P$ -generable. In the third sequence, the prices for the day are in set $Θ$ . All days are in one of these three sequences.

Over the first sequence, the time-averaged sum must limit to $ϵ$ or less, because $α_{C} (k) < ϵ$ , always.

Over the second (fuzzy) sequence, the long-term frequency of $a_{j}$ being taken must limit to $\frac{ϵ}{L}$ or less, by calibration, so the time-averaged sum must limit to $\frac{ϵ}{L}$ or less.

Over the third sequence, because it has finitely many points in it, the time-averaged sum limits to 0.

Therefore, the time-averaged sum must limit to $ϵ (1 + \frac{1}{L})$ or less. Because $L$ is a fixed constant, and $ϵ$ can be as small as we want, the time-averaged sum must converge to 0.