Preemptive Learning

If , then $liminf n \to \infty P_{n} (A_{n}) = liminf n \to \infty sup m \geq n P_{m} (A_{n})$ and $limsup n \to \infty P_{n} (A_{n}) = limsup n \to \infty inf m \geq n P_{m} (A_{n})$

BCS(P)??

It's the set of all sequences of $R$ -combinations (bundles of cash and shares), that are $¯ ¯ ¯ P$ -generable (There's a sequence of $E F$ -combinations that can be written down in poly-time that will turn into the $R$ -combinations given market data), and bounded (there's some $b$ such that the L1 norm, the sum of the absolute value of the coefficients, is $\leq b$ for all elements of the sequence.)

These sound like weird conditions to impose, but $R$ -combinations can be used to encode constraints between sentences like "3 of these 7 sentences are true" and "A xor B" by having the $R$ -combination for that group of sentences have a value of 3, and 1, respectively.

The $¯ ¯ ¯ P$ -generable condition is important to impose so the trader is actually able to write down the combination in the first place to buy and sell it.

The "boundedness" part is mainly useful to scale down an unruly sequence so the magnitude of each combination is 1 or less, to make it feasible to analyze.

Because of these essential properties, $B C S (¯ ¯ ¯ P)$ could be thought of as the set of $R$ -combination-sequences it's actually possible to prove stuff about and that the logical inductor can feasibly analyze. It will be showing up in most future theorems, as our set of "sufficiently nice" bundles of cash and shares.

Basic Intuition

Imagine a giant grid, with the index of the $R$ -combinations on the $x$ -axis, and the day on the $y$ -axis. Imagine it as a landscape where the elevation at a spot is the value of the combination on a particular day.

We'll be walking along the diagonal, in this particular case. Imagine there's a series of signs along that diagonal, that list the greatest and least elevation/value you'd ever reach if you just walked north forever. (this corresponds to ${sup}_{m \geq n} P_{m} (A_{n})$ and $inf$ , respectively) What this theorem says is that if you walk along the diagonal, the asymptotic lower bound on the elevation/value is the same as the asymptotic lower bound of the "greatest elevation to the north/greatest future value" advertised on the series of signs. Similarly, the asymptotic upper bound on the elevation/value is the same as the asyptotic upper bound of the "lowest elevation to the north/lowest future value"

Put another way, the "asymptotic lower bound of greatest future value" and "asymptotic upper bound of lowest future value" eventually get projected back into bounds on the value of the combinations along the diagonal. This links the far-distant values of combinations back to their "immediate" values along the diagonal, if we wait long enough.

Proof Formulation

Well, since we've already proved the Ε-ROI Lemma, we can assume that preemptive-learning property is false, and then show that it lets us fulfill the four $ε$ -ROI lemma prerequisites that'll result in a contradiction with the assumption that we have a logical inductor.

As a recap, they are as follows:

$ε$ -ROI on all "employees"

The sequence of "employees" is efficiently emulatable so they can be combined into a "trading firm"

There is a $¯ ¯ ¯ P$ -generable sequence $¯ ¯¯ ¯ α$ that describes the magnitude of the sequence of "employees"

$lim k \to \infty α_{k} \neq 0$ .

What would happen if the preemptive learning property, $liminf n \to \infty P_{n} (A_{n}) = liminf n \to \infty sup m \geq n P_{m} (A_{n})$ was false?

Well, straightaway, ${sup}_{m \geq n} P_{m} (A_{n}) \geq P_{n} (A_{n})$ . So if it's going to fail at all, it must be because $liminf n \to \infty P_{n} (A_{n}) < liminf n \to \infty sup m \geq n P_{m} (A_{n})$ .

This means that there's a gap, so there's some $b$ and some $ε > 0$ where $liminf n \to \infty P_{n} (A_{n}) < b - ε < b + ε < liminf n \to \infty sup m \geq n P_{m} (A_{n})$ .

This suggests the buy low, sell high strategy for the employees. Buy an $R$ -combination when its starting price along the diagonal is $b - ε$ or less, and resell it when its price inevitably goes above $b + ε$ , and pick up a little bit of guaranteed cash for $ε$ -ROI.

There's problems with this, of course. You can't have a sharp cutoff-function for buying and selling, you have to use the continuous indicator functions. Also, the price will only "inevitably" go above $b + ε$ in the limit. Let's analyze it a bit more, until a path reveals itself.

So, for infinitely many $n$ , $P_{n} (A_{n}) < b - ε$ by the definition of lim inf.

And there's some far-distant day $s_{e}$ where $\forall n > s_{e} : {sup}_{m \geq n} P_{n} (A_{n}) > b + ε$ .

Wait, what?

Lets say it was false, then. Then $\forall s_{e} \exists n > s_{e} : {sup}_{m \geq n} P_{n} (A_{n}) \leq b + ε$ . Or, put another way, there would be infinitely many $n$ where the greatest future value is $b + ε$ or less. Oh wait, by the definition of lim inf, lim inf(greatest future value) would be $b + ε$ or less. But it's greater than $b + ε$ , and thus, a contradiction.

Notice, the previous statement means that, along the diagonal, you'll eventually get to the point where the highest future value on all combinations further along the diagonal is over $b + ε$ . It does not mean that all combinations in the entire sequence will eventually go over $b + ε$ .

If we imagine our trading firm going along the diagonal and leaving one "employee" behind for each combination, which'll continue north forever, checking the value of the same combination... That means that our "trading firm" could just leave employees that'll do nothing, until day/combination $s_{e}$ , and then it'd start getting serious and outputting employees that buy low (if their combination is underpriced on the diagonal), wait for it to inevitably become overpriced, and sell their entire combination back then, because after day/combination $s_{e}$ , every combination is going to go above $b + ε$ value, eventually.

Also, instead of buying and selling precisely at $b - ε$ and $b + ε$ , we could have our indicator functions start buying and selling a bit closer to the middle, with those bounds just denoting when to go all-in (all-in corresponds to buying/selling 1 $R$ -combination/whatever's left). Then since the value on a combination is guaranteed to go above $b + ε$ eventually, each employee past day $s_{e}$ is going to end up unloading everything it bought on its first day (note: not the actual first day), and get $ε$ guaranteed cash.

Also, since the $R$ -combinations are bounded, that means its possible to scale them all down so they have a magnitude of 1 or less and preserve the theorem. That takes care of the first condition, the $ε$ -ROI one, since $ε$ guaranteed cash on a trade magnitude of 1 or less is an $ε$ fraction of the total trade magnitude.

The second condition about being able to emulate the employees also looks fairly simple if we can define a "percent of original purchase left" feature, since a "sell the easily-definable thing if the price goes too low" trigger is pretty easy to implement.

The third condition about being able to emulate the magnitude of the employees using market data can be fulfilled without too much trouble, too. Since all the employees will end up selling back everything they bought by the argument for point 1, the magnitude is twice as big as the magnitude of the original trade. Just sum up whatever expressible features were used to make the original trade and bam, you've got an expressible feature that'll produce the magnitude of the employee when exposed to market data. (the expressible features of the first trade can be written down in $p o l y (k)$ time, remember)

The fourth condition is trivially taken care of by that "infinitely often" clause about how often the value of the combinations dips below $b - ε$ on the diagonal.

Full Proof

Alright, first, we'll define our series of traders. If the trader's index is $< s_{e}$ , it'll just output 0 forever. Otherwise, there are three phases. For $n < k$ , the k'th employee outputs the 0 trade. For $n = k$ , we want to buy an $R$ -combination if it's underpriced, and for $n > k$ , we want to sell the remaining amount of the combination back if it's overpriced. Let's define the initial trade, the trade made by the k'th trader on the k'th day. $T_{k}^{k} := I n d_{ε / 2} (A_{k}^{† * k} < b - ε / 2) \cdot (A_{k}^{†} - A_{k}^{† * k})$ This is basically just saying "start buying the $R$ -combination $A_{k}$ at $b - ε / 2$ , and go all the way up to buying one of the combination at $b - ε$ ". And also the $R$ -combination is going to have a price of 1 or less because we scaled it down, and we could do that because it was in $B C S (¯ ¯ ¯ P)$ , so we could divide it by the upper bound.

Now, for the later parts. We'll need a "fraction of original purchase to sell off" expressible feature. $F_{n} := I n d_{ε / 2} (A_{k}^{† * n} > b + ε / 2) (1 - \sum k < i < n F_{i})$ The first part of it is the indicator to start buying at $b + ε / 2$ and go all-in at $b + ε$ , and the second part is the percent of original purchase left over (1-all the previous sellings)

Finally, for $n > k$ , we'll need to use that expressible feature to determine how much to sell off. So the trade would be $T_{n}^{k} := - F_{n} \cdot T_{k}^{k}$ Just use the "fraction to sell off" feature to scale down the original purchase, and sell it off.

Ok, so we need to establish $ε$ -ROI, that what we just defined is an efficiently emulatable sequence of traders, that the magnitudes of the traders is $¯ ¯ ¯ P$ -generable, and the sequence of trader magnitudes doesn't go to zero.

Let's start with the second. The k'th "employee" makes no trades before day k.

The algorithm for the k'th employee can be written down in poly(k) time, because the $E F$ -combination $A_{k}^{d a g g e r}$ is computable in $p o l y (k)$ time, by the definition of $B C S (¯ ¯ ¯ P)$ (remember, being $¯ ¯ ¯ P$ -generable was one of the conditions, and that implies that it takes $p o l y (k)$ time to write down $A_{k}^{†}$ ). And the recursive definition for "fraction of purchase left" is the same for each trader. And the test to see whether the trader's index is $< s_{e}$ also takes fairly little time.

And each individual employee has to be able to write down its trade in poly(n) time. By caching past trades, it would only take $p o l y (n)$ time to compute the "fraction of original purchase left" feature is, and the $R$ -combination is just the same every time and doesn't change.

Thus, since the k'th employee makes no trades before day $k$ , the k'th employee can be written down in $p o l y (k)$ time, and they all run in $p o l y (n)$ time, it's an efficiently emulatable sequence of traders.

Next up: Showing that all the original purchase will be sold off eventually.

By induction on $F_{n}$ , we can find that $\sum_{k < i \leq n} F_{i} \leq 1$ and $F_{n} \geq 0$ . Remember, by our original assumption, there's some day $m$ where $P_{m} (A_{k}) > b + ε$ . On that day, the indicator function will be 1, so

(will return later)

LESSWRONG
LW

LESSWRONG
LW

Preemptive Learning

Basic Intuition

Proof Formulation