Contents

• Preliminaries
• Construction 1
• Proposition 1
• Notation
• Results
• Theorem 1
• Definition 1
• Corollary 1
• Definition 2
• Construction 2
• Corollary 2
• Theorem 2
• Corollary 3
• Construction 3
• Corollary 4
• Definition 3
• Theorem 3
• Theorem 4
• Appendix A
• Proposition A.1
• Proof of Proposition A.1
• Proof of Proposition 1
• Proposition A.2
• Proof of Proposition A.2
• Lemma A.1
• Appendix B
• Lemma B.1
• Lemma B.2
• Proof of Lemma B.2
• Proof of Theorem 1
• Proposition B.1
• Proof of Proposition B.1
• Proof of Corollary 1
• Proof of Corollary 2
• Proposition B.2
• Proof of Proposition B.2
• Proposition B.3
• Proof of Proposition B.3
• Proposition B.4
• Proof of Proposition B.4
• Proof of Theorem 2
• Proof of Corollary 3
• Proof of Corollary 4
• Proposition B.5
• Proof of Proposition B.5
• Proof of Theorem 3
• Proposition B.6
• Proof of Proposition B.6
• Proof of Theorem 4

We consider transparent games between bounded CDT agents ("transparent" meaning each player has a model of the other players). The agents compute the expected utility of each possible action by executing an optimal predictor of a causal counterfactual, i.e. an optimal predictor for a function that evaluates the other players and computes the utility for the selected action. Since the agents simultaneously attempt to predict each other, the optimal predictors form an optimal predictor system for the reflective system comprised by the causal counterfactuals of all agents. We show that for strict maximizers, the resulting outcome is a bounded analogue of an approximate Nash equilibrium, i.e. a strategy which is an optimal response within certain resource constraints up to an asymptotically small error. For "thermalizers" (agents that choose an action with probability proportional to 2^{\frac{u}{T}}), we get a similar result with expected utility \E_s[u] replaced by "free utility" \E_s[u]+T \H(s). Thus, such optimal predictor systems behave like bounded counterparts of reflective oracles.

Preliminaries

The proofs for this section are given in Appendix A.

We redefine \mathcal{E}{2(ll,\phi)} and \mathcal{E}{2(ll)} to be somewhat smaller proto-error spaces which nevertheless yield the same existence theorems as before. This is thanks to Lemma A.1.

Construction 1

Given \phi \in \Phi, denote \mathcal{E}_{2(ll,\phi)} the set of bounded functions \delta: \Nats^2 \rightarrow \Reals^{\geq 0} s.t.

\forall \psi \in \Phi: \psi \leq \phi \implies E_{\lambda_\psi^k}[\delta(k,j)] = O(\psi(k)^{-1})

Denote

\mathcal{E}{2(ll)} := \bigcap{\phi \in \Phi} \mathcal{E}_{2(ll,\phi)}

Proposition 1

If \phi \in \Phi is s.t. \exists n: \LimInf{k} 2^{-k^n} \phi(k) = 0, O(\phi^{-1}) is a proto-error space.

For any \phi \in \Phi, \mathcal{E}{2(ll,\phi)} is an ample proto-error space. When \phi is non-decreasing, \mathcal{E}{2(ll,\phi)} is stable.

\mathcal{E}_{2(ll)} is a stable ample proto-error space.

Notation

We denote O(\phi^{-\frac{1}{\infty}}):=O(\phi^{-1})^{\frac{1}{\infty}}. We allow the same abuse of notation for this symbol as for usual big O notation.

For any (poly,rlog)-bischeme \hat{Q}=(Q,r_Q,\sigma_Q) we use \hat{\sigma}_Q^{kj} to denote U^{r_Q(k,j)} \times \sigma_Q^{kj}.

For reflective systems \mathcal{R}=(\Sigma,f,\mu) we write indices in \Sigma as superscripts rather than subscripts as before.

Given \pi \in \Pi_\Sigma, we denote U(\pi)^{nkj}:=U^{\pi_2^{nkj}} and \pi^{nkj}(x,y):=\beta(ev(\pi_1^{nkj};x,y)).

Results

The proofs for this section are given in Appendix B.

We start by showing that choosing an action by maximizing over optimally predicted utility is an optimal strategy in some sense.

Theorem 1

Fix a proto-error space \mathcal{E}. Consider \mathcal{A} a finite set, \mu a word ensemble and {f_a: \Supp \mu \rightarrow [0,1]}{a \in \mathcal{A}}. Suppose {\hat{P}a}{a \in \mathcal{A}} are \mathcal{E}(poly,rlog)-optimal predictors for f. Assume that \sigma{P_a} and r_{P_a} don’t depend on a (this doesn’t limit generality since we can replace \sigma_{P_a} by \prod_{b \in \mathcal{A}} \sigma_{P_b} and r_{P_a} by a polynomial r_P \geq \max_{b \in \mathcal{A}} r_{P_b}). Consider \hat{A} an \mathcal{A}-valued (poly,rlog)-bischeme. Define \hat{M} another \mathcal{A}-valued (poly,rlog)-bischeme where \hat{M}^{kj}(x) is computed by sampling y from \hat{\sigma}_P^{kj} and choosing arbitrarily from a \in \mathcal{A} s.t.\hat{P}_a^{kj}(x,y) is maximal. Then, there is \delta \in \mathcal{E}^{\frac{1}{2}} s.t.

\E_{\mu^k \times \hat{\sigma}M^{kj}}[f{\hat{M}^{kj}}] \geq \E_{\mu^k \times \hat{\sigma}A^{kj}}[f{\hat{A}^{kj}}] - \delta(k,j)

Definition 1

Given suitable sets X,Y and \phi \in \Phi, a \phi(poly,rlog)-scheme of signature X \rightarrow Y is \hat{A}=(A:\Nats \times X \times \Words^2 \rightarrow Y, r_A: \Nats \rightarrow \Nats, \sigma_A: \Nats \times \Words \rightarrow [0,1]) s.t.

(i) The runtime of A^k is bounded by p(t_\phi(k)) for some polynomial p.

(ii) |r_A(k)| \leq p'(t_\phi(k)) for some polynomial p'.

(iii) \sigma_A^k is a probability measure on \Words and there is c > 0 s.t. \Supp \sigma_A^k \subseteq \WordsUpToLen{c \Floor{log(k+2)^{\phi(k)}}}.

A \phi(poly,rlog)-scheme of signature \Words \rightarrow Y is also called a Y-valued \phi(poly,rlog)-scheme.

As usual, we sometimes use \hat{A}^{kj} as implicit notation in which A receives a value sampled from U^{r_A(k)} for the second argument and/​or a value sampled from \sigma_A^k for the third argument.

Corollary 1

Fix \phi \in \Phi. Consider \mathcal{A} a finite set, \mu a word ensemble and {f_a: \Supp \mu \rightarrow [0,1]}{a \in \mathcal{A}}. Suppose {\hat{P}a}{a \in \mathcal{A}} are \mathcal{E}{2(ll,\phi)}(poly,rlog)-optimal predictors for f. Consider \epsilon \in (0,1) and \hat{A} an \mathcal{A}-valued \phi^{1-\epsilon}(poly,rlog)-scheme. Define \hat{M} as in Theorem 1. Then

\E_{\mu^k \times \lambda_\phi^k}[\E_{\hat{\sigma}M^{kj}}[f{\hat{M}^{kj}}]] \geq \E_{\mu^k \times \hat{\sigma}A^{k}}[f{\hat{A}^{k}}] - O(\phi^{-\frac{1}{\infty}})

We now introduce the game theoretical setting.

Definition 2

A distributional game is a quadruple G=(\mu,\mathcal{P},\mathcal{A},u) where \mu is a word ensemble, \mathcal{P} is a finite set representing players, {\mathcal{A}^n}{n \in \mathcal{P}} are finite sets representing the possible actions of each player and {u^n: \Supp \mu \times \prod{n \in \mathcal{P}} \mathcal{A}^n \rightarrow [0,1]}_{n \in \mathcal{P}} represent the utility functions.

For each x \in \Supp \mu, G defines an ordinary game in normal form. We think of G as a single game where the strategies are (some class of) functions s: \Supp \mu \rightarrow \mathcal{A}^n and the payoffs are \E_\mu[u^n(\prod_{n \in \mathcal{P}} s^n(x))].

Construction 2

Consider G=(\mu,\mathcal{P},\mathcal{A},u) a distributional game and {\phi^n \in \Phi}_{n \in \mathcal{P}}. We construct the reflective system \mathcal{R}G^\phi=(\mathcal{P},u\phi,\mu_G).

\mu_G is defined by

\mu_G^{nk}(k,x,a)=\frac{\mu^k(x) \chi_{\mathcal{A}^n}(a)}{#\mathcal{A}^n}

Define M_G^n: \Nats^2 \times \Supp \mu \times \Words \times \Pi_{\mathcal{P}} \rightarrow \wp(\mathcal{A}^n) by

M_G^{nkj}(x,y,\pi):=\Argmax{a \in \mathcal{A}} \pi^{nkj}((k,x,a),y)

Denote \Delta_G^n to be the space of mixed actions of player n i.e. the space of probability measures on \mathcal{A}^n.

Define s_{G,\phi}^n: \Nats \times \Supp \mu \times \Pi_{\mathcal{P}} \rightarrow \Delta_G^n by

\Pr_{s_{G,\phi}^{nk}(x,\pi)}[a]:=\E_{\lambda_{\phi^n}^k}[\E_{U(\pi)^{nkj}}[\frac{\chi_{M_G^{nkj}(x,y,\pi)}}{#M_G^{nkj}(x,y,\pi)}]]

Define s_{G,\phi}: \Nats \times \Supp \mu \times \Pi_{\mathcal{P}} \rightarrow \prod_{n \in \mathcal{P}} \Delta_G^n by

s_{G,\phi}^k(x,\pi) := \prod_{n \in \mathcal{P}} s_{G,\phi}^{nk}(x,\pi)

Define s_{G,\phi}^{\bar{n}}: \Nats \times \Supp \mu \times \Pi_{\mathcal{P}} \rightarrow \prod_{m \in \mathcal{P} \setminus n} \Delta_G^m by

s_{G,\phi}^{\bar{n}k}(x,\hat{Q}):=\prod_{m \in \mathcal{P} \setminus n} s_{G,\phi}^{mk}(x,\hat{Q}^m)

Finally, define u_\phi by

u_\phi^{nk}(x,a,\pi):=\E_{a \times s_{G,\phi}^{\bar{n}k}(x,\pi)}[u^n]

For any (poly,rlog)-predictor \hat{Q} we will use the notation s_{G,\phi}^{nk}(x,\hat{Q}) \in \Delta_G^n to mean

s_{G,\phi}^{nk}(x,\hat{Q}):=\E_{\sigma_Q}[s_{G,\phi}^{nk}(x,\hat{Q}[z])]

For a family {\hat{Q}^n}{n \in \mathcal{P}} of (poly,rlog)-predictors, we will use the notations s{G,\phi}^k(x,\hat{Q}) \in \prod_{n \in \mathcal{P}} \Delta_G^n and s_{G,\phi}^{\bar{n}k}(x,\hat{Q}) \in \prod_{m \in \mathcal{P} \setminus n} \Delta_G^m to mean

s_G^k(x,\hat{Q}):=\prod_{n \in \mathcal{P}} s_{G,\phi}^{nk}(x,\hat{Q}^n)

s_G^{\bar{n}k}(x,\hat{Q}):=\prod_{m \in \mathcal{P} \setminus n} s_{G,\phi}^{mk}(x,\hat{Q}^m)

Corollary 2

Fix G=(\mu,\mathcal{P},\mathcal{A},u) a distributional game, {\phi^n \in \Phi}{n \in \mathcal{P}} and \hat{P} an \mathcal{E}{2(ll,\phi)}^*(poly,rlog)-optimal predictor system for \mathcal{R}_G^\phi. Consider n \in \mathcal{P}, \epsilon \in (0,1) and \hat{A} an \mathcal{A}^n-valued (\phi^n)^{1-\epsilon}(poly,rlog) scheme. Then

\E_{\mu^k}[\E_{s_{G,\phi}^k(x,\hat{P})}[u^n]] \geq \E_{\mu^k}[\E_{\hat{A}^k(x) \times s_{G,\phi}^{\bar{n}k}(x,\hat{P})}[u^n]] - O((\phi^n)^{-\frac{1}{\infty}})

We now move from studying strict maximizers to studying thermalizers.

Theorem 2

Fix a proto-error space \mathcal{E}. Consider \mathcal{A} a finite set, \mu a word ensemble and {f_a: \Supp \mu \rightarrow [0,1]}{a \in \mathcal{A}}. Suppose {\hat{P}a}{a \in \mathcal{A}} are \mathcal{E}(poly,rlog)-optimal predictors for f and T: \Nats^2 \rightarrow \Reals^{>0} is some function. Assume that \sigma{P_a} and r_{P_a} don’t depend on a. Consider \hat{A} an \mathcal{A}-valued (poly,rlog)-bischeme. Suppose \hat{M}_T is another \mathcal{A}-valued (poly,rlog)-bischeme satisfying

|\Pr_{\hat{\sigma}M}[M_T^{kj}(x)=a] - E{\hat{\sigma}_P}[Z_T^{kj}(x,y)^{-1} 2^{\frac{P_a^{kj}(x,y)}{T^{kj}}}]| \leq \delta_r(k,j)

Here y is sampled from \hat{\sigma}P, Z_T^{kj}(x,y):=\sum{a \in \mathcal{A}} 2^{\frac{P_a^{kj}(x,y)}{T^{kj}}} is the normalization factor and \delta_r,T\delta_r^{\frac{1}{2}} \in \mathcal{E}^{\frac{1}{4}}. Then, there is \delta \in \mathcal{E}^{\frac{1}{4}} s.t.

\E_{\mu^k}[\E_{\hat{\sigma}{M_T}^{kj}}[f{\hat{M}T^{kj}(x)}(x)] + T^{kj} \H(\hat{M}T^{kj}(x))] \geq \E{\mu^k}[\E{\hat{\sigma}A^{kj}}[f{\hat{A}^{kj}(x)}(x)] + T^{kj} \H(\hat{A}^{kj}(x))] - \delta(k,j)

Here \H for stands the (base 2) Shannon entropy of a probability measure on \mathcal{A}.

Corollary 3

Fix \phi \in \Phi. Consider \mathcal{A} a finite set, \mu a word ensemble and {f_a: \Supp \mu \rightarrow [0,1]}{a \in \mathcal{A}}. Suppose {\hat{P}a}{a \in \mathcal{A}} are \mathcal{E}{2(ll,\phi)}(poly,rlog)-optimal predictors for f and T: \Nats \rightarrow \Reals^{>0} a bounded function. Consider \epsilon \in (0,1) and \hat{A} an \mathcal{A}-valued \phi^{1-\epsilon}(poly,rlog)-scheme. Assume \hat{M}_T is as in Theorem 2. Then

\E_{\mu^k}[\E_{\lambda_\phi^k}[E_{\hat{\sigma}{M_T}^{kj}}[f{\hat{M}T^{kj}(x)}(x)]] + T^k \H(\E{\lambda_\phi^k}[ \hat{M}T^{kj}(x)])] \geq \E{\mu^k}[\E_{\hat{\sigma}A^k}[f{\hat{A}^k(x)}(x)] + T^k \H(\hat{A}^k(x))] - O(\phi^{-\frac{1}{\infty}})

Here \E_{\lambda_\phi^k}[\hat{M}_T^{kj}(x)] stands for averaging the probability measure \hat{M}T^{kj}(x) on \mathcal{A} with respect to parameter j using probability distribution \lambda\phi^k.

Construction 3

Consider G=(\mu,\mathcal{P},\mathcal{A},u) a distributional game, {\phi^n \in \Phi}_{n \in \mathcal{P}} and T: \mathcal{P} \times \Nats \rightarrow \Reals^{>0}. We construct the reflective system \mathcal{R}G^{\phi,T}=(\mathcal{P},u{\phi,T},\mu_G).

Define s_{G,\phi,T}^n: \Nats \times \Supp \mu \times \Pi_{\mathcal{P}} \rightarrow \Delta_G^n by

\Pr_{s_{G,\phi,T}^{nk}(x,\pi)}[a]:=\E_{\lambda_{\phi^n}^k}[\E_{U(\pi)^{nkj}}[Z_{G,\phi,T}^{nkj}(x,y,\pi)^{-1} 2^{(T^{nk})^{-1}\pi^{nkj}((k,x,a),y)}]]

Here Z is the normalization factor.

Define s_{G,\phi,T}: \Nats \times \Supp \mu \times \Pi_{\mathcal{P}} \rightarrow \prod_{n \in \mathcal{P}} \Delta_G^n by

s_{G,\phi,T}^k(x,\pi) := \prod_{n \in \mathcal{P}} s_{G,\phi,T}^{nk}(x,\pi)

Define s_{G,\phi,T}^{\bar{n}}: \Nats \times \Supp \mu \times \Pi_{\mathcal{P}} \rightarrow \prod_{m \in \mathcal{P} \setminus n} \Delta_G^m by

s_{G,\phi,T}^{\bar{n}k}(x,\pi) := \prod_{m \in \mathcal{P} \setminus n} s_{G,\phi,T}^{mk}(x,\pi)

Finally, define u_{\phi,T} by

u_{\phi,T}^{nk}(x,a,\pi):=\E_{a \times s_{G,\phi,T}^{\bar{n}k}(x,\pi)}[u^n]

We define the notations s_{G,\phi,T}^{nk}(x,\hat{Q}), s_{G,\phi,T}^k(x,\hat{Q}) and s_{G,\phi,T}^{\bar{n}k}(x,\hat{Q}) analogously to before.

Corollary 4

Fix G=(\mu,\mathcal{P},\mathcal{A},u) a distributional game, {\phi^n \in \Phi}{n \in \mathcal{P}}, T: \mathcal{P} \times \Nats \rightarrow \Reals^{>0} bounded and \hat{P} an \mathcal{E}{2(ll,\phi)}^*(poly,rlog)-optimal predictor system for \mathcal{R}_G^{\phi,T}. Consider n \in \mathcal{P}, \epsilon \in (0,1) and \hat{A} an \mathcal{A}^n-valued (\phi^n)^{1-\epsilon}(poly,rlog) scheme. Then

\E_{\mu^k}[\E_{s_{G,\phi,T}^k(x,\hat{P})}[u^n] + T^k \H(s_{G,\phi,T}^{nk}(x,\hat{P}))] \geq \E_{\mu^k}[\E_{\hat{A}^k(x) \times s_{G,\phi,T}^{\bar{n}k}(x,\hat{P})}[u^n] + T^k \H(\hat{A}^k(x))] - O((\phi^n)^{-\frac{1}{\infty}})

Finally, we show that assuming \phi^n doesn’t depend on n and T doesn’t fall to zero too fast, deterministic advice is sufficient to construct an optimal predictor system for \mathcal{R}_G^{\phi,T}.

Definition 3

Consider a reflective system \mathcal{R}=(\Sigma,f,\mu) and {\phi^n \in \Phi}{n \in \Sigma}. \mathcal{R} is said to be \phi-Hoelder when there are {c^{nk} \in \Reals^{>0}}{n \in \Sigma, k \in \Nats}, {\rho^n: \Sigma \rightarrow [0,1]}{n \in \Sigma}, {\psi^{nm} \in \Phi}{n,m \in \Sigma}, {\alpha^n \in (0,1]}{n \in \Sigma} and {\delta^n: \Nats \rightarrow \Reals^{\geq 0}}{n \in \Sigma} s.t.

(i) \forall n \in \Sigma , \exists \epsilon^n > 0: c^{nk}=O(\phi^n(k)^{\frac{\alpha^n}{2} - \epsilon^n})

(ii) \sum_{m \in \Sigma} \rho^n(m) = 1

(iii) \psi^{nm} \geq \phi^n

(iv) \delta^n(k) = O(\phi^n(k)^{-\frac{1}{\infty}})

(v) \E_{\mu^{nk}}[(f^n(x,\pi)-f^n(x,\tilde{\pi}))^2] \leq c^{nk} \E_{\rho^n}[\E_{\mu^{mk} \times \lambda_{\psi^{nm}}^k}[\E_{U(\pi)^{mkj} \times U(\tilde{\pi})^{mkj}}[(\pi^{mkj}(x,y)-\tilde{\pi}^{mkj}(x,y))^2]]]^{\alpha^n} + \delta^n(k)

Theorem 3

Consider a finite set \Sigma, a reflective system \mathcal{R}=(\Sigma,f,\mu) and {\phi^n \in \Phi}{n \in \Sigma}. If \mathcal{R} is \phi-Hoelder then it has an \mathcal{E}{2(ll,\phi)}^*(poly,log)-optimal predictor system.

Theorem 4

Consider G=(\mu,\mathcal{P},\mathcal{A},u) a distributional game, \phi \in \Phi and T: \mathcal{P} \times \Nats \rightarrow \Reals^{>0}. Assume \frac{1}{T^{nk}} = O(\phi(k)^{\frac{1}{4} - \epsilon}) for some \epsilon > 0. Then \mathcal{R}_G^{\phi,T} is \phi-Hoelder.

Appendix A

Proposition A.1

Suppose h: \Reals^{\geq 0} \rightarrow \Reals^{\geq 0} is a non-decreasing function s.t. \int_0^\infty h(x)^{-1} dx < \infty. Define \delta_h: \Nats^2 \rightarrow \Reals^{\geq 0} by

\delta_h(k,j):=\min(\frac{\log \log (k+3)}{h(\log \log (j+3))},1)

Then, \delta_h \in \mathcal{E}_{2(ll)}.

Proof of Proposition A.1

Consider \phi \in \Phi. We have

\LimSup{k} , \phi(k) E_{\lambda_\phi^k}[\delta_h(k,j)] = \LimSup{k} , \phi(k) \frac{\sum_{j=2}^{t_\phi(k)-1} (\log\log(j+1)-\log \log j) \delta_h(k,j)}{\log \log t_\phi(k)}

\LimSup{k} , \phi(k) E_{\lambda_\phi^k}[\delta_h(k,j)] = \LimSup{k} , \phi(k) \frac{\int_{x=2}^{t_\phi(k)} \delta_h(k,\Floor{x}) d (\log \log x)}{\phi(k) \log\log k}

\LimSup{k} , \phi(k) E_{\lambda_\phi^k}[\delta_h(k,j)] \leq \LimSup{k} , \int_{x=2}^{t_\phi(k)} h(\log\log (\Floor{x}+3))^{-1} d (\log \log x)

\LimSup{k} , \phi(k) E_{\lambda_\phi^k}[\delta_h(k,j)] \leq \LimSup{k} , \int_{x=2}^{t_\phi(k)} h(\log\log x)^{-1} d (\log \log x)

\LimSup{k} , \phi(k) E_{\lambda_\phi^k}[\delta_h(k,j)] \leq \int_0^\infty h(t)^{-1} dt

Proof of Proposition 1

Mostly obvious modulo Proposition A.1. To see \mathcal{E}{2(ll,\phi)} is stable for non-decreasing \phi, consider a non-constant polynomial p: \Nats \rightarrow \Nats and \delta \in \mathcal{E}{2(ll,\phi)}. Define \delta'(k,j):=\delta(p(k),j). To get the desired condition for \delta' and \psi \in \Phi with \psi \leq \phi, consider any \psi' \in \Phi s.t.\psi' \leq \phi and for sufficiently large k we have \psi'(p(k))=\psi(k). Suche \psi' exists since for for k sufficiently large \phi(k) \leq \phi(p(k)). We have

\LimSup{k} , \psi'(k) E_{\lambda_{\psi'}^k}[\delta(k,j)] < \infty

In particular

\LimSup{k} ,\psi'(p(k)) E_{\lambda_{\psi'}^{p(k)}}[\delta(p(k),j)] < \infty

\LimSup{k} , \psi(k) E_{\lambda_{\psi}^k}[\delta'(k,j)] < \infty

Proposition A.2

Consider a polynomial q: \Nats^2 \rightarrow \Nats. There is a function \lambda_q: \Nats^3 \rightarrow [0,1] s.t.

(i) \forall k,j \in \Nats: \sum_{i \in \Nats} \lambda_q(k,j,i) = 1

(ii) For any function \epsilon: \Nats^2 \rightarrow [0,1] we have

\epsilon(k,j) - \sum_{i \in \Nats} \lambda_q(k,j,i) , \epsilon(k,q(k,j)+i) \in \mathcal{E}_{2(ll)}

Proof of Proposition A.2

Given functions q_1,q_2: \Nats^2 \rightarrow \Nats s.t.q_1(k,j) \geq q_2(k,j) for k,j \gg 0, the proposition for q_1 implies the proposition for q_2 by setting

\lambda_{q_2}(k,j,i):=\begin{cases}\lambda_{q_1}(k,j,i-q_1(k,j)+q_2(k,j)) & \text{if } i-q_1(k,j)+q_2(k,j) \geq 0 \ 0 & \text{if } i-q_1(k,j)+q_2(k,j) < 0 \end{cases}

Therefore, it is enough to prove to proposition for functions of the form q(k,j)=j^{m+n \log k} for m > 0.

Consider any \phi \in \Phi. We have

\LimSup{k} , \phi(k) \frac{\log\log k}{\phi(k) \log\log k} < \infty

\LimSup{k} , \phi(k) \frac{\log (m+n \log k)}{\phi(k) \log \log k} < \infty

\LimSup{k} , \phi(k) \frac{\int\limits_{x=2}^{2^{m+n \log k}} d(\log \log x)}{\phi(k) \log \log k} < \infty

Since \epsilon takes values in [0,1]

\LimSup{k} , \phi(k) \frac{\int\limits_{x=2}^{2^{m+n \log k}} \epsilon(k,\Floor{x}) d(\log \log x)}{\phi(k) \log \log k} < \infty

Similarly

\LimSup{k} , \phi(k) \frac{\int\limits_{x=t_\phi(k)}^{t_\phi(k)^{m+n \log k}} \epsilon(k,\Floor{x}) d(\log \log x)}{\phi(k) \log \log k} < \infty

The last two equations imply that

\LimSup{k} , \phi(k) \frac{\int\limits_{x=2}^{t_\phi(k)} \epsilon(k,\Floor{x}) d(\log \log x) - \int\limits_{x=2^{m+n \log k}}^{t_\phi(k)^{m+n \log k}} \epsilon(k,\Floor{x}) d(\log \log x)}{\phi(k) \log \log k} < \infty

Raising x to a power is equivalent to adding a constant to \log \log x, therefore

\LimSup{k} , \phi(k) \frac{\int\limits_{x=2}^{t_\phi(k)} \epsilon(k,\Floor{x}) d(\log \log x) - \int\limits_{x=2}^{t_\phi(k)} \epsilon(k,\Floor{x^{m+n \log k}}) d(\log \log x)}{\phi(k) \log \log k} < \infty

\LimSup{k} , \phi(k) \frac{\int\limits_{x=2}^{t_\phi(k)} (\epsilon(k,\Floor{x})-\epsilon(k,\Floor{x^{m+n \log k}})) d(\log \log x)}{\phi(k) \log \log k} < \infty

Since \Floor{x^{m+n \log k}} \geq \Floor{x}^{m+n \log k} we can choose \lambda_q satisfying condition (i) so that

\int\limits_{x=j}^{j+1} \epsilon(k,\Floor{x^{m+n \log k}}) d(\log\log x) = (\log\log(j+1)-\log\log j) \sum_i \lambda_q(k,j,i) , \epsilon(k,j^{m+n \log k}+i)

It follows that

\int\limits_{x=j}^{j+1} \epsilon(k,\Floor{x^{m+n \log k}}) d(\log\log x) = \int\limits_{x=j}^{j+1} \sum_i \lambda_q(k,\Floor{x},i) , \epsilon(k,\Floor{x}^{m+n \log k}+i) d(\log\log x)

\LimSup{k} , \phi(k) \frac{\int\limits_{x=2}^{t_\phi(k)} (\epsilon(k,\Floor{x})-\sum_i \lambda_q(k,\Floor{x},i) , \epsilon(k,\Floor{x}^{m+n \log k}+i)) d(\log \log x)}{\phi(k) \log \log k} < \infty

\LimSup{k} , \phi(k) \frac{\sum_{j=2}^{t_\phi(k)-1} (\log\log(j+1)-\log\log j)(\epsilon(k,j)-\sum_i \lambda_q(k,j,i) , \epsilon(k,j^{m+n \log k}+i))}{\phi(k) \log \log k} < \infty

\epsilon(k,j) - \sum_{i \in \Nats} \lambda_q(k,j,i) , \epsilon(k,q(k,j)+i) \in \mathcal{E}_{2(ll)}

Lemma A.1

Consider (f, \mu) a distributional estimation problem, \hat{P}, \hat{Q} (poly,rlog)-predictors. Suppose p: \Nats^2 \rightarrow \Nats a polynomial, \phi \in \Phi and \delta \in \mathcal{E}_{2(ll,\phi)} are s.t.

\forall i,k,j \in \Nats: \E[(\hat{P}^{k,p(k,j)+i}-f)^2] \leq \E[(\hat{Q}^{kj}-f)^2] + \delta(k,j)

Then \exists \delta' \in \mathcal{E}_{2(ll,\phi)} s.t.

\E[(\hat{P}^{kj}-f)^2] \leq \E[(\hat{Q}^{kj}-f)^2] + \delta'(k,j)

The proof of Lemma A.1 is analogous to before and we omit it.

Appendix B

The following is a slightly stronger version of one direction of the orthogonality lemma.

Lemma B.1

Consider (f, \mu) a distributional estimation problem and \hat{P} an \mathcal{E}(poly,rlog)-optimal predictor for (f, \mu). Then there are c_1,c_2 \in \Reals and an \mathcal{E}^{\frac{1}{2}}-moderate function \delta: \Nats^5 \rightarrow [0,1] s.t. for any k,j,r,l,t \in \Nats, \tau a probability measure on \WordsUpToLen{l} and Q: \Supp \mu^k \times \WordsLen{r_P(k,j)} \times \Words \times \WordsLen{r} \times \WordsUpToLen{l} \xrightarrow{alg} \Rats that runs in time t on any valid input

\Abs{\E_{\mu^k \times U^{r_P(k,j)} \times \sigma_P^{kj} \times U^r \times \tau}[Q(x,y,z,u,w)(P^{kj}(x,y,z)-f(x))]} \leq (c_1 + c_2 E_{\mu^k \times U^{r_P(k,j)} \times \sigma_P^{kj} \times U^r \times \tau}[Q(x,y,z,u,w)^2]) \delta(k,j,t,2^l,2^{\Abs{Q}})

The proof is analogous to the original and we omit it.

Lemma B.2

Fix a proto-error space \mathcal{E}. Consider \mathcal{A} a finite set, \mu a word ensemble and {f_a: \Supp \mu \rightarrow [0,1]}{a \in \mathcal{A}}. Suppose {\hat{P}a}{a \in \mathcal{A}} are \mathcal{E}(poly,rlog)-optimal predictors for f. Assume that \sigma{P_a} and r_{P_a} don’t depend on a. Consider \hat{A} an \mathcal{A}-valued (poly,rlog)-bischeme. Assume \hat{\sigma}_A factors as \hat{\sigma}_P \times \tau. Then

\Abs{\E_{\mu \times \hat{\sigma}P \times \tau}[P{A(x,y,z)}(x,y) - f_{A(x,y,z)}]} \in \mathcal{E}^{\frac{1}{2}}

Proof of Lemma B.2

\E_{\mu \times \hat{\sigma}P \times \tau}[P{A(x,y,z)}(x,y) - f_{A(x,y,z)}(x)] = \sum_{a \in \mathcal{A}} \E_{\mu \times \hat{\sigma}P \times \tau}[\delta{A(x,y,z),a} (P_a(x,y) - f_a(x))]

Applying Lemma B.1 we get the desired result.

Proof of Theorem 1

Lemma B.2 implies

\Abs{\E_{\mu \times \hat{\sigma}P \times \hat{\sigma}A}[\hat{P}{\hat{A}} - f{\hat{A}}]} \in \mathcal{E}^{\frac{1}{2}}

\Abs{\E_{\mu \times \hat{\sigma}P \times \tau}[\hat{P}{\hat{M}} - f_{\hat{M}}]} \in \mathcal{E}^{\frac{1}{2}}

Combining the two

\Abs{\E_{\mu \times \hat{\sigma}P \times \tau}[\hat{P}{\hat{M}} - f_{\hat{M}}]} + \Abs{\E_{\mu \times \hat{\sigma}P \times \hat{\sigma}A}[\hat{P}{\hat{A}} - f{\hat{A}}]} \in \mathcal{E}^{\frac{1}{2}}

\Abs{\E_{\mu \times \hat{\sigma}P \times \tau}[\hat{P}{\hat{M}} - f_{\hat{M}}] - \E_{\mu \times \hat{\sigma}P \times \hat{\sigma}A}[\hat{P}{\hat{A}} - f{\hat{A}}]} \in \mathcal{E}^{\frac{1}{2}}

\Abs{\E_{\mu \times \hat{\sigma}P \times \tau \times \hat{\sigma}A}[\hat{P}{\hat{M}} - \hat{P}{\hat{A}}] - \E_{\mu \times \hat{\sigma}P \times \tau \times \hat{\sigma}A}[f{\hat{M}} - f{\hat{A}}]} \in \mathcal{E}^{\frac{1}{2}}

The construction of \hat{M} implies that for every x \in \Supp \mu^k we have

\E_{\hat{\sigma}P \times \tau}[P{M^{kj}(x,y,z)}^{kj}(x,y)] \geq \E_{\hat{\sigma}_P \times \hat{\sigma}A}[P{A^{kj}(x,z)}^{kj}(x,y)]

Combining with the above we get the desired result.

Proposition B.1

Consider \phi \in \Phi, \epsilon \in (0,1), \zeta: \Nats^2 \rightarrow \Reals bounded below and \xi: \Nats \rightarrow \Reals bounded. Assume that \forall k,j \in \Nats: j \geq t_{\phi^{1-\epsilon}}(k) \implies \zeta^{kj}=\xi^k. Then \E_{\lambda_\phi^k}[\zeta^{kj}] \geq \xi^k - O(\phi(k)^{-\epsilon}).

Proof of Proposition B.1

\E_{\lambda_\phi^k}[\zeta^{kj}] = \Pr_{\lambda_\phi^k}[j < t_{\phi^{1-\epsilon}}(k)] \E_{\lambda_\phi^k}[\zeta^{kj} \mid j < t_{\phi^{1-\epsilon}}(k)] + \Pr_{\lambda_\phi^k}[j \geq t_{\phi^{1-\epsilon}}(k)] \E_{\lambda_\phi^k}[\zeta^{kj} \mid j \geq t_{\phi^{1-\epsilon}}(k)]

\E_{\lambda_\phi^k}[\zeta^{kj}] \geq \frac{\log\log t_{\phi^{1-\epsilon}}(k)}{\log\log t_\phi(k)} \inf \zeta + \frac{\log\log t_\phi(k) - \log\log t_{\phi^{1-\epsilon}}(k)}{\log\log t_\phi(k)} \xi^k

\E_{\lambda_\phi^k}[\zeta^{kj}] \geq O(\phi(k)^{-\epsilon}) \inf \zeta +(1 - O(\phi(k)^{-\epsilon})) \xi^k

\E_{\lambda_\phi^k}[\zeta^{kj}] \geq \xi^k - O(\phi(k)^{-\epsilon})

Proof of Corollary 1

Choose some a_0 \in \mathcal{A}. Define the \mathcal{A}-valued (poly,rlog)-scheme \hat{B} by

\hat{B}^{kj}(x):=\begin{cases}\hat{A}^k(x) \text{ if } j \geq t_{\phi^{1-\epsilon}}(k) \ a_0 \text{ otherwise} \end{cases}

Applying Theorem 1 we get \delta \in \mathcal{E}_{2(ll,\phi)}^{\frac{1}{2}} s.t.

\E_{\mu^k \times \hat{\sigma}M^{kj}}[f{\hat{M}^{kj}}] \geq \E_{\mu^k \times \hat{\sigma}B^{kj}}[f{\hat{B}^{kj}}] - \delta(k,j)

\E_{\mu^k \times \lambda_\phi^k}[\E_{\hat{\sigma}M^{kj}}[f{\hat{M}^{kj}}]] \geq \E_{\mu^k \times \lambda_\phi^k}[\E_{\hat{\sigma}B^{kj}}[f{\hat{B}^{kj}}]] - \E_{\lambda_\phi^k}[\delta(k,j)]

Proposition B.1 implies

\E_{\mu^k \times \lambda_\phi^k}[\E_{\hat{\sigma}B^{kj}}[f{\hat{B}^{kj}}]] \geq \E_{\mu^k \times \hat{\sigma}A^k}[f{\hat{A}^k}] - O(\phi(k)^{-\epsilon})

Also

\E_{\lambda_\phi^k}[\delta(k,j)] \leq \E_{\lambda_\phi^k}[\delta(k,j)^2]^{\frac{1}{2}}

\E_{\lambda_\phi^k}[\delta(k,j)] = O(\phi(k)^{-\frac{1}{2}})

Putting everything together we get the desired result.

Proof of Corollary 2

For each a \in \mathcal{A}^n define \hat{P}^{kj}a(k,x):=\hat{P}^{kj}(k,x,a) and u{\phi,a}^n(k,x):=u_\phi^{nk}(x,a,\hat{P}). It is easy to see \hat{P}a is an \mathcal{E}{2(ll,\phi)}^*(poly,rlog)-optimal predictor for u_{\phi,a}. We have

\E_{s_{G,\phi}^k(x,\hat{P})}[u^n] = \E_{\lambda_{\phi^n}^k}[\E_{\hat{\sigma}M^{kj}}[u{\phi,\hat{M}^{kj}(x)}^{nk}(x)]] \pm O(\phi^n(k)^{-1})

Here \hat{M}^{kj}(x,y,z) selects an element of M_G^{nkj}(x,y,\hat{P}[z]) uniformly at random up to a small rounding error which yields the O(\phi^n(k)^{-1}) term. Also

\E_{\hat{A}^k(x) \times s_{G,\phi}^{\bar{n}k}(x,\hat{P})}[u^n] = \E_{\hat{\sigma}A^{k}}[u{\phi,\hat{A}^{k}(x)}^{nk}(x)]

Applying Corollary 1 we get the desired result.

Proposition B.2

Consider \mathcal{A} a finite set, u: \mathcal{A} \rightarrow \Reals and T > 0. Define \vartheta: \mathcal{A} \rightarrow [0,1] by \vartheta(a):=Z^{-1} 2^{\frac{u(a)}{T}} where Z is the normalization constant \sum_{a \in \mathcal{A}} 2^{\frac{u(a)}{T}}. Consider \rho: \mathcal{A} \rightarrow [0,1] with \sum_{a \in \mathcal{A}} \rho(a) = 1. Then

\E_{\vartheta}[u] + T \H(\vartheta) = \E_{\rho}[u] + T \H(\rho) + T \KL{\rho}{\vartheta}

Proof of Proposition B.2

\KL{\rho}{\vartheta} = \E_\rho[\log \frac{\rho}{\vartheta}]

\KL{\rho}{\vartheta} = \E_\rho[\log \frac{\rho}{Z^{-1} 2^{\frac{u}{T}}}]

\KL{\rho}{\vartheta} = \E_\rho[\log \rho + \log Z - \frac{u}{T}]

\KL{\rho}{\vartheta} = -\H(\rho) + \log Z - \frac{\E_\rho[u]}{T}

T \KL{\rho}{\vartheta} = T \log Z - (\E_\rho[u] + T \H(\rho))

On the other hand

\H(\vartheta) = -\E_\vartheta[\log \vartheta]

\H(\vartheta) = -\E_\vartheta[\log (Z^{-1} 2^{\frac{u}{T}})]

\H(\vartheta) = -\E_\vartheta[-\log Z + \frac{u}{T}]

\H(\vartheta) = \log Z - \frac{\E_{\vartheta}[u]}{T}

T \log Z = \E_{\vartheta}[u] + T \H(\vartheta)

Combining the two we get the desired result.

Proposition B.3

Consider \mathcal{A} a finite set, u_1,u_2: \mathcal{A} \rightarrow \Reals and T > 0. Define the probability measures \vartheta_1, \vartheta_2: \mathcal{A} \rightarrow [0,1] by \vartheta_i(a):=Z_i^{-1} 2^{\frac{u_i(a)}{T}} where Z_i are normalization factors. Then

\KL{\vartheta_1}{\vartheta_2} \leq T^{-1} \sum_{a \in \mathcal{A}} \Abs{u_1(a) - u_2(a)}

Proof of Proposition B.3

\KL{\vartheta_1}{\vartheta_2} = \E_{\vartheta_1}[\log \frac{\vartheta_1}{\vartheta_2}]

\KL{\vartheta_1}{\vartheta_2} = \E_{\vartheta_1}[\log \frac{Z_1^{-1} 2^{\frac{u_1}{T}}}{Z_2^{-1} 2^{\frac{u_2}{T}}}]

\KL{\vartheta_1}{\vartheta_2} = \E_{\vartheta_1}[\frac{u_1-u_2}{T}] + \log \frac{Z_2}{Z_1}

\KL{\vartheta_1}{\vartheta_2} = \E_{\vartheta_1}[\frac{u_1-u_2}{T}] + \log \frac{\sum_{a \in \mathcal{A}} 2^{\frac{u_2(a)}{T}}}{Z_1}

\KL{\vartheta_1}{\vartheta_2} = \E_{\vartheta_1}[\frac{u_1-u_2}{T}] + \log \sum_{a \in \mathcal{A}} Z_1^{-1} 2^{\frac{u_1(a)}{T}} 2^{\frac{u_2(a)-u_1(a)}{T}}

\KL{\vartheta_1}{\vartheta_2} = \E_{\vartheta_1}[\frac{u_1-u_2}{T}] + \log \E_{\vartheta_1}[2^{\frac{u_2-u_1}{T}}]

\KL{\vartheta_1}{\vartheta_2} \leq T^{-1}(\max_{a \in \mathcal{A}} (u_1(a) - u_2(a)) - \min_{a \in \mathcal{A}} (u_1(a) - u_2(a)))

\KL{\vartheta_1}{\vartheta_2} \leq T^{-1} \sum_{a \in \mathcal{A}} \Abs{u_1(a) - u_2(a)}

Proposition B.4

Consider \mathcal{A} a finite set. There is a c > 0 s.t. for any \rho_1, \rho_2 probability measures on \mathcal{A} we have

\Abs{\H(\rho_1)-\H(\rho_2)} \leq c d_{TV}(\rho_1, \rho_2)^{\frac{1}{2}}

Here d_{TV}(\rho_1, \rho_2) := \frac{1}{2} \sum_{a \in \mathcal{A}} \Abs{\rho_1(a)-\rho_2(a)} is the total variation distance.

Proof of Proposition B.4

Given 0 \leq p \leq q \leq 1 we have

\Abs{q \log q - p \log p} = \Abs{\int_p^q d(x \log x)}

\Abs{q \log q - p \log p} = \Abs{\int_p^q (\log x + \frac{1}{\ln 2}) dx}

\Abs{q \log q - p \log p} = \Abs{\int_p^q \log (\mathrm{e}x) dx}

\Abs{q \log q - p \log p} \leq \int_p^q \Abs{\log (\mathrm{e}x)} dx

For some c' > 0 we have \Abs{\log (\mathrm{e}x)} \leq \frac{c'}{2}x^{-\frac{1}{2}} for x \in (0,1] hence

\Abs{q \log q - p \log p} \leq \int_p^q \frac{c'}{2}x^{-\frac{1}{2}} dx

\Abs{q \log q - p \log p} \leq c'(q^{\frac{1}{2}}-p^{\frac{1}{2}})

\Abs{q \log q - p \log p} \leq c'(q-p)^{\frac{1}{2}}

\Abs{\H(\rho_1)-\H(\rho_2)} = \Abs{\sum_{a \in \mathcal{A}} \rho_1(a) \log \rho_1(a) - \rho_2(a) \log \rho_2(a)}

\Abs{\H(\rho_1)-\H(\rho_2)} \leq \sum_{a \in \mathcal{A}} \Abs{\rho_1(a) \log \rho_1(a) - \rho_2(a) \log \rho_2(a)}

\Abs{\H(\rho_1)-\H(\rho_2)} \leq \sum_{a \in \mathcal{A}} c' \Abs{\rho_1(a)-\rho_2(a)}^{\frac{1}{2}}

Using the concavity of the square root we complete the proof.

Proof of Theorem 2

For any k,j \in \Nats, x \in \Supp \mu^k and y \in \Words^2 define \vartheta^{kj}(x) and \vartheta^{kj}(x,y) probability measures on \mathcal{A} by

\Pr_{\vartheta^{kj}(x)}[a]:=W^{kj}(x)^{-1} 2^{(T^{kj})^{-1} \E_{\hat{\sigma}_P}[\hat{P}_a^{kj}(x)]}

\Pr_{\vartheta^{kj}(x,y)}[a]:=Z_T^{kj}(x,y)^{-1} 2^{(T^{kj})^{-1} P_a^{kj}(x,y)}

Here W is the normalization factor. By the convexity of Kullback-Leibler divergence

\KL{\E_{\hat{\sigma}P}[\vartheta^{kj}(x,y)]}{\vartheta^{kj}(x)} \leq \E{\hat{\sigma}_P}[\KL{\vartheta^{kj}(x,y)}{\vartheta^{kj}(x)}]

Applying Proposition B.3

\KL{\E_{\hat{\sigma}P}[\vartheta^{kj}(x,y)]}{\vartheta^{kj}(x)} \leq \E{\hat{\sigma}P}[(T^{kj})^{-1} \sum{a \in \mathcal{A}} \Abs{P_a^{kj}(x,y)-\E_{\hat{\sigma}_P}[P_a^{kj}(x,y')]}]

\KL{\E_{\hat{\sigma}P}[\vartheta^{kj}(x,y)]}{\vartheta^{kj}(x)} \leq (T^{kj})^{-1} \sum{a \in \mathcal{A}} \E_{\hat{\sigma}P}[(P_a^{kj}(x,y)-\E{\hat{\sigma}_P}[P_a^{kj}(x,y')])^2]^{\frac{1}{2}}

\KL{\E_{\hat{\sigma}P}[\vartheta^{kj}(x,y)]}{\vartheta^{kj}(x)} \leq (T^{kj})^{-1} \sum{a \in \mathcal{A}} \E_{\hat{\sigma}_P \times \hat{\sigma}_P}[(P_a^{kj}(x,y)-P_a^{kj}(x,y'))^2]^{\frac{1}{2}}

Applying the uniqueness theorem, we get

T^{kj} \E_{\mu^k}[\KL{\E_{\hat{\sigma}_P}[\vartheta^{kj}(x,y)]}{\vartheta^{kj}(x)}] \in \mathcal{E}^{\frac{1}{4}}

We also have

d_{TV}(\hat{M}T^{kj}(x),\E{\hat{\sigma}_P}[\vartheta^{kj}(x,y)]) \leq c_1 \delta_r(k,j)

for some c_1 > 0. Applying Propositions B.2 and B.4 we get that

T^{kj} \Abs{\KL{\hat{M}T^{kj}(x)}{\vartheta^{kj}(x)} - \KL{\E{\hat{\sigma}_P}[\vartheta^{kj}(x,y)]}{\vartheta^{kj}(x)}} \leq c_2 \delta_r(k,j)+ c_3 T^{kj} \delta_r(k,j)^{\frac{1}{2}}

for some c_2, c_3 > 0. Combining with the above, we get

T^{kj} \E_{\mu^k}[\KL{\hat{M}_T^{kj}(x)}{\vartheta^{kj}(x)}] \in \mathcal{E}^{\frac{1}{4}}

In particular, for some \delta \in \mathcal{E}^{\frac{1}{4}}

T^{kj} \E_{\mu^k}[\KL{\hat{M}T^{kj}(x)}{\vartheta^{kj}(x)}] \leq T^{kj} \E{\mu^k}[\KL{\hat{A}^{kj}(x)}{\vartheta^{kj}(x)}] + \delta(k,j)

-T^{kj} \E_{\mu^k}[\KL{\hat{M}T^{kj}(x)}{\vartheta^{kj}(x)}] \geq -T^{kj} \E{\mu^k}[\KL{\hat{A}^{kj}(x)}{\vartheta^{kj}(x)}] - \delta(k,j)

Applying Proposition B.2

\E_{\mu^k}[\E_{\hat{\sigma}{M_T}^{kj}}[\hat{P}{\hat{M}T^{kj}(x)}(x)] + T^{kj} \H(\hat{M}T^{kj}(x))] \geq \E{\mu^k}[\E{\hat{\sigma}A^{kj}}[\hat{P}{\hat{A}^{kj}(x)}(x)] + T^{kj} \H(\hat{A}^{kj}(x))] - \delta(k,j)

Applying Lemma B.2 we get the desired result.

Proof of Corollary 3

Choose some a_0 \in \mathcal{A}. Define the \mathcal{A}-valued (poly,rlog)-scheme \hat{B} by

\hat{B}^{kj}(x):=\begin{cases}\hat{A}^k(x) \text{ if } j \geq t_{\phi^{1-\epsilon}}(k) \ a_0 \text{ otherwise} \end{cases}

Applying Theorem 2 we get \delta \in \mathcal{E}_{2(ll,\phi)}^{\frac{1}{4}} s.t.

\E_{\mu^k}[\E_{\hat{\sigma}{M_T}^{kj}}[f{\hat{M}T^{kj}(x)}(x)] + T^k \H(\hat{M}T^{kj}(x))] \geq \E{\mu^k}[\E{\hat{\sigma}B^{kj}}[f{\hat{B}^{kj}(x)}(x)] + T^k \H(\hat{B}^{kj}(x))] - \delta(k,j)

\E_{\mu^k}[\E_{\lambda_\phi^k}[\E_{\hat{\sigma}{M_T}^{kj}}[f{\hat{M}T^{kj}(x)}(x)]] + T^k \E{\lambda_\phi^k}[\H(\hat{M}T^{kj}(x))]] \geq \E{\lambda_\phi^k \times \mu^k}[\E_{\hat{\sigma}B^{kj}}[f{\hat{B}^{kj}(x)}(x)] + T^k \H(\hat{B}^{kj}(x))] - \E_{\lambda_\phi^k}[\delta(k,j)]

Using the concavity of entropy and the property of \delta

\E_{\mu^k}[\E_{\lambda_\phi^k}[\E_{\hat{\sigma}{M_T}^{kj}}[f{\hat{M}T^{kj}(x)}(x)]] + T^k \H(\hat{M}T^{kj}(x))] \geq \E{\lambda\phi^k \times \mu^k}[\E_{\hat{\sigma}B^{kj}}[f{\hat{B}^{kj}(x)}(x)] + T^k \H(\hat{B}^{kj}(x))] - O(\phi(k)^{-\frac{1}{4}})

Applying Proposition B.1 we get the desired result.

Proof of Corollary 4

For each a \in \mathcal{A}^n define \hat{P}^{kj}a(k,x):=\hat{P}^{kj}(k,x,a) and u{\phi,T,a}^n(k,x):=u_{\phi,T}^{nk}(x,a,\hat{P}). It is easy to see \hat{P}a is an \mathcal{E}{2(ll,\phi)}^*(poly,rlog)-optimal predictor for u_{\phi,T,a}. Construct the (poly,rlog)-bischeme \hat{M}_T to satisfy the condition of Theorem 2 with \delta_r(k,j) \leq 2^{-j}. We have (with the help of Proposition B.4)

\E_{s_{G,\phi,T}^k(x,\hat{P})}[u^n] = \E_{\lambda_{\phi^n}^k}[\E_{\hat{\sigma}{M_T}^{kj}}[u{\phi,T,\hat{M}_T^{kj}(x)}^{nk}(x)]] \pm O(\phi^n(k)^{-1})

\H(s_{G,\phi,T}^{nk}(x,\hat{P})) = \H(\E_{\lambda_{\phi^n}^k}[\hat{M}_T^{kj}(x)]) \pm O(\phi^n(k)^{-\frac{1}{2}})

\E_{\hat{A}^k(x) \times s_{G,\phi,T}^{\bar{n}k}(x,\hat{P})}[u^n] = \E_{\hat{\sigma}A^{k}}[u{\phi,T,\hat{A}^{k}(x)}^{nk}(x)]

Applying Corollary 3 we get the desired result.

Proposition B.5

Consider a finite set \Sigma, \mathcal{R}=(\Sigma,f,\mu) a \phi-Hoelder reflective system and two collections of (poly,rlog)-predictors {\hat{Q}1^n}{n \in \Sigma} and {\hat{Q}2^n}{n \in \Sigma}. Assume that \forall n \in \Sigma: \hat{Q}1^n \underset{\mathcal{E}{2(ll)}^{\frac{1}{2}}}{\overset{\mu^n}{\simeq}} \hat{Q}_2^n. Then

\forall n \in \Sigma: \E_{\mu_n^k}[(\mathcal{R}[\hat{Q}_1]^n(x)-\mathcal{R}[\hat{Q}_1]^n(x))^2] = O(\phi^n(k)^{-\frac{1}{\infty}})

Proof of Proposition B.5

\E_{\mu^{nk}}[(\mathcal{R}[\hat{Q}1]^n(x)-\mathcal{R}[\hat{Q}1]^n(x))^2] = \E{\mu^{nk}}[(\E{\sigma_1}[f^n(x,\hat{Q}1[a])]-\E{\sigma_2}[f^n(x,\hat{Q}_2[a])])^2]

\E_{\mu^{nk}}[(\mathcal{R}[\hat{Q}_1]^n(x)-\mathcal{R}[\hat{Q}1]^n(x))^2] \leq E{\mu^{nk} \times \sigma_1 \times \sigma_2}[(f^n(x,\hat{Q}_1[a_1])-f^n(x,\hat{Q}_2[a_2]))^2]

\E_{\mu^{nk}}[(\mathcal{R}[\hat{Q}1]^n(x)-\mathcal{R}[\hat{Q}1]^n(x))^2] \leq \E{\sigma_1 \times \sigma_2}[c^{nk} \E{\rho^n}[\E_{\lambda_{\psi^{nm}}^k}[\E_{\mu^{mk} \times U^{r_1(k,j)} \times U^{r_2(k,j)}}[(Q_1^{mkj}(x,y,a_1)-Q_2^{mkj}(x,y,a_2))^2]]]^{\alpha^n}] + \delta^n(k)

\E_{\mu^{nk}}[(\mathcal{R}[\hat{Q}1]^n(x)-\mathcal{R}[\hat{Q}1]^n(x))^2] \leq c^{nk} \E{\rho^n}[\E{\lambda_{\psi^{nm}}^k}[\E_{\mu^{mk} \times U^{r_1(k,j)} \times U^{r_2(k,j)} \times \sigma_1 \times \sigma_2}[(Q_1^{mkj}(x,y,a_1)-Q_2^{mkj}(x,y,a_2))^2]]]^{\alpha^n} + \delta^n(k)

Using the similarity of \hat{Q}1 and \hat{Q}2 there are {\tilde{\delta}^n: \Nats^2 \rightarrow [0,1] \in \mathcal{E}{2(ll)}}{n \in \Sigma} s.t.

\E_{\mu^{nk}}[(\mathcal{R}[\hat{Q}1]^n(x)-\mathcal{R}[\hat{Q}1]^n(x))^2] \leq c^{nk} \E{\rho^n}[\E{\lambda_{\psi^{nm}}^k}[\tilde{\delta}^m(k,j)^{\frac{1}{2}}]]^{\alpha^n} + \delta^n(k)

\E_{\mu^{nk}}[(\mathcal{R}[\hat{Q}1]^n(x)-\mathcal{R}[\hat{Q}1]^n(x))^2] \leq c^{nk} \E{\rho^n}[\E{\lambda_{\psi^{nm}}^k}[\tilde{\delta}^m(k,j)]]^{\frac{\alpha^n}{2}} + \delta^n(k)

\E_{\mu^{nk}}[(\mathcal{R}[\hat{Q}_1]^n(x)-\mathcal{R}[\hat{Q}1]^n(x))^2] \leq O(\phi^n(k)^{\frac{\alpha^n}{2} - \epsilon^n}) \E{\rho^n}[O(\psi^{nm}(k)^{-1})]^{\frac{\alpha^n}{2}} + O(\phi^n(k)^{-\frac{1}{\infty}})

Using \psi^{nm} \geq \phi^n we get the desired result.

Proof of Theorem 3

Fix a finite set \Sigma and a collection {\phi_n \in \Phi}{n \in \Sigma}. Consider \mathcal{R} a \phi-Hoelder reflective system. By the general existence theorem, there is \hat{R} an \mathcal{E}{2(ll)}(poly,rlog)-optimal predictor system for \mathcal{R}. For each n \in \Sigma we can choose \hat{P}^n, an \mathcal{E}{2(ll)}(poly,log)-optimal predictor for \mathcal{R}[\hat{R}]^n. By the uniqueness theorem, we have \hat{P}^{n} \underset{\mathcal{E}{2(ll)}^\frac{1}{2}}{\overset{\mu^n}{\simeq}} \hat{R}^{n}. By Proposition B.5 this implies E_{\mu^{nk}}[(\mathcal{R}[\hat{P}]^n(x)-\mathcal{R}[\hat{R}]^n(x))^2] = O(\phi^n(k)^{-\frac{1}{\infty}}). This means \hat{P}^n is an \mathcal{E}{2(ll,\phi^n)}^*(poly,log)-optimal predictor for \mathcal{R}[\hat{P}]^n and \hat{P} is an \mathcal{E}{2(ll,\phi)}^*(poly,log)-optimal predictor system for \mathcal{R}.

Proposition B.6

Fix a finite set \Sigma and a collection {\phi_n \in \Phi}{n \in \Sigma}. Consider \mathcal{R} = (\Sigma, f, \mu) a reflective system. Assume there are {c^{nmk} \in \Reals^{>0}}{n,m \in \Sigma, k \in \Nats}, {\psi^{nm} \in \Phi}{n,m \in \Sigma}, {\alpha^n \in (0,1]}{n \in \Sigma} and {\delta^{nm}: \Nats \rightarrow \Reals^{\geq 0}}_{n,m \in \Sigma} s.t.

(i) \forall n,m \in \Sigma , \exists \epsilon^{nm} > 0: c^{nmk}=O(\phi^n(k)^{\frac{\alpha^n}{2} - \epsilon^{nm}})

(ii) \psi^{nm} \geq \phi^n

(iii) \delta^{nm}(k) = O(\phi^n(k)^{-\frac{1}{\infty}})

(iv) For any m \in \Sigma and \pi,\tilde{\pi} \in \Pi_\Sigma s.t. \forall l \in \Sigma \setminus m,k,j \in \Nats: \pi^{lkj}=\tilde{\pi}^{lkj} \E_{\mu^{nk}}[(f^n(x,\pi)-f^n(x,\tilde{\pi}))^2] \leq c^{nmk} \E_{\mu^{mk} \times \lambda_{\psi^{nm}}^k}[\E_{U(\pi)^{mkj} \times U(\tilde{\pi})^{mkj}}[(\pi^{mkj}(x,y)-\tilde{\pi}^{mkj}(x,y))^2]]^{\alpha^n} + \delta^{nm}(k)

Then, \mathcal{R} is \phi-Hoelder.

Proof of Proposition B.6

Identify \Sigma with {n \in \Nats \mid 1 \leq n \leq N} where N = #\Sigma. Consider any \pi,\tilde{\pi} \in \Pi_\Sigma. Define \pi_n recursively for all n \leq N by \pi_0 := \pi, \pi_{n+1}^{n+1,kj}:=\tilde{\pi}^{n+1,kj} and \forall m \in \Sigma \setminus {n+1}: \pi_{n+1}^{mkj}:=\pi_n^{mkj}. In particular, it follows that \pi_N = \tilde{\pi}. We have

\E_{\mu^{nk}}[(f^n(x,\pi_{m-1})-f^n(x,\pi_m))^2] \leq c^{nmk} \E_{\mu^{mk} \times \lambda_{\psi^{nm}}^k}[\E_{U(\pi)^{mkj} \times U(\tilde{\pi})^{mkj}}[(\pi^{mkj}(x,y)-\tilde{\pi}^{mkj}(x,y))^2]]^{\alpha^n} + \delta^{nm}(k)

\frac{1}{N} \sum_{m=1}^N \E_{\mu^{nk}}[(f^n(x,\pi_{m-1})-f^n(x,\pi_m))^2] \leq \frac{1}{N} \sum_{m=1}^N (c^{nmk} \E_{\mu^{mk} \times \lambda_{\psi^{nm}}^k}[\E_{U(\pi)^{mkj} \times U(\tilde{\pi})^{mkj}}[(\pi^{mkj}(x,y)-\tilde{\pi}^{mkj}(x,y))^2]]^{\alpha^n} + \delta^{nm}(k))

Denoting c^{nk}:=\max_{m \in \Sigma} c^{nmk}, \delta^n:=\frac{1}{N} \sum_{m=1}^N \delta^{nm} we get

\E_{\mu^{nk}}[(\frac{1}{N} \sum_{m=1}^N (f^n(x,\pi_{m-1})-f^n(x,\pi_m)))^2] \leq c^{nk} (\frac{1}{N} \sum_{m=1}^N \E_{\mu^{mk} \times \lambda_{\psi^{nm}}^k}[\E_{U(\pi)^{mkj} \times U(\tilde{\pi})^{mkj}}[(\pi^{mkj}(x,y)-\tilde{\pi}^{mkj}(x,y))^2]])^{\alpha^n} + \delta^n(k)

\E_{\mu^{nk}}[(f^n(x,\pi)-f^n(x,\tilde{\pi}))^2] \leq N^2 c^{nk} (\frac{1}{N} \sum_{m=1}^N \E_{\mu^{mk} \times \lambda_{\psi^{nm}}^k}[\E_{U(\pi)^{mkj} \times U(\tilde{\pi})^{mkj}}[(\pi^{mkj}(x,y)-\tilde{\pi}^{mkj}(x,y))^2]])^{\alpha^n} + N^2 \delta^n(k)

Proof of Theorem 4

Consider n,m \in \mathcal{P} and \pi,\tilde{\pi} \in \Pi_{\mathcal{P}} s.t. \forall l \in \mathcal{P} \setminus m,k,j \in \Nats: \pi^{lkj}=\tilde{\pi}^{lkj}.

\E_{\mu_G^{nk}}[(u_{\phi,T}^{nk}(x,a,\pi)-u_{\phi,T}^{nk}(x,a,\tilde{\pi}))^2] \leq \E_{\mu^k}[d_{TV}(s_{G,\phi,T}^{\bar{n}k}(x,\pi),s_{G,\phi,T}^{\bar{n}k}(x,\tilde{\pi}))^2]

\E_{\mu_G^{nk}}[(u_{\phi,T}^{nk}(x,a,\pi)-u_{\phi,T}^{nk}(x,a,\tilde{\pi}))^2] \leq \E_{\mu^k}[d_{TV}(s_{G,\phi,T}^{mk}(x,\pi),s_{G,\phi,T}^{mk}(x,\tilde{\pi}))^2]

\E_{\mu_G^{nk}}[(u_{\phi,T}^{nk}(x,a,\pi)-u_{\phi,T}^{nk}(x,a,\tilde{\pi}))^2] \leq \E_{\mu^k}[(\frac{1}{2} \sum_{b \in \mathcal{A}^m} \Abs{\Pr_{s_{G,\phi,T}^{mk}(x,\pi)}[b]-\Pr_{s_{G,\phi,T}^{mk}(x,\tilde{\pi})}[b]})^2]

Slightly abusing notation, define s_{G,\phi,T}^m: \Nats^2 \times \Supp \mu \times \Words \times \Pi_{\mathcal{P}} \rightarrow \Delta_G^m by

\Pr_{s_{G,\phi,T}^{mkj}(x,y,\pi)}[a]:=Z_{G,\phi,T}^{mkj}(x,y,\pi)^{-1} 2^{(T^{mk})^{-1}\pi^{mkj}((k,x,a),y)}

We have

s_{G,\phi,T}^{mk}(x,\pi) = \E_{\lambda_\phi^k}[\E_{U(\pi)^{mkj}}[s_{G,\phi,T}^{mkj}(x,y,\pi)]]

\E_{\mu_G^{nk}}[(u_{\phi,T}^{nk}(x,a,\pi)-u_{\phi,T}^{nk}(x,a,\tilde{\pi}))^2] \leq \E_{\mu^k}[(\frac{1}{2} \sum_{b \in \mathcal{A}^m} \Abs{\E_{\lambda_\phi^k}[\E_{U(\pi)^{mkj}}[\Pr_{s_{G,\phi,T}^{mkj}(x,y,\pi)}[b]]-\E_{U(\tilde{\pi})^{mkj}}[\Pr_{s_{G,\phi,T}^{mkj}(x,y,\tilde{\pi})}[b]]]})^2]

\E_{\mu_G^{nk}}[(u_{\phi,T}^{nk}(x,a,\pi)-u_{\phi,T}^{nk}(x,a,\tilde{\pi}))^2] \leq \E_{\mu^k}[\E_{\lambda_\phi^k}[\E_{U(\pi)^{mkj} \times U(\tilde{\pi})^{mkj}}[d_{TV}(s_{G,\phi,T}^{mkj}(x,y,\pi),s_{G,\phi,T}^{mkj}(x,y,\tilde{\pi}))]]^2]

\E_{\mu_G^{nk}}[(u_{\phi,T}^{nk}(x,a,\pi)-u_{\phi,T}^{nk}(x,a,\tilde{\pi}))^2] \leq \E_{\mu^k \times \lambda_\phi^k}[\E_{U(\pi)^{mkj} \times U(\tilde{\pi})^{mkj}}[d_{TV}(s_{G,\phi,T}^{mkj}(x,y,\pi),s_{G,\phi,T}^{mkj}(x,y,\tilde{\pi}))^2]]

Using Pinsker’s inequality

\E_{\mu_G^{nk}}[(u_{\phi,T}^{nk}(x,a,\pi)-u_{\phi,T}^{nk}(x,a,\tilde{\pi}))^2] \leq \frac{1}{2} \E_{\mu^k \times \lambda_\phi^k}[\E_{U(\pi)^{mkj} \times U(\tilde{\pi})^{mkj}}[\KL{s_{G,\phi,T}^{mkj}(x,y,\pi)}{s_{G,\phi,T}^{mkj}(x,y,\tilde{\pi})}]]

Using Proposition B.3

\E_{\mu_G^{nk}}[(u_{\phi,T}^{nk}(x,a,\pi)-u_{\phi,T}^{nk}(x,a,\tilde{\pi}))^2] \leq \frac{1}{2} (T^{mk})^{-1} \E_{\mu^k \times \lambda_\phi^k}[\E_{U(\pi)^{mkj} \times U(\tilde{\pi})^{mkj}}[\sum_{b \in \mathcal{A}^m}\Abs{\pi^{mkj}((k,x,b),y)-\tilde{\pi}^{mkj}((k,x,b),y)}]]

\E_{\mu_G^{nk}}[(u_{\phi,T}^{nk}(x,a,\pi)-u_{\phi,T}^{nk}(x,a,\tilde{\pi}))^2] \leq \frac{1}{2} #\mathcal{A}^m (T^{mk})^{-1} \E_{\mu_G^{mk} \times \lambda_\phi^k}[\E_{U(\pi)^{mkj} \times U(\tilde{\pi})^{mkj}}[\Abs{\pi^{mkj}((k,x,b),y)-\tilde{\pi}^{mkj}((k,x,b),y)}]]

\E_{\mu_G^{nk}}[(u_{\phi,T}^{nk}(x,a,\pi)-u_{\phi,T}^{nk}(x,a,\tilde{\pi}))^2] \leq \frac{1}{2} #\mathcal{A}^m (T^{mk})^{-1} \E_{\mu_G^{mk} \times \lambda_\phi^k}[\E_{U(\pi)^{mkj} \times U(\tilde{\pi})^{mkj}}[(\pi^{mkj}((k,x,b),y)-\tilde{\pi}^{mkj}((k,x,b),y))^2]]^{\frac{1}{2}}

Applying Proposition B.6 we get the desired result.