Intelligent Agent Foundations Forumsign up / log in
On the computational feasibility of forecasting using gamblers
discussion post by Vadim Kosoy 92 days ago | discuss

This is an informal note about an idea which I consider important, but which I’m not planning to start working on immediately (first I want to develop the theory of delegation some more in the realizable setting). Putting it up here as a reminder, a point to bear in mind, and in case someone else wants to pick it up.

Forecasting using gamblers (a.k.a. logical induction generalized outside of logic, a.k.a. dominant forecasting)* can be regarded as a generalization of Bayesian inference, however it seem qualitatively less computationally tractable than Bayesian inference. Bayesian inference for a modest number of efficiently computable hypotheses (i.e. hypotheses that allow computing the conditional probability distribution of the next observation efficiently; this is a stronger requirement than efficient samplability) is efficiently computable. On the other hand, computing a dominant forecaster seems intractable even for a modest number of efficiently computable gamblers, since it amounts to finding a fixed point which is a problem that is often \(\mathrm{PPAD}\)-equivalent.

However, it occurred to me that there is a fairly large class of gamblers for which the problem is tractable, in particular it probably includes gamblers for incomplete models. A gambler is a continuous function \(G: {\Delta{\mathcal{O}}^\omega}\rightarrow {C({\mathcal{O}}^\omega)}\) (we will ignore dependence on past forecasts since it is immaterial for our purpose). For now, pretend that \({\Delta{\mathcal{O}}^\omega}\) is a finite dimensional space (indeed, when \({\mathcal{O}}\) is finite, the simplest way to get a computable approximation is truncating the space to finite dimension via replacing \({\mathcal{O}}^\omega\) by \({\mathcal{O}}^n\); nevertheless it would be nice to get the functional analysis right later). Then, \({C({\mathcal{O}}^\omega)}\) is its cotangent space and therefore \(G\) is a covector field = section of the cotangent bundle = differential form of rank 1. It is thus natural to consider the special case when \(G\) is exact i.e. equal to the differential of some function \(g: {\Delta{\mathcal{O}}^\omega}\rightarrow \mathbb{R}\). For convenience, we will take a minus sign, i.e. \(G = -{\operatorname{d}}g\). Moreover, we can consider the further special case when \(g\) is convex. The resulting class of gamblers is closed under linear combinations, so dominating a countable set of “convex gamblers” reduces to dominating a single convex gambler.

For convex differentiable \(g\), \(G = -{\operatorname{d}}g\) and any \(\mu \in {\Delta{\mathcal{O}}^\omega}\) and \(x \in {\mathcal{O}}^\omega\), we have

\[G(\mu,x) - {\operatorname{E}}_{\mu}[G(\mu)] = {\operatorname{E}}_{\mu}[{\operatorname{d}}g(\mu)] - {\operatorname{E}}_{\delta_x}[{\operatorname{d}}g(\mu)] \leq g(\mu) - g(\delta_x)\]

It follows that for any \(\mu^* \in \arg\min g\)

\[\operatorname{supp} \mu^* \subseteq \arg\max G(\mu^*)\]

Thus, we reduced the problem to convex optimization which is well-studied and tractable! Specifically for an incomplete model \(\Phi\), the associated function \(g\) is something like a convex function of the Kantorovich-Rubinstein distance from \(\Phi\), except that KR distance is not differentiable. This should be possible to remedy either by “smoothing” the KR distance or by considering subgradients and multivalued gamblers**.

*We need a better name for this. “Logical induction” sounds specific to formal logic, and “dominant forecasting” is too generic. My ideas so far are “mercantile forecasting” and “Dutch forecasting”. Also, we might want a special name for the incomplete models version as opposed to the fully general gamblers version.

**More generally, it seems possible to incorporate multivalued gamblers into the formalism e.g. using Lassonde’s fixed point theorem.



NEW LINKS

NEW POSTS

NEW DISCUSSION POSTS

RECENT COMMENTS

What does the Law of Logical
by Alex Appel on Smoking Lesion Steelman III: Revenge of the Tickle... | 0 likes

To quote the straw vulcan:
by Stuart Armstrong on Hyperreal Brouwer | 0 likes

I intend to cross-post often.
by Scott Garrabrant on Should I post technical ideas here or on LessWrong... | 1 like

I think technical research
by Vadim Kosoy on Should I post technical ideas here or on LessWrong... | 2 likes

I am much more likely to miss
by Abram Demski on Should I post technical ideas here or on LessWrong... | 1 like

Note that the problem with
by Vadim Kosoy on Open Problems Regarding Counterfactuals: An Introd... | 0 likes

Typos on page 5: *
by Vadim Kosoy on Open Problems Regarding Counterfactuals: An Introd... | 0 likes

Ah, you're right. So gain
by Abram Demski on Smoking Lesion Steelman | 0 likes

> Do you have ideas for how
by Jessica Taylor on Autopoietic systems and difficulty of AGI alignmen... | 0 likes

I think I understand what
by Wei Dai on Autopoietic systems and difficulty of AGI alignmen... | 0 likes

>You don’t have to solve
by Wei Dai on Autopoietic systems and difficulty of AGI alignmen... | 0 likes

Your confusion is because you
by Vadim Kosoy on Delegative Inverse Reinforcement Learning | 0 likes

My confusion is the
by Tom Everitt on Delegative Inverse Reinforcement Learning | 0 likes

> First of all, it seems to
by Abram Demski on Smoking Lesion Steelman | 0 likes

> figure out what my values
by Vladimir Slepnev on Autopoietic systems and difficulty of AGI alignmen... | 0 likes

RSS

Privacy & Terms