Bounded Oracle Induction

post by Diffractor · 2018-11-28T08:11:28.183Z · LW · GW · 0 comments

Contents

  Introduction:
  Notation:
  The OI Algorithm:  
  Interpretation of a Trade:
  Facts About OI: 
  Future Directions:
  APPENDIX: Auxiliary Algorithms
None
No comments

Introduction:

Because logical induction relies on the Brouwer fixed-point theorem, and reflective oracles rely on the Kakutani fixed-point theorem which Brouwer is a special case of, it's possible that logical induction could have been derived for the first time from reflective oracles. Attempting to do this in the most obvious way by having traders output a circuit that takes a binary-search approximation of the market as input doesn't produce any insights in particular. However, by attempting to redevelop the logical induction algorithm from scratch with the aid of a bounded reflective oracle, we arrive at a new way of looking at logical induction, with the following interesting features.

1: It collapses the distinction between the algorithm outputting the trading circuit, and the trading circuit itself.

2: All trades can be naturally interpreted as probability measures over bitstrings, with the reward given by a simple betting game, instead of shares that pay off if some boolean combination is true. However, the betting game doesn't incentivize true belief reporting, just moving the probability distribution of the market in the right direction. This turns out to be isomorphic to the original formulation of the value of a trade, subject to one extra restriction on worst-case trade value.

3: The market prices are also a probability measure over bitstrings/worlds, exactly like a universal inductor.

4: It does the reflective-solomonoff thing of "draw a turing machine with probability $2^{-\text{K-complexity}}$, use it to predict future bits"

First, notation will be established, and the algorithm will be discussed. Then the connection between OI-trader scoring and LI-trader scoring will be established, and questions of how many of the nice properties of LI carry over will be discussed. We will finish with basic discussion of what this result means, and then there will be an appendix which contains the definitions of auxiliary algorithms, and the next post [AF · GW] will contain the proof that the algorithm is an Oracle Inductor.

As a quick refresher, a bounded reflective oracle takes as input a query of the form $(A,p)$, and returns $1$ if $A$ has bounded runtime, and only makes oracle calls to algorithms with the same runtime bound, and outputs $1$ with probability greater than $p$, and $0$ if $A$ has bounded runtime and only makes oracle calls to algorithms with the same runtime bound, and outputs $1$ with probability less than $p$. If the probability of a $1$ is exactly $p$, or if $A$ exceeds runtime bounds, the oracle is allowed to randomize arbitrarily.

Notation:

$\{0,1{\}}^L$ and $\{0,1{\}}^{\ast }$ are the sets of all bitstrings of length $L$, and the set of all finite bitstrings, respectively. Elements of these sets are denoted by $x$. $\lambda$ refers to the empty string.

$B_L$ is the set of all satisfiable booleans with all variables having an index $\le L$, and $B^{}$ is the set of all satisfiable booleans. $B_{\ast }$ is the set of all booleans (including unsatisfiable ones), and $B_{\ast L}$ is the set of all booleans with all variables having an index $\le L$. Elements of these sets are denoted by $B$. $B_{\top }$ is the trivial boolean which is satisfied by all bitstrings. Note that a boolean $B\in B_L$ induces a function $\{0,1{\}}^L\to \{0,1{\}}^{}$ .

$f$ is a function $N^{+}\to N^{+}$ that is time-constructible, monotonically increasing, and $f\left(t\right)>t$. It will give the runtime bound for the traders.

$l$ is some function $N^{+}\to N^{+}$ upper-bounded by $2^{f\left(t\right)}$, that is time-constructible, monotonically increasing, and $l\left(t\right)>t$. It gives the most distant bit the oracle inductor thinks about on turn $t$.

$d$ is the function $N^{+}\to N^{+}$ given by $d\left(t\right)=l\left(t\right)+\lceil {\log }_{2}l\left(t\right)\rceil +2t+7$ , giving the number of iterations of binary-search deployed on turn $t$.

$\delta$ is the function $N^{+}\to [0,1]\cup Q$ given by $\delta \left(t\right)=2^{-(t+3)}$. It gives the proportion of the inductor distribution that is made up by the uniform distribution, to ensure that all bitstrings have a probability high enough for binary-search to accurately approximate their probability.

$\text{query}(A,p)$ consults the bounded reflective oracle about whether $A$ returns $1$ with probability greater than $p$.

$\text{flip}\left(p\right)$ rounds $p$ down to $1$ if it is greater than $1$, and then flips a coin that returns $1$ with probability $p$. In our model of computation, this operation takes unit time.

The OI Algorithm:

$\overline{\underset{–}{\text{Algorithm 1:}\text{OI(t),}{N}^{+}\to \Delta \{0,1{\}}^{\text{l(t)}}}}\text{IF}\text{flip(}\delta \text{(t))}=1\text{return}\text{Unif(l(t))}\text{ELSE}a\leftarrow \text{Unif(f(t))}b\leftarrow 1\text{FOR}i\text{from}1\text{to f(t)}\text{IF}\text{flip}\left(\frac{1}{2}\right)=0\text{break}\text{ELSE}b\leftarrow b+1\text{return}\text{Approx(OI(t),l(t),d(t),BTtoBool(a,t,b))}$

In short, the distribution induced by the oracle induction algorithm has a small portion of the probability mass composed of the uniform distribution, and otherwise the algorithm selects a turing machine according to the universal distribution, and a "budget", with $2^{-b}$ of the probability mass on a budget of $b$, much like the logical inductor algorithm. In this setting, all trades can be interpreted as a mixture of probability distributions of the form "condition the oracle induction distribution on some boolean being true", so the budgeted trader is consulted to get a boolean (note that the trader may be randomized!), and $\text{Approx}$ is used to approximately replicate the probability distribution produced by conditioning the oracle induction distribution on the resulting boolean.

$\overline{\underset{–}{\text{Algorithm 2:}\text{Approx(}\Delta \text{,L,D,B),}\Delta \{0,1{\}}^L\times (N^{+}{)}^2\times B_L\to \Delta \{0,1{\}}^L}}x\leftarrow \lambda \text{FOR}i\text{from}1\text{to}Lx\leftarrow x+\text{NextBit(}\Delta \text{,D,}i\text{,B,}x\text{)}\text{return}x$

This starts with the empty bitstring and repeatedly concantates it with $\text{NextBit}$ which gets the next bit, until a bitstring of length $L$ is produced. $\Delta$, $D$ and $B$ are just passed on to $\text{NextBit}$.

$\overline{\underset{–}{\text{Algorithm 3:}\text{NextBit(}\Delta \text{,D,i,B,x),}\Delta \{0,1{\}}^L\times (N^{+}{)}^2\times B_L\times \{0,1{\}}^{i-1}\to \Delta \{0,1{\}}^{}}}{B}^{\prime }\leftarrow \text{ToPref(x)}\wedge \text{B}{B}_0^{\prime }\leftarrow B^{\prime }\wedge \neg x_i{B}_1^{\prime }\leftarrow B^{\prime }\wedge x_i\text{IF}\text{SAT}\left(B_0^{\prime }\right)=0\text{return}1\text{ELSE IF}\text{SAT}\left(B_1^{\prime }\right)=0\text{return}0\text{ELSE}\text{return}\text{flip}\left(\frac{\text{BinSearch(}1,\text{eval}(B_1^{\prime },\Delta )\text{,D)}}{\text{BinSearch(}1,\text{eval}(B^{\prime },\Delta )\text{,D)}}\right)$

This defines a boolean constraint that says that $B$ must be true, and the initial prefix of the bitstring must equal $x$. Then two more boolean constraints are generated, which are the same except they specify that the next bit is a $0$ or $1$. If only one of the two is a satisfiable boolean, the next bit is forced to be $0$ or $1$ in compliance with the satisfiability requirement, otherwise, binary search for $D$ iterations on the probability of $\Delta$ outputting a bitstring that satisfies $B^{\prime }$ or $B_1^{\prime }$ is used to figure out the probability of the next bit being a $1$.

$\overline{\underset{–}{\text{Algorithm 4:}\text{BinSearch(n,}\Delta \text{,D),}\{0,1,2\}\times \Delta \{0,1{\}}^{}\times N^{+}\to [0,1]\cup Q}}hi\leftarrow 1lo\leftarrow 0\text{FOR}i\text{from}1\text{to D}\text{IF}\text{query}(\Delta ,\frac{hi+lo}{2})=1lo\leftarrow \frac{hi+lo}{2}\text{ELSE}hi\leftarrow \frac{hi+lo}{2}\text{IF}\text{n}=0\text{return}lo\text{ELSE IF}\text{n}=1\text{return}\frac{hi+lo}{2}\text{ELSE}\text{return}hi$

This uses the oracle to implement binary-search for $D$ rounds on some algorithm, and output either a lower-bound, average, or upper-bound estimate of the probability of the algorithm outputting $1$.

$\overline{\underset{–}{\text{Algorithm 5:}\text{BTtoBool(a,t,b),}\{0,1{\}}^{f\left(t\right)}\times (N^{+}{)}^2\to B_{l\left(t\right)}}}\text{IF}\text{query(OverBudget(a,t,b),}\frac{2^{-\text{l(t}-1)}}{2(\text{t}-1)}\text{)}=1\text{return}{B}_{\top }\text{ELSE}\text{return}\text{TradeToBool(a,t)}$

This uses the oracle to test whether the trader is possibly over-budget, and if so, returns the null boolean, otherwise, it returns the boolean that the trader returns. $\text{OverBudget}$ randomly selects a day and a world/bitstring, and returns $1$ if the world/bitstring hasn't been ruled out by that day and the trader is over-budget relative to that world/bitstring, so the oracle call is testing whether there's any combination of worlds and days where the trader is over-budget.

$\overline{\underset{–}{\text{Algorithm 6:}\text{OverBudget(a,t,b),}\{0,1{\}}^{\ast }\times (N^{+}{)}^2\to \Delta \{0,1{\}}^{}}}n\leftarrow \text{rand(}1,\text{t}-1\text{)}B\leftarrow \text{ToPref(Unif(l}\left(n\right)\text{))}\text{IF}\text{SAT(DP(}n)\wedge B)=0\text{return}0\text{ELSE IF}-n+{\sum }_{1\le i\le n}\frac{\text{BinSearch(}0,\text{eval(clip(}B,\text{l(i)),Approx(OI(i),l(i),d(t),TradeToBool(a,i))),d(t))}}{\text{BinSearch(}2,\text{eval(clip(}B,\text{l(i)),OI(i)),d(t))}}<-b+1\text{return}1\text{ELSE}\text{return}0$

This randomly picks a day and bitstring, and returns $1$ if the bitstring is plausible (hasn't been ruled out by the deductive process) on that day, and the trader might be over-budget. Note that the strength of the approximation rises as a function of $t$. This means that at later days, more accurate retroactive estimates are used for the value of a trade on previous days. The mess of parentheses in the numerator essentially clips the bitstring to the appropriate length, and uses binary search to find the probability that (an approximation of (the distribution produced by conditioning the OI distribution on (the boolean outputted by the trader))) assigns to the bitstring.

$\overline{\underset{–}{\text{Algorithm 7:}\text{TradeToBool(a,i),}\{0,1{\}}^{\ast }\times N^{+}\to \Delta B_{l\left(i\right)}}}\text{run (a,i) on a UTM}\text{IF}\text{UTM(a,i) doesn't halt in f(i) steps, or an oracle call to an algorithm}\text{other than eval(B,OI(i')) for i'}\le \text{i, B}\in B_{\ast l\left(i\right)}\text{, is made,}\text{return}{B}_{\top }\text{ELSE}B\leftarrow \text{clip(ToBool(UTM(a,i)),l(i))}\text{IF}\text{SAT(}B)=0\text{return}{B}_{\top }\text{ELSE}\text{return}B$

This takes a trader, and returns the null constraint if it times out or makes an "out of bounds" oracle call or outputs an unsatisfiable boolean. Otherwise, it takes the bitstring the trader outputs, interprets it as some boolean constraint, clips the constraint to the appropriate length, and outputs that constraint. Note that because algorithms can be randomized, this won't necessarily output the same boolean every time, so the distribution produced by $\text{Approx(}\Delta \text{,L,D,TradeToBool(a,i))}$ should actually be thought of as a probabilistic mixture of conditional distributions.

To put all this together, the inductor selects a turing machine and a budget with the appropriate probability, and queries the turing machine about what boolean combination it thinks the true sequence of bits fulfills. As the turing machine can only report one boolean combination, mixtures of various booleans are implemented by the turing machine randomizing. If the past history of the turing machine has it possibly going over-budget on the next "trade", or violates conditions by running over time, or making illegal oracle calls, or providing an impossible-to-fulfill boolean, then the market just defaults to asking (an approximation of) itself about its own probabilities. Otherwise, the market outputs (an approximation of) its own probability distribution, conditioned on being in conformance with the trader. A bounded reflective oracle is exploited as an NP-oracle, and to effectively narrow down the probability of itself outputting a specific bitstring.

Interpretation of a Trade:

The interpretation of a trade from the logical induction paper was that you'd lose $P\left(x_i\right)$ dollars in order to acquire a share that would be worth $1$ dollar in worlds $x$ where $x_i=1$,and $0$ dollars if $x_i=0$.

The interpretation of a trade in this setting is that a trader and a market spread $1$ dollar amongst various bitstrings/worlds $x$,(which will be lost), giving a probability measure, and if the world is revealed to be $x$, the trader earns $\frac{T\left(x\right)}{P\left(x\right)}$ dollars in return. (where $T\left(x\right)$ is the probability the trader assigned to $x$, and $P\left(x\right)$ is the probability the market assigned to $x$). The value of a trader at time $t$ in world $x$ is then $-t+{\sum }_{1\le i\le t}\frac{T_i\left(x\right)}{P_i\left(x\right)}$ .

Surprisingly enough, these two interpretations are actually equivalent! We can take (some) LI trades, and convert them into an OI trade with the same value in all worlds, and also do the reverse.

First, let's say our OI trader spreads its dollar according to $P|B$ (it copies the market probability distribution, conditional on the world fulfilling the constraint $B$). Then, in all worlds $x$ that don't fulfill the boolean, it will lose $1$ dollar because it assigned $0$ measure to $x$, and in all $x$ that fulfill the boolean, because $T\left(x\right)=\frac{P\left(x\right)}{P\left(B\right)}$, it gets $-1+\frac{1}{P\left(B\right)}$ dollars in return. If we multiply these two values by $P\left(B\right)$, we get $-P\left(B\right)$ dollars when it fails, and $1-P\left(B\right)$ dollars when it succeeds, which is the exact same as a logical-induction trader buying one share in $B$. So, the value of the OI trader outputting the distribution $P|B$ has the exact same value in all worlds as buying $\frac{1}{P\left(B\right)}$ shares of $B$, which is the same as spending $1$ dollar buying shares of $B$.

We interpret a randomized choice of a boolean as the trader $T$ spending $\text{P}(T=B)$ ($\text{P}$ is an ordinary probability, not the market price of anything)of the probability mass on the conditional distribution $P|B$. This sums up to produce a probability measure, where $T\left(x\right)={\sum }_{B\in B^{}}\text{P}(T=B)\cdot \left(P|B\right)\left(x\right)$.

Generalizing a bit, all OI trades are equivalent to a LI trade where it spends $T\left(x\right)$ dollars buying shares of the boolean corresponding to $x$, and spends $1$ dollar in total.

Also, if the trader outputs the null boolean, $T\left(x\right)=P\left(x\right)$, so the value of that trade in all worlds is 0 and equivalent to not buying or selling anything. This can be used to have the equivalent LI trade spend less than $1$ dollar buying shares, if some portion of $T$ is composed of $P$ .

Going in the reverse direction, from a LI trade to a OI trade, is more difficult, because there is both buying and selling of shares. From before, buying $1$ share of $B$ is equivalent to the OI trader distributing $P\left(B\right)$ of its probability mass according to the $P|B$ distribution. It's slightly more involved to show, but selling $1$ share of $B$ has equivalent value in all worlds as distributing $P\left(\neg B\right)$ of the OI trader mass on the $P|\neg B$ distribution.

Now, if, at the end of translating the LI trade into OI terms, less than all of the probability mass has been spent on various conditional distributions, the rest of the probability mass can be spent on copying $P$ since it has $0$ value in all worlds. But what if the measure of the resulting trade sums to greater than $1$? In that case, the extreme-worst-case value of the LI trade (all purchased shares were worth $0$, all sold shares were worth $1$)is below $-1$.

Therefore, if there's a LI trader with a circuit that's evaluatable in polynomial time (not just writable in poly-time), and it never makes a trade with extreme worst-case value below $-1$ (ie, it doesn't blow too much money at any given time), there's a corresponding OI trader! This includes almost all the traders from the proofs of the logical induction paper. However, the traders from 4.7.2 (conditionals on theories) and 4.5.10 (affine unbiasedness from feedback) need to be adapted.

Conjecture 1: There is an LI trader with extreme-worst-case value on each turn of $-1$ that exploits the market if it violates Affine Unbiasedness from Feedback, and another such trader that exploits the market if the market conditional on $\psi$ is exploitable by a trader with extreme-worst-case value on each turn of $-1$.

If this conjecture holds, oracle induction would inherit all the nice properties of logical induction.

Exploitation is defined in the standard way, as the set of plausible values according to worlds consistent with the deductive process at time $t$ , over all $t$, being bounded below and unbounded above.

Note that if we consider the market as composed of all the traders probability-distributions aggregated together, the payoff to everybody corresponds to taking everyone's money, and distributing that money back to everyone according to the fraction of the probability-mass in the winning world $x$ that was contributed from their distribution.

Also note that because the OI-traders can implement very long and complex combinations of distributions by randomizing, OI-traders are able to make some trades that LI-traders can't, because they can output trades that are too long and complicated for the LI-trader to write down in polynomial time. An OI-trader, converted to an LI-trade, may even have purchases in every single boolean, which LI-traders definitely can't replicate.

Conjecture 2: There is an LI trader that runs in poly-time, and an Oracle Inductor that is inexploitable by poly-time adversaries, such that the trader exploits the Oracle Inductor, and there is an OI trader that runs in poly-time and a Logical Inductor that is inexploitable by poly-time adversaries, such that the trader exploits the Logical Inductor.

Facts About OI:

Just like logical inductors, there is no trader that runs in time less than $f\left(t\right)$ that exploits the market. This is shown by the following theorems which are analogous to the theorems establishing that the logical induction algorithm is inexploitable.

Theorem 1: If a trader that can be simulated on a UTM in less than $f\left(t\right)$ time exploits $\text{OI}$, there is some finite budget $b$ such that the budgeted trader exploits $\text{OI}$.

Theorem 2: If a budgeted trader exploits $\text{OI}$, the supertrader exploits $\text{OI}$.

Theorem 3: The supertrader doesn't exploit $\text{OI}$.

The proofs will be deferred to the next post.

As for the strength of the bounded reflective oracle needed to guarantee that all oracle calls are well-defined, it is $O\left(l\right(t{)}^3+t^{3}l(t{)}^2+l(t\left)f\right(t)+f(t\left)\log f\right(t\left)\right)$ . Again, the proof will be deferred to the next post.

Future Directions:

The two conjectures would be interesting to settle, although only the first is truly critical to showing that this is as powerful as a logical inductor.

The interpretation of trades as probability measures over bitstrings, with payoff given by the proportion of probability mass in the winning string contributed by a trader is useful, although the lack of an incentive for accurate belief reporting is slightly worrying, and prevents us from truly attributing beliefs to individual traders.

The close parallel between this and Reflective-Oracle Solomonoff Induction may prove to be fruitful, and potentially lead to a variant of AIXI in this setting, which may be ported back to logical induction.

APPENDIX: Auxiliary Algorithms

$\overline{\underset{–}{\text{flip(p),}{Q}^{\ge 0}\to \Delta \{0,1{\}}^{}}}p\leftarrow \text{min(}1,p)\text{return}\text{output of a coin which returns 1 with probability p}$

In our model of computation, assume that this takes unit time.

$\overline{\underset{–}{\text{Unif(n),}N\to \Delta \{0,1{\}}^n}}x\leftarrow \lambda \text{FOR}i\text{from}1\text{to n}x\leftarrow x+\text{flip}\left(\frac{1}{2}\right)\text{return}x$

This generates a random bitstring of length $n$.

$\overline{\underset{–}{\text{rand(m,n),}(N^{+}{)}^2\to \Delta N^{+}}}\text{FOR}i\text{from m to n}\text{IF}\text{flip(}\frac{1}{\text{n}-i+1})=1\text{return}i\text{break}$

This randomly selects an integer in $[m,n]$, with equal probability for each integer.

$\overline{\underset{–}{\text{clip(B,n),}{B}_{\ast }\times N^{+}\to B_{\ast }}}B\leftarrow \text{B with all variables with an index >n removed}\text{return}B$

This is used to ensure that the traders output boolean constraints that aren't about unreasonably distant digits.

$\overline{\underset{–}{\text{eval(B,x),}{B}_{\ast }\times \{0,1{\}}^{\ast }\to \Delta \{0,1{\}}^{}}}n\leftarrow \text{max index of a variable in B}x\leftarrow \text{x+Unif(max(0,}n\text{-|x|))}\text{return}\text{B(}x)$

This applies a boolean circuit to a bitstring, and pads it with randomly selected bits if the bitstring is too short. Note that since traders are allowed to call the oracle on this function applied to the oracle inductor, this implicitly assigns 50% probability to all bits that are too distant for the oracle inductor to have thought about them yet.

$\overline{\underset{–}{\text{ToPref(x),}\{0,1{\}}^{\ast }\to B^{}}}B\leftarrow {\bigwedge }_{1\le i\le \text{|x|}}{y}_i={\text{x}}_i\text{return}B$

This converts a bitstring to a boolean which requires that the prefix of a bitstring equals $\text{x}$. The equality should be understood as $\neg y_i$ if ${\text{x}}_i=0$, and $y_i$ if ${\text{x}}_i=1$.

$\overline{\underset{–}{\text{SAT(B),}{B}_{\ast }\to \{0,1{\}}^{}}}n\leftarrow \text{max index of a variable in B}\text{return}\text{query(eval(B,}\lambda ),2^{-(n+1)})$

This uses the oracle as a SAT-solver, by using $\text{eval(B,}\lambda )$ to randomly generate a bitstring of length $n$. If there is a bitstring which fulfills the boolean, there is a $2^{-n}$ probability of generating that bitstring, so the oracle can perfectly discriminate between satisfiable and unsatisfiable booleans.

$\overline{\underset{–}{\text{ToBool(x),}\{0,1{\}}^{\ast }\to B_{\ast }}}$

This just turns a bitstring into the boolean it encodes, given some efficient encoding scheme.

$\overline{\underset{–}{\text{DP(n),}{N}^{+}\to B_{l\left(n\right)}}}$

This is the deductive process, a blackbox deterministic algorithm which outputs booleans of index at most $l\left(n\right)$ in at most $max\left(l\right(n),f(n\left)\right)$ time s.t $\forall n\forall i<n:DP\left(n\right)\wedge DP\left(i\right)=DP\left(n\right)$ (ie, the constraints on the true environment get more stringent over time but always stay satisfiable).

0 comments

Comments sorted by top scores.