Intelligent Agent Foundations Forumsign up / log in
1.IRL is hard
post by Vadim Kosoy 31 days ago | 6 comments

We show that assuming the existence of public-key cryptography, there is an environment in which Inverse Reinforcement Learning is computationally intractable, even though the “teacher” agent, the environment and the utility functions are computable in polynomial-time and there is only 1 bit of information to learn.

continue reading »
2.Stabilizing logical counterfactuals by pseudorandomization
post by Vadim Kosoy 241 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.

continue reading »
3.Logical counterfactuals for random algorithms
post by Vadim Kosoy 282 days ago | Abram Demski, Nate Soares and Patrick LaVictoire like this | discuss

Updateless decision theory was informally defined by Wei Dai in terms of logical conditional expected utility, where the condition corresponds to an algorithm (the agent) producing a given output (action or policy). This kind of conditional expected values can be formalised by optimal predictors. However, since optimal predictor systems which are required to apply optimal predictors to decision theory generally have random advice, we need counterfactuals well-defined for random algorithms i.e. algorithms that produce different outputs with different probabilities depending on internal coin tosses. We propose to define these counterfactuals by a generalization of the notion of conditional expected utility which amounts to linear regression of utility with respect to the probabilities of different outputs in the space of “impossible possible worlds.” We formalise this idea by introducing “relative optimal predictors,” prove the analogue of the conditional probability formula (which takes matrix form) and uniqueness theorems.

Motivation

We start by explaining the analogous construction in classical probability theory and proceed to defining the logical counterpart in the Results section.

Consider \(\zeta\) a probability measure on some space, a random variable \(u\) representing utility, a finite set \(\mathcal{A}\) representing possible actions and another random variable \(p\) taking values in \([0,1]^{\mathcal{A}}\) and satisfying \(\sum_{a \in \mathcal{A}} p_a = 1\) representing the probabilities of taking different actions. For a deterministic algorithm, \(p\) takes values \(\{0,1\}^{\mathcal{A}}\) allowing defining conditional expected utility as

\[u_a := \operatorname{E}_\zeta[u \mid p_a = 1] = \frac{\operatorname{E}_\zeta[u p_a]}{\operatorname{E}_\zeta[p_a]}\]

In the general case, it is tempting to consider

\[\operatorname{E}_{\zeta \ltimes p}[u \mid a] = \frac{\operatorname{E}_\zeta[u p_a]}{\operatorname{E}_\zeta[p_a]}\]

where \(\zeta \ltimes p\) stands for the semidirect product of \(\zeta\) with \(p\), the latter regarded as a Markov kernel with target \(\mathcal{A}\). However, this would lead to behavior similar to EDT since conditioning by \(a\) is meaningful even for a single “world” (i.e. completely deterministic \(u\) and \(p\)). Instead, we select \(u^* \in {\mathbb{R}}^{\mathcal{A}}\) that minimizes \(\operatorname{E}_\zeta[(u - p^t u^*)^2]\) (we regard elements of \({\mathbb{R}}^{\mathcal{A}}\) as column vectors so \(p^t\) is a row vector). This means \(u^*\) has to satisfy the matrix equation

\[\operatorname{E}_\zeta[p p^t] u^* = \operatorname{E}_\zeta[u p]\]

The solution to this equation is only unique when \(\operatorname{E}_\zeta[p p^t]\) is non-degenerate. This corresponds to requiring positive probability of the condition for usual conditional expected values. In case \(p\) takes values in \(\{0,1\}^{\mathcal{A}}\), \(u^*\) is the usual conditional expected value.

Preliminaries

continue reading »
4.Implementing CDT with optimal predictor systems
post by Vadim Kosoy 299 days ago | Patrick LaVictoire likes this | 2 comments

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 \(\operatorname{E}_s[u]\) replaced by “free utility” \(\operatorname{E}_s[u]+T \operatorname{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.

continue reading »
5.Reflection with optimal predictors
post by Vadim Kosoy 323 days ago | Patrick LaVictoire likes this | discuss

A change in terminology: It is convenient when important concepts have short names. The concept of an “optimal predictor scheme” seems much more important than its historical predecessor, the “optimal predictor”. Therefore “optimal predictor schemes” will be henceforth called just “optimal predictors” while the previous concept of “optimal predictor” might be called “flat optimal predictor”.

We study systems of computations which have access to optimal predictors for each other. We expect such systems to play an important role in decision theory (where self-prediction is required to define logical counterfactuals and mutual prediction is required for a collection of agents in a game) and Vingean reflection (where the different computations correspond to different successor agents). The previously known existence theorems for optimal predictors are not directly applicable to this case. To overcome this we prove new, specifically tailored existence theorems.

The Results section states the main novelties, Appendix A contains adaptations of old theorems, Appendix B proves selected claims from Appendix A and Appendix C proves the novel results.

Results

continue reading »
6.Superrationality in arbitrary games
discussion post by Vadim Kosoy 345 days ago | Jessica Taylor, Nate Soares, Patrick LaVictoire, Scott Garrabrant and Stuart Armstrong like this | 5 comments
7.Bounded Solomonoff induction using optimal predictor schemes
post by Vadim Kosoy 339 days ago | Patrick LaVictoire likes this | discuss

Most of the content of this post was covered by the talk I gave in Los Angeles MIRIx in October, minus the proofs and a minor amendment of Theorem 1 (the role of \(\Delta_{sqp,\phi}^2\)).

We define variants of the concept of generatable distributional estimation problem and show that these variants also admits a uniformly universal optimal predictor scheme. We show how to use this to implement a form of bounded Solomonoff induction.

Results

We have previously defined a “word ensemble” to be a collection \(\{\mu^k\}_{k \in {\mathbb{N}}}\) of probability measures on \({{\{ 0, 1 \}^*}}\) s.t. for some polynomial \(p\), \(\operatorname{supp}\mu^k \subseteq {{\{ 0, 1 \}^{\leq{p(k)}}}}\). This was convenient when the formalism was based on Boolean circuits but unnecessary for Turing machines. It is enough to assume that the Turing machine is allowed to read only the beginning of the input and thus halt in time arbitrarily smaller than the length of the input. In the following we will use “word ensemble” to mean an arbitrary sequence of probability measures on \({{\{ 0, 1 \}^*}}\), allow such word ensembles in distributional estimation problems etc.

All proofs are in the Appendix.

We start by defining “\(\Delta(log)\)-sampler” and “\(\Delta(log)\)-generator” for \(\Delta\) an error space of rank 2 (they were previously defined for an error space of rank 1). Fix such an error space.

continue reading »
8.Logical counterfactuals using optimal predictor schemes
discussion post by Vadim Kosoy 376 days ago | discuss
9.Stability of optimal predictor schemes under a broader class of reductions
discussion post by Vadim Kosoy 376 days ago | discuss
10.Improved error space for universal optimal predictor schemes
discussion post by Vadim Kosoy 380 days ago | discuss
11.Towards reflection with relative optimal predictor schemes
post by Vadim Kosoy 380 days ago | Jessica Taylor likes this | discuss

We construct a family or oracles relative to which all estimation problems which have approximate solutions in exponential time are generatable. Relatively to these oracles, we can use the optimal predictor scheme \(\Lambda\) for assigning expectation values to arbitrary deterministic computations within time that is superquasipolynomial in the logarithm of the computation time. In particular, this should allow reflection in the sense of Garrabrant once we succeed to derandomize \(\Lambda\) relative to the same oracle.

Results

continue reading »
12.Optimal predictor schemes pass a Benford test
post by Vadim Kosoy 411 days ago | Jessica Taylor, Patrick LaVictoire and Scott Garrabrant like this | discuss

We formulate a concept analogous to Garrabrant’s irreducible pattern in the complexity theoretic language underlying optimal predictor schemes and prove a formal relation to Garrabant’s original definition. We prove that optimal predictor schemes pass the corresponding version of the Benford test (namely, on irreducible patterns they are \(\Delta\)-similar to a constant).

Results

All the proofs are given in the appendix.

continue reading »
13.Optimal predictors for global probability measures
post by Vadim Kosoy 422 days ago | discuss

There are two commonly used formalisms in average case complexity theory: problems with a single global probability measure on parameter space or problems with a family of such probability measures. Previous posts about optimal predictors focused on the family approach. In this post we give the formalism for global measures.

Results

continue reading »
14.Predictor schemes with logarithmic advice
post by Vadim Kosoy 438 days ago | Nate Soares likes this | 2 comments

We introduce a variant of optimal predictor schemes where optimality holds within the space of random algorithms with logarithmic advice. These objects are also guaranteed to exist for the error space \(\Delta_{avg}^2\). We introduce the class of generatable problems and construct a uniform universal predictor scheme for this class which is optimal in the new sense with respect to the \(\Delta^2_{avg}\) error space. This is achieved by a construction similar to Levin’s universal search.

Results

continue reading »
15.Optimal predictor schemes
post by Vadim Kosoy 453 days ago | Jim Babcock and Jessica Taylor like this | 2 comments

I introduce the concept of “optimal predictor scheme” which differs from (quasi)optimal predictors in depending on an additional parameter representing the amount of computing resources the predictor is allowed to use. For a certain flavor of optimal predictor scheme, I prove existence for arbitrary distributional decision problems.

Results

It is convenient to think of the concepts of “optimal predictor” and “quasi-optimal predictor” as special cases of the more general \(\Delta\)-optimal predictors corresponding to different choices of the “error space” \(\Delta\).

continue reading »
16.Quasi-optimal predictors
post by Vadim Kosoy 467 days ago | Nate Soares and Patrick LaVictoire like this | 2 comments

In this post I define the concept of quasi-optimal predictors which is a weaker variant on the theme of optimal predictors. I explain the properties of quasi-optimal predictors that I currently understand (which are completely parallel to the properties of optimal predictors) and give an example where there is a quasi-optimal predictor but there is no optimal predictor.

All proofs are given in the appendix and are mostly analogous to proofs of corresponding theorems for optimal predictors.

continue reading »
17.Optimal predictors and propositional calculus
discussion post by Vadim Kosoy 468 days ago | discuss
18.Optimal predictors and conditional probability
link by Vadim Kosoy 472 days ago | Jessica Taylor and Patrick LaVictoire like this | 3 comments
19.A complexity theoretic approach to logical uncertainty (Draft)
link by Vadim Kosoy 522 days ago | Benja Fallenstein, Daniel Dewey, Jessica Taylor, Nate Soares and Patrick LaVictoire like this | 2 comments
20.Identity and quining in UDT
link by Vadim Kosoy 575 days ago | Benja Fallenstein and Patrick LaVictoire like this | 5 comments

NEW LINKS

NEW POSTS

NEW DISCUSSION POSTS

RECENT COMMENTS

Can you provide links to the
by Vadim Kosoy on Two Questions about Solomonoff Induction | 0 likes

And I just wanted to write a
by Vadim Kosoy on Online Learning 1: Bias-detecting online learners | 0 likes

Also see the notion of
by Paul Christiano on Online Learning 1: Bias-detecting online learners | 2 likes

Given that this is my first
by Ryan Carey on Online Learning 1: Bias-detecting online learners | 1 like

I initially played around
by Devi Borg on Logical Inductors that trust their limits | 2 likes

I still feel like I don't
by Devi Borg on Logical Inductors that trust their limits | 2 likes

Running the traders on some r
by Sune Kristian Jakobsen on Variations of the Garrabrant-inductor | 0 likes

1. Note that IRL is
by Jessica Taylor on Heroin model: AI "manipulates" "unmanipulatable" r... | 0 likes

Stuart did make it easier for
by Patrick LaVictoire on (C)IRL is not solely a learning process | 0 likes

Nicely done. I should have
by Sam Eisenstat on The set of Logical Inductors is not Convex | 1 like

Ok, I think we need to
by Stuart Armstrong on Heroin model: AI "manipulates" "unmanipulatable" r... | 0 likes

I strongly predict that if
by Jessica Taylor on Heroin model: AI "manipulates" "unmanipulatable" r... | 0 likes

Wireheading the human is the
by Stuart Armstrong on Heroin model: AI "manipulates" "unmanipulatable" r... | 0 likes

Re 1: There are cases where
by Jessica Taylor on Heroin model: AI "manipulates" "unmanipulatable" r... | 0 likes

1. I don't really see the
by Stuart Armstrong on Heroin model: AI "manipulates" "unmanipulatable" r... | 0 likes

RSS

Privacy & Terms (NEW 04/01/15)