Stabilizing logical counterfactuals by pseudorandomization
post by Vadim Kosoy 732 days ago | Abram Demski likes this | 2 comments

Previously, we discussed the construction of logical counterfactuals in the language of optimal predictors. These counterfactuals were found to be well-behaved when a certain non-degeneracy condition is met which can be understood as a bound on the agent’s ability to predict itself. We also demonstrated that desired game-theoretic behavior seems to require randomization (thermalizing instead of maximizing) which has to be logical randomization to implement metathreat game theory by logical counterfactuals. Both of these considerations suggest that the agent has to pseudorandomize (randomize in the logical uncertainty sense) its own behavior. Here, we show how to implement this pseudorandomization and prove it indeed guarantees the non-degeneracy condition.

Results

The proofs of the results are given in Appendix A.

Motivation

Fix $$n \in {\mathbb{N}}$$. Denote $$\mathcal{A} := \{a \in {\mathbb{N}}\mid a < n\}$$. Suppose $$\{q_a \in [0,1]\}_{a \in \mathcal{A}}$$ is a probability distribution on $$\mathcal{A}$$, i.e. $$\sum_{a \in \mathcal{A}} q_a = 1$$. We want to construct a procedure that samples $$\mathcal{A}$$ according to the probabilities $$q$$.

Suppose we are given $$h$$, a uniformly distributed $$[0,1]^\mathcal{A}$$-valued random variable. Then we can select $$s(q,h) \in \mathcal{A}$$ by

$s(q,h):=\min \{a \in \mathcal{A} \mid \frac{q_a}{\sum_{b = a}^{n-1} q_b} \geq h_a\}$

It is easy to see that $$s(q,h)$$ implements the desired sampling i.e. $$\operatorname{Pr}[s(q,h) = a] = q_a$$.

In order to translate the above into logical uncertainty, we need a source of pseudorandom that can be the counterpart of $$h$$. The following definition establishes the desiderata of this object.

Definition

Fix an error space $$\mathcal{E}$$ and $$d: {\mathbb{N}}\rightarrow {\mathbb{R}}^{\geq 0}$$. Consider $$n \in {\mathbb{N}}$$, $$\nu$$ a probability measure on $$[0,1]^n$$, $$\mu$$ a word ensemble and $$h: \operatorname{supp}\mu \rightarrow [0,1]^n$$. $$(\mu,h)$$ is said to be $$\nu$$-distributed $$\mathcal{E}(poly,log)$$-pseudorandom within precision $$d$$ when for any $$\{0,1\}$$-valued $$(poly,log)$$-bischeme $$\hat{S}$$, uniformly bounded family of functions $$\{f^k: [0,1]^n \rightarrow {\mathbb{R}}\}_{k \in {\mathbb{N}}}$$ and sequence $$\{L^k \in {\mathbb{R}}^{>0}\}_{k \in {\mathbb{N}}}$$ s.t. $$f^k$$ is Lipschitz continuous with constant $$L^k$$, there is $$\delta \in \mathcal{E}$$ s.t.

${\lvert \operatorname{E}_{\mu \times U^{r_S}}[\hat{S}(f \circ h -\operatorname{E}_\nu[f]) \rvert} \leq \delta + L d$

Note

Compare the above to the previously given definition of an “irreducible” estimation problem.

We now give a basic existence result for pseudorandom functions by establishing that a random function is pseudorandom.

Construction

Consider $$t: {\mathbb{N}}\rightarrow {\mathbb{N}}$$ and $$\alpha: {\mathbb{N}}\rightarrow {\mathbb{R}}^{\geq 0}$$. $$\mathcal{E}_{2(t,\alpha)}$$ is defined to be the set of bounded functions $$\delta: {\mathbb{N}}^2 \rightarrow {\mathbb{R}}^{\geq 0}$$ s.t.

$\exists \epsilon > 0 \, \forall m \in {\mathbb{N}}: \text{for almost all } k \in {\mathbb{N}}: \forall j < (t^k)^m: \epsilon \delta^{kj} \leq \alpha^k$

Proposition 1

Consider $$t: {\mathbb{N}}\rightarrow {\mathbb{N}}$$ and $$\alpha: {\mathbb{N}}\rightarrow {\mathbb{R}}^{\geq 0}$$. If exists $$m \in {\mathbb{N}}$$ s.t. $$\alpha^k = \Omega(2^{-k^m})$$ then $$\mathcal{E}_{2(t,\alpha)}$$ is an error space. If exists $$m \in {\mathbb{N}}$$ s.t. $$\alpha^k = \Omega(k^{-m})$$ then $$\mathcal{E}_{2(t,\alpha)}$$ is an ample error space.

Proposition 2

For any $$\phi \in \Phi$$, $$\mathcal{E}_{2(t_\phi,\frac{1}{\phi})} \subseteq \mathcal{E}_{2(ll,\phi)}$$.

Theorem 1

For any $$n \in {\mathbb{N}}$$ there is $$M_n > 0$$ s.t. the following holds. Consider $$\nu$$ a probability measure on $$[0,1]^n$$ and $$\mu$$ a word ensemble. Let $$h^*: \operatorname{supp}\mu \rightarrow [0,1]^n$$ be generated by independently sampling $$\nu$$ for each $$x \in \operatorname{supp}\mu$$. Suppose $$t: {\mathbb{N}}\rightarrow {\mathbb{N}}$$, $$\alpha: {\mathbb{N}}\rightarrow {\mathbb{R}}^{\geq 0}$$ and $$d: {\mathbb{N}}\rightarrow {\mathbb{R}}^{\geq 0}$$ are s.t. $$t^k \geq k$$ and

$\forall m \in {\mathbb{N}}: {\lim_{k \rightarrow \infty}} (t^k)^m (d^k)^{-n} \exp(-\frac{1}{2}\frac{(d^k)^{2n} (\alpha^k)^2}{\sum_{x \in {{\{ 0, 1 \}^*}}} \mu^k(x)^2}) = 0$

Then $$(\mu,h^*)$$ is $$\nu$$-distributed $$\mathcal{E}_{2(t,\alpha)}(poly,log)$$-pseudorandom within precision $$M_n d$$ with probability 1.

Finally, we show pseudorandomization guarantees non-degeneracy.

Notation

Given measurable space $$X$$ and $$Y$$, $$f: X \xrightarrow{mk} Y$$ will denote a Markov kernel with source $$X$$ and target $$Y$$. For each $$x \in X$$, $$f(x)$$ will refer to the corresponding $$Y$$-valued random variable.

Theorem 2

Fix $$n \in {\mathbb{N}}$$. Consider $$\mathcal{E}$$ an error space, $$d: {\mathbb{N}}\rightarrow {\mathbb{R}}^{\geq 0}$$, $$\mu$$ a word ensemble, $$q: \operatorname{supp}\mu \xrightarrow{mk} [0,1]^n$$, $$\zeta: {\mathbb{N}}\rightarrow (0,\frac{1}{n}]$$ and $$h: \operatorname{supp}\mu \rightarrow [0,1]^n$$. Suppose that for any $$x \in \operatorname{supp}\mu^k$$, $$\sum_{a = 0}^{n-1} q_a(x) = 1$$ and $$\forall a < n: q_a(x) \geq \zeta^k$$ with probability 1 and that $$(\mu,h)$$ is uniform $$\mathcal{E}(poly,log)$$-pseudorandom within precision $$d$$. Define $$p: \operatorname{supp}\mu \rightarrow [0,1]^n$$ by

$p_a(x):=\operatorname{Pr}[a = \min \{b < n \mid \frac{q_b(x)}{\sum_{c = b}^{n-1} q_c(x)} \geq h_b(x)\}]$

Assume $$\hat{P}$$ is a symmetric $$\mathcal{E}(poly,rlog)$$-orthogonal predictor for $$(\mu,pp^t)$$. Let $$\hat{\xi}$$ be the lowest eigenvalue of $$\hat{P}$$. Then there is $$\delta \in \mathcal{E}$$ s.t.

$\operatorname{E}_{\mu \times \hat{\sigma}_P}[\theta(\frac{\zeta^n}{n(n+1)} - \hat{\xi}) \cdot (\frac{\zeta^n}{n(n+1)} - \hat{\xi})] \leq \delta + \zeta^{-1} d$

Corollary

In the setting of Theorem 2, assume $$\zeta^{-1} d \in \mathcal{E}$$. Then there is $$\hat{Q}$$ a symmetric $$\mathcal{E}(poly,rlog)$$-optimal predictor for $$(\mu,pp^t)$$ s.t. its lowest eigenvalue is at least $$\frac{\zeta^n}{n(n+1)}$$.

Appendix A

Proposition 1 and 2 are obvious and we skip the proofs.

Construction A

Given $$r > 0$$, let $$H(r)$$ be the set of functions $$\omega: [0,1]^n \rightarrow [-1,+1]$$ given by $$\omega(z)=\cos(\pi \vartheta^t z)$$ or $$\omega(z)=\sin(\pi \vartheta^t z)$$ for $$\vartheta \in {\mathbb{Z}}^n$$, $${\lVert \vartheta \rVert} \leq r$$.

Proof of Theorem 1

Consider any continuous function $$\omega: [0,1]^n \rightarrow [-1,+1]$$. For any $$k \in {\mathbb{N}}$$ and $$S: \operatorname{supp}\mu^k \xrightarrow{mk} [0,1]$$, we have

$\operatorname{E}_{\mu^k \ltimes S}[S(x)(\omega(h^*(x)) -\operatorname{E}_\nu[\omega])] = \sum_{x \in {{\{ 0, 1 \}^*}}} \mu^k(x) \operatorname{E}[S(x)](\omega(h^*(x)) -\operatorname{E}_\nu[\omega])$

Denote $$\eta$$ the probability measure from which $$h^*$$ is sampled. That is, $$\eta$$ is the completion of $$\prod_{x \in \operatorname{supp}\mu} \nu$$. Denote $$\lambda(x):=\mu^k(x) \operatorname{E}[S(x)]\omega(h^*(x))$$.

$\operatorname{E}_{\mu^k \ltimes S}[S(x)(\omega(h^*(x)) -\operatorname{E}_\nu[\omega])] = \sum_{x \in {{\{ 0, 1 \}^*}}} \lambda(x) -\operatorname{E}_\eta[\sum_{x \in {{\{ 0, 1 \}^*}}} \lambda(x)]$

By Hoeffding’s inequality,

$\operatorname{Pr}_\eta[{\lvert \sum_{x \in {{\{ 0, 1 \}^*}}} \lambda(x) -\operatorname{E}_\eta[\sum_{x \in {{\{ 0, 1 \}^*}}} \lambda(x)] \rvert} \geq (d^k)^n\alpha^k] \leq 2 \exp(-\frac{2(d^k)^{2n}(\alpha^k)^2}{\sum_{x \in {{\{ 0, 1 \}^*}}}(2 \mu^k(x))^2})$

$\operatorname{Pr}_\eta[{\lvert \operatorname{E}_{\mu^k \ltimes S}[S(x)(\omega(h^*(x)) -\operatorname{E}_\nu[\omega])] \rvert} \geq (d^k)^n\alpha^k] \leq 2 \exp(-\frac{1}{2}\frac{(d^k)^{2n}(\alpha^k)^2}{\sum_{x \in {{\{ 0, 1 \}^*}}}\mu^k(x)^2})$

For some $$M_1 > 0$$ we have $$\#H(r) \leq M_1 r^n$$. Denote $$H^k := H((d^k)^{-1})$$. For any $$j \geq 1$$ we have

$\operatorname{Pr}_\eta[\exists \omega \in H^k, s \in {{\{ 0, 1 \}^{{\lfloor \log j \rfloor}}}}: {\lvert \operatorname{E}_{\mu^k \times U^j}[\beta(ev(s;x,y))(\omega(h^*(x)) -\operatorname{E}_\nu[\omega])] \rvert} \geq (d^k)^n\alpha^k] \leq 2 M_1 (d^k)^{-n} j \exp(-\frac{1}{2}\frac{(d^k)^{2n}(\alpha^k)^2}{\sum_{x \in {{\{ 0, 1 \}^*}}}\mu^k(x)^2})$

For any $$m \in {\mathbb{N}}$$, we know that

$\sum_{k=0}^\infty (t^k)^m (d^k)^{-n} \exp(-\frac{1}{2}\frac{(d^k)^{2n} (\alpha^k)^2}{\sum_{x \in {{\{ 0, 1 \}^*}}} \mu^k(x)^2}) < \infty$

It follows that with $$\eta$$-probability 1

$\forall m \in {\mathbb{N}}: \text{for almost all } k \in {\mathbb{N}}: \forall \omega \in H^k, s \in {{\{ 0, 1 \}^{{\lfloor m \log t^k \rfloor}}}}: {\lvert \operatorname{E}_{\mu^k \times U^{(t^k)^m}}[\beta(ev(s;x,y))(\omega(h^*(x)) -\operatorname{E}_\nu[\omega])] \rvert} < (d^k)^n\alpha^k$

This implies that for any $$\{0,1\}$$-valued $$(poly,log)$$-bischeme $$\hat{S}$$

$\forall m \in {\mathbb{N}}: \text{for almost all } k \in {\mathbb{N}}: \forall \omega \in H^k, j < (t^k)^m: {\lvert \operatorname{E}_{\mu^k \times U^{r_S(k,j)}}[\hat{S}^{kj}(x)(\omega(h^*(x)) -\operatorname{E}_\nu[\omega])] \rvert} < (d^k)^n\alpha^k$

Consider a uniformly bounded family of functions $$\{f^k: [0,1]^n \rightarrow {\mathbb{R}}\}_{k \in {\mathbb{N}}}$$ and sequence $$\{L^k \in {\mathbb{R}}^{>0}\}_{k \in {\mathbb{N}}}$$ s.t. $$f^k$$ is Lipschitz continuous with constant $$L^k$$. By Corollary B (see Appendix B) there are $$M_{2n}, M_{3n} > 0$$, $$\{g^k: [0,1]^n \rightarrow {\mathbb{R}}\}_{k \in {\mathbb{N}}}$$ and $$\{c_\omega^k \in {\mathbb{R}}\}_{k \in {\mathbb{N}}, \omega \in H^k}$$ s.t. $${\lvert g^k \rvert} \leq \frac{1}{2} M_{2n} L^k d^k$$, $${\lvert c_\omega^k \rvert} < M_{3n} \sup {\lvert f \rvert}$$ and $$f^k = \sum_{\omega \in H^k} c_\omega^k \omega + g^k$$.

$\operatorname{E}_{\mu^k \times U^{r_S(k,j)}}[\hat{S}^{kj}(x)(f^k(h^*(x)) -\operatorname{E}_\nu[f^k])] = \sum_{\omega \in H^k} c_\omega^k \operatorname{E}_{\mu^k \times U^{r_S(k,j)}}[\hat{S}^{kj}(x)(\omega(h^*(x)) -\operatorname{E}_\nu[\omega])] + \operatorname{E}_{\mu^k \times U^{r_S(k,j)}}[\hat{S}^{kj}(x)(g^k(h^*(x)) -\operatorname{E}_\nu[g^k])]$

${\lvert \operatorname{E}_{\mu^k \times U^{r_S(k,j)}}[\hat{S}^{kj}(x)(f^k(h^*(x)) -\operatorname{E}_\nu[f^k])] \rvert} \leq M_{3n} \sup {\lvert f \rvert} \sum_{\omega \in H^k} {\lvert \operatorname{E}_{\mu^k \times U^{r_S(k,j)}}[\hat{S}^{kj}(x)(\omega(h^*(x)) -\operatorname{E}_\nu[\omega])] \rvert} + M_{2n} L^k d^k$

$\forall m \in {\mathbb{N}}: \text{for almost all } k \in {\mathbb{N}}: j < (t^k)^m: {\lvert \operatorname{E}_{\mu^k \times U^{r_S(k,j)}}[\hat{S}^{kj}(x)(f^k(h^*(x)) -\operatorname{E}_\nu[f^k])] \rvert} < M_1 M_{3n} \sup {\lvert f \rvert} \alpha^k + M_{2n} L^k d^k$

Proposition A.1

Fix an error space $$\mathcal{E}$$ and $$d: {\mathbb{N}}\rightarrow {\mathbb{R}}^{\geq 0}$$. Consider $$n \in {\mathbb{N}}$$, $$\nu$$ a probability measure on $$[0,1]^n$$, $$\mu$$ a word ensemble and $$h: \operatorname{supp}\mu \rightarrow [0,1]^n$$. Assume $$(\mu, h)$$ is $$\nu$$-distributed $$\mathcal{E}(poly,log)$$-pseudorandom within precision $$d$$. Then, for any $$\{0,1\}$$-valued $$(poly,rlog)$$-bischeme $$\hat{S}$$, uniformly bounded family of functions $$\{f^k: [0,1]^n \rightarrow {\mathbb{R}}\}_{k \in {\mathbb{N}}}$$ and sequence $$\{L^k \in {\mathbb{R}}^{>0}\}_{k \in {\mathbb{N}}}$$ s.t. $$f^k$$ is Lipschitz continuous with constant $$L^k$$, there is $$\delta \in \mathcal{E}$$ s.t.

${\lvert \operatorname{E}_{\mu \times \hat{\sigma}_S}[\hat{S}(f \circ h -\operatorname{E}_\nu[f]) \rvert} \leq \delta + L d$

Proof of Proposition A.1

The definition of pseudorandom implies for any $$f$$ and $$L$$ as above there is an $$\mathcal{E}$$-moderate function $$\delta: {\mathbb{N}}^4 \rightarrow {\mathbb{R}}^{\geq 0}$$ s.t. for any $$k,j,s \in {\mathbb{N}}$$, $$A: {{\{ 0, 1 \}^*}}^2 \xrightarrow{alg} \{0,1\}$$

${\lvert \operatorname{E}_{\mu \times U^s}[A(x,y) (f^k(h(x)) - \operatorname{E}_\nu[f^k]) \rvert} \leq \delta(k,j,T_A^\mu(k,s),2^{{\lvert A \rvert}}) + L^k d^k$

This easily implies the desired result.

Proof of Theorem 2

Since it is possible to find a lowest eigenvector of a symmetric matrix in time polynomial in the number of significant digits, there is a $${\mathbb{Q}}^n$$-valued $$(poly,rlog)$$-bischeme $$\hat{u}$$ s.t. $${\lVert (\hat{P} - \hat{\xi}) \hat{u} \rVert} \leq \delta_1$$ and $$1 \leq \hat{u}^t \hat{u} \leq 1 + \delta_1$$ for $$\delta_1 \in \mathcal{E}$$. For any bounded $${\mathbb{Q}}$$-valued $$(poly,rlog)$$-bischeme $$\hat{S}$$ with $$\hat{\sigma}_S = \hat{\sigma}_P \times \tau$$ we have

${\lvert \operatorname{E}_{\mu \times \hat{\sigma_P} \times \tau}[\hat{S} \hat{u}^t (\hat{P} - pp^t) \hat{u}] \rvert} \in \mathcal{E}$

$\tilde{\delta}_S := {\lvert \operatorname{E}_{\mu \times \hat{\sigma_P} \times \tau}[\hat{S} (\hat{\xi} - (\hat{u}^t p)^2)] \rvert} \in \mathcal{E}$

Denote $$\mathcal{A} := \{a \in {\mathbb{N}}\mid a < n\}$$. Let $$\hat{m}$$ be an $$\mathcal{A}$$-valued $$(poly,rlog)$$-bischeme s.t. $${\lvert \hat{u}_m \rvert} = \max_{a \in \mathcal{A}} {\lvert \hat{u}_a \rvert}$$. We have $${\lvert \hat{u}_m \rvert} \geq \frac{1}{\sqrt{n}}$$ and in particular if $$x \in \operatorname{supp}\mu$$ is s.t. $$p_m(x)=1$$ then $$(\hat{u}^t(x) p(x))^2 \geq \frac{1}{n}$$.

For any $$k \in {\mathbb{N}}$$, $$a \in \mathcal{A}$$, denote $$\varsigma_a^k:=\frac{\zeta^k}{1 - a \zeta^k}$$, $$\varpi_a^k:=\frac{1 - (n-1) \zeta^k}{1 - a \zeta^k}$$. Define $$f_a^k: [0,1]^n \rightarrow [0,1]$$ by

$f_a^k(z):=\min(\theta(1-\frac{z_a}{\varsigma_a^k}) \cdot (1-\frac{z_a}{\varsigma_a^k}), \min_{b < a}(\theta(\frac{z_b-\varpi_b^k}{1-\varpi_b^k}) \cdot \frac{z_b-\varpi_b^k}{1-\varpi_b^k}))$

$$f_a^k$$ is Lipschitz continuous with constant $$L_a^k := \max(\frac{1}{\varsigma_a^k}, \max_{b < a} \frac{1}{1-\varpi_a^k}) \leq (\zeta^k)^{-1}$$.

$$f_a^k$$ only depends on the first $$a + 1$$ variables. As a function of these variables, its graph is a pyramid of height 1 whose base is the box $$\prod_{b < a} [\varpi_b^k,1] \times [0,\varsigma_a^k]$$. It follows that $$\int_{[0,1]^n} f_a^k(z) dz = \frac{1}{a+2}(\prod_{b < a} (1 - \varpi_b^k)) \varsigma_a^k \geq \frac{(\zeta^k)^{a+1}}{a+2} \geq \frac{(\zeta^k)^n}{n+1}$$.

For any $$\{0,1\}$$-valued $$(poly,rlog)$$-bischeme $$\hat{S}$$ we can apply Proposition A.1 to get $$\delta_S \in \mathcal{E}$$ s.t.

${\lvert \operatorname{E}_{\mu \times \hat{\sigma}_S}[\hat{S} (f_a \circ h - \int_{[0,1]^n} f_a(z) dz)] \rvert} \leq \delta_S + \zeta^{-1} d$

We have $$f_m \circ h = \sum_{a \in \mathcal{A}} \delta_{ma} f_a \circ h$$. Assuming $$\hat{\sigma}_S = \hat{\sigma_P} \times \tau$$, we get $$\delta'_S \in \mathcal{E}$$ s.t.

${\lvert \operatorname{E}_{\mu \times \hat{\sigma_P} \times \tau}[\hat{S} (f_m \circ h - \int_{[0,1]^n} f_m(z) dz)] \rvert} \leq \delta'_S + n \zeta^{-1} d$

It is easy to see that for any for any $$x \in \operatorname{supp}\mu^k$$, if $$h_a(x) \in \operatorname{supp}f_a^k(x)$$ then $$p_a(x) = 1$$. Hence $$(\hat{u}^t p)^2 \geq \frac{1}{n} f_m \circ h$$. We conclude

$\operatorname{E}_{\mu \times \hat{\sigma_P} \times \tau}[\hat{S} (\frac{1}{n} f_m \circ h - \hat{\xi})] \leq \tilde{\delta}_S$

$\operatorname{E}_{\mu \times \hat{\sigma_P} \times \tau}[\hat{S} (\frac{1}{n} \int_{[0,1]^n} f_m(z) dz - \hat{\xi})] \leq \tilde{\delta}_S + \delta'_S + \zeta^{-1} d$

$\operatorname{E}_{\mu \times \hat{\sigma_P} \times \tau}[\hat{S} (\frac{\zeta^n}{n(n+1)} - \hat{\xi})] \leq \tilde{\delta}_S + \delta'_S + \zeta^{-1} d$

Since $$\hat{\xi}$$ can be approximated by a $$(poly,rlog)$$-bischeme up to an error in $$\mathcal{E}$$, there is $$\delta \in \mathcal{E}$$ s.t.

$\operatorname{E}_{\mu \times \hat{\sigma_P}}[\theta(\frac{\zeta^n}{n(n+1)} - \hat{\xi}) \cdot (\frac{\zeta^n}{n(n+1)} - \hat{\xi})] \leq \delta + \zeta^{-1} d$

Proposition A.2

Fix an error space $$\mathcal{E}$$. Consider a distributional estimation problem $$(\mu, f)$$ and a corresponding $$\mathcal{E}$$-orthogonal predictor $$\hat{P}$$. Suppose $$\hat{Q}$$ is a bounded $${\mathbb{Q}}$$-valued $$(poly,rlog)$$-bischeme s.t. $$\hat{\sigma}_Q = \hat{\sigma}_P$$ (denote $$\hat{\sigma}$$) and $$\operatorname{E}_{\mu \times \hat{\sigma}}[{\lvert P - Q \rvert}] \in \mathcal{E}$$. Then $$\hat{Q}$$ is an $$\mathcal{E}$$-optimal predictor for $$(\mu, f)$$.

Proof of Proposition A.2

Consider a bounded $${\mathbb{Q}}$$-valued $$(poly,log)$$-bischeme $$\hat{S}$$ with $$\hat{\sigma}_S = \hat{\sigma} \times \tau$$. We have

$\operatorname{E}_{\mu \times \hat{\sigma} \times \tau}[\hat{S} (\hat{Q} - f)] = \operatorname{E}_{\mu \times \hat{\sigma} \times \tau}[\hat{S} (\hat{Q} - \hat{P} + \hat{P} - f)]$

${\lvert \operatorname{E}_{\mu \times \hat{\sigma} \times \tau}[\hat{S} (\hat{Q} - f)] \rvert} \leq {\lvert \operatorname{E}_{\mu \times \hat{\sigma} \times \tau}[\hat{S} (\hat{Q} - \hat{P})] \rvert} + {\lvert \operatorname{E}_{\mu \times \hat{\sigma} \times \tau}[\hat{S} (\hat{P} - \hat{f})] \rvert}$

${\lvert \operatorname{E}_{\mu \times \hat{\sigma}}[\hat{S} (\hat{Q} - f)] \rvert} \leq \sup {\lvert \hat{S} \rvert} \operatorname{E}_{\mu \times \hat{\sigma}}[{\lvert \hat{Q} - \hat{P} \rvert}] + {\lvert \operatorname{E}_{\mu \times \hat{\sigma} \times \tau}[\hat{S} (\hat{P} - \hat{f})] \rvert}$

Proof of Corollary

Given a field $$F$$, let $$\operatorname{Sym}^2(F^n)$$ be the space of $$n \times n$$ symmetric matrices over $$F$$. Given $$x \in {\mathbb{R}}$$, denote $$\tau_x: \operatorname{Sym}^2({\mathbb{R}}^n) \rightarrow \operatorname{Sym}^2({\mathbb{R}}^n)$$ the following function. Given $$M \in \operatorname{Sym}^2({\mathbb{R}}^n)$$, let $$\{e_i\}_{i < n}$$ be an orthonormal basis of eigenvectors for $$M$$ and $$\{\lambda_i\}_{i < n}$$ be the corresponding eigenvalues. Then, $$\tau_x(M) := \sum_{i < n} \max(\lambda_i, x) e_i e_i^t$$. As easy to see, the definition doesn’t depend on the choice of $$e$$.

Denote $$\rho := \frac{\zeta^n}{n(n+1)}$$. Let $$\hat{Q}$$ be a $$\operatorname{Sym}^2({\mathbb{Q}}^n)$$-valued $$(poly,rlog)$$-bischeme with $$\hat{\sigma}_Q = \hat{\sigma}_P$$ whose lowest eigenvalue is at least $$\rho$$ and which satisfies $${\lvert \hat{Q}_{ab} - \tau_\rho(\hat{P})_{ab} \rvert} \in \mathcal{E}$$. Using Theorem 2 and $$\zeta^{-1} d \in \mathcal{E}$$ we conclude that

$\operatorname{E}_{\mu \times \hat{\sigma}_P}[{\lvert \hat{P}_{ab} - \tau_\rho(\hat{P})_{ab} \rvert}] \in \mathcal{E}$

$\operatorname{E}_{\mu \times \hat{\sigma}_P}[{\lvert \hat{P}_{ab} - \hat{Q}_{ab} \rvert}] \in \mathcal{E}$

Applying Proposition A.2 we get the desired result.

Appendix B

Cartwright and Kucharski give a generalization of Jackson’s inequality for an arbitrary compact connected Lie group. We only need the uniform norm, rank 1 case for the standard torus, so we state here this special case.

Theorem B

Fix $$n \in {\mathbb{N}}$$. Denote $$T^n := {\mathbb{R}}^n / {\mathbb{Z}}^n$$ the standard n-dimensional torus. Then there is $$M_n >0$$ s.t. for any $$r > 0$$ there is $$K_r \in C^\infty(T^n, {\mathbb{R}})$$ s.t. its Fourier transform satisfies $$\operatorname{supp}\hat{K}_r \subseteq \{\vartheta \in {\mathbb{Z}}^n \mid {\lVert \vartheta \rVert} \leq r\}$$ and for any $$f \in C(T^n, {\mathbb{C}})$$ we have

$\sup {\lvert f - K_r * f \rvert} \leq M_n \sup_{d(z,w) \leq \frac{1}{r}} {\lvert f(z) - f(w) \rvert}$

Moreover, the $$\hat{K}_r$$ are uniformly bounded.

Note B

The fact $$\hat{K}_r$$ are uniformly bounded is not stated explicitly in Cartwright and Kucharski but it is evident from their construction of $$K$$.

Corollary B

For any $$n \in {\mathbb{N}}$$ there are $$M_{1n}, M_{2n} > 0$$ s.t. the following holds. Consider $$r > 0$$ and $$f:[0,1]^n \rightarrow {\mathbb{R}}$$, Lipschitz continuous with constant $$L$$. Then there are $$g \in C([0,1]^n, {\mathbb{R}})$$ and $$\{c_\omega \in {\mathbb{R}}\}_{\omega \in H(r)}$$ s.t. $${\lvert g \rvert} \leq M_{1n} \frac{L}{r}$$, $${\lvert c_\omega \rvert} < M_{2n} \sup {\lvert f \rvert}$$ and $$f = \sum_{\omega \in H(r)} c_\omega \omega + g$$.

Proof of Corollary B

Using reflections, $$f$$ can be continued to a function on $$[0,2]^n$$ with periodic boundary conditions which is still Lipschitz continuous with constant $$L$$. This new function can be reinterpreted as a function $$f' \in C(T^n, {\mathbb{R}})$$ Lipschitz continuous with constant $$2L$$. Applying Theorem B, $$f' = K_r * f' + g'$$ where $${\lvert g' \rvert} \leq 2M_n \frac{L}{r}$$. Using the properties of $$K_r$$, we have $$(K_r * f')(z) = \sum_{{\lVert \vartheta \rVert} \leq r} c_{\vartheta} \exp(2 \pi i \vartheta^t z)$$, where $${\lvert c_\vartheta \rvert} \leq M'_n \sup {\lvert f \rvert}$$ for some $$M'_n > 0$$ because the $$\hat{K}_r$$ are uniformly bounded and $${\lvert \hat{f}' \rvert}$$ can be bounded by $$\int_{T^n} {\lvert f'(z) \rvert} dz \leq \sup {\lvert f' \rvert}$$. Since $$f$$ is real, $$c_\vartheta = \bar{c}_{-\vartheta}$$, yielding the desired result.

 by Paul Christiano 730 days ago | Vadim Kosoy likes this | link Intuitively, this is very similar to previous approaches to salvaging decision theory (e.g. see mine here, but the whole thing is basically the same as playing chicken with the universe, which just corresponds to using a very low temperature). I am still not able (/ don’t have the time) to closely follow these proofs or even the result statements. It looks to me like your goal is to formalize the basic intuitive arguments, and that the construction works by a similar diagonalization. If that’s not the case, it may be worth calling out the differences explicitly. reply
 by Vadim Kosoy 727 days ago | link Yeah, what I’m doing here is more or less a formalisation of the ideas in your writeup, with the added technical complication that the “math intuition model” is nondeterministic so you need to use matrix counterfactuals. In order to get UDTish instead of CDTish behavior, I am going to make the agent select some sort of “logical policy” instead of action (i.e. something that reduces to a metathreat in a game theoretic setting). reply

NEW DISCUSSION POSTS

[Delegative Reinforcement
 by Vadim Kosoy on Stable Pointers to Value II: Environmental Goals | 1 like

Intermediate update: The
 by Alex Appel on Further Progress on a Bayesian Version of Logical ... | 0 likes

Since Briggs [1] shows that
 by 258 on In memoryless Cartesian environments, every UDT po... | 2 likes

This doesn't quite work. The
 by Nisan Stiennon on Logical counterfactuals and differential privacy | 0 likes

I at first didn't understand
 by Sam Eisenstat on An Untrollable Mathematician | 1 like

This is somewhat related to
 by Vadim Kosoy on The set of Logical Inductors is not Convex | 0 likes

This uses logical inductors
 by Abram Demski on The set of Logical Inductors is not Convex | 0 likes

Nice writeup. Is one-boxing
 by Tom Everitt on Smoking Lesion Steelman II | 0 likes

Hi Alex! The definition of
 by Vadim Kosoy on Delegative Inverse Reinforcement Learning | 0 likes

A summary that might be
 by Alex Appel on Delegative Inverse Reinforcement Learning | 1 like

I don't believe that
 by Alex Appel on Delegative Inverse Reinforcement Learning | 0 likes

This is exactly the sort of
 by Stuart Armstrong on Being legible to other agents by committing to usi... | 0 likes

When considering an embedder
 by Jack Gallagher on Where does ADT Go Wrong? | 0 likes

The differences between this
 by Abram Demski on Policy Selection Solves Most Problems | 1 like

Looking "at the very
 by Abram Demski on Policy Selection Solves Most Problems | 0 likes