Formalizing Newcombian Problems with Fuzzy Infra-Bayesianism

2mo

Introduction

In this post, we introduce contributions and supracontributions^[1], which are basic objects from infra-Bayesianism that go beyond the crisp case (the case of credal sets). We then define supra-POMDPs, a generalization of partially observable Markov decision processes (POMDPs). This generalization has state transition dynamics that are described by supracontributions.

We use supra-POMDPs to formalize various Newcombian problems in the context of learning theory where an agent repeatedly encounters the problem. The one-shot version of these problems are well-known to highlight flaws with classical decision theories.^[2] In particular, we discuss the opaque, transparent, and epsilon-noisy versions of Newcomb's problem, XOR blackmail, and counterfactual mugging.

We conclude by stating a theorem that describes when optimality for the... (read 6373 more words →)

Proof Section to Formalizing Newcombian Problems with Fuzzy Infra-Bayesianism

Brittany Gelb

2mo

This proof section accompanies Formalizing Newcombian problems with fuzzy infra-Bayesianism. We prove the following result.

Theorem [Alexander Appel (@Diffractor), Vanessa Kosoy (@Vanessa Kosoy)]:
Let $ν : Π_{H} \times O^{< H} \to Δ O$ be a Newcombian problem of horizon $H \in N$ that satisfies pseudocausality. Let $M_{ν} = (S, Θ_{0}, A, O, T, B)$ denote the associated supra-POMDP with infinite time horizon and time discount $γ \in [0, 1) .$ Then
$lim γ \to 1 | min π \in Π E_{M_{ν}^{π}} [L^{γ}] - min π \in Π E_{ν^{π}} [L^{γ}] | = 0.$
Furthermore, if ${π_{γ}}_{γ \in [0, 1)}$ is a family of policies such that ${lim}_{γ \to 1} E_{M_{ν}^{π_{γ}}} [L^{γ}] - {min}_{π \in Π} E_{M_{ν}^{π}} [L^{γ}] = 0,$ then
$lim γ \to 1 E_{ν^{π_{γ}}} [L^{γ}] - min π \in Π E_{ν^{π}} [L^{γ}] = 0.$

Proof: Let $λ$ denote the empty history. Given a supracontribution $Θ$ , let $max (Θ)$ denote the set of maximal extreme points of $Θ .$ First we remark that for any supra-POMDP, without loss of generality, a set of copolicies $Ξ$ can always be replaced by

{τ \in Ξ | τ (λ) \in max (Θ_{0}), \forall h \neq λ \in (S \times A)^{*}, τ (h) \in max (T (s, a))} .

Given an episode policy $π \in Π_{H},$ let $τ_{π}$ denote the episode copolicy that initializes the state to $(π, λ),$ i.e. $τ_{π} (λ) = δ_{π \times λ} .$ Let $τ_{π}^{π} \in Δ (A \times O)^{H}$ denote the distribution over outcomes determined by the interaction of $π$ and $τ_{π} .$ Note that the expected loss with respect to $τ_{π}^{π}$ is equal to the expected... (read 586 more words →)

Proof Section to Crisp Supra-Decision Processes

Brittany Gelb

5mo

This post accompanies Crisp Supra-Decision Processes and contains the proof of the following proposition.

Proposition 1 [Alexander Appel (@Diffractor), Vanessa Kosoy (@Vanessa Kosoy)]: Let $M = (S, s_{0}, A, O, T, B, L, γ)$ be a crisp supra-MDP with geometric time discount such that $S$ and $A$ are finite. Then there exists a stationary optimal policy.

Proof: We first recall some notation. Let $A$ denote the set of actions, and let $S$ denote the set of states. Let $(A \times S)^{*}$ denote the set of histories and $(A \times S)^{n} \subset (A \times S)^{*}$ denote the set of histories of length $n$ . For $h \in (A \times S)^{*}$ , let $h (A \times S)^{ω}$ denote the set of destinies with prefix $h .$

Throughout, we assume that $L^{γ} : (A \times S)^{ω} \to [0, 1]$ is the sum of the momentary losses at each time-step with geometric time discount $γ \in [0, 1) .$ More specifically, given $d \in (A \times S)^{ω},$ we write $d = a_{0} \prod_{t = 1}^{\infty} s_{t} a_{t} .$ Then $L^{γ} (d)$ is given by $L^{γ} (d) = (1 - γ) \sum_{t = 0}^{\infty} γ^{t} L (s_{t}, a_{t}) .$

Fix $n \in N .$ Recall that $(A \times S)^{ω}$ can be written as the finite disjoint union

(A \times S)^{ω} = \prod h \in (A \times S)^{n} h (A \times S)^{ω} .

This fact, together with Fubini's theorem, implies... (read 651 more words →)

Crisp Supra-Decision Processes

Brittany Gelb

5mo

Introduction

In this post, we describe a generalization of Markov decision processes (MDPs) and partially observable Markov decision processes (POMDPs) called crisp supra-MDPs and supra-POMDPs. The new feature of these decision processes is that the stochastic transition dynamics are multivalued, i.e. specified by credal sets. We describe how supra-MDPs give rise to crisp causal laws, the hypotheses of infra-Bayesian reinforcement learning. Furthermore, we discuss how supra-MDPs can approximate MDPs by a coarsening of the state space. This coarsening allows an agent to be agnostic about the detailed dynamics while still having performance guarantees for the full MDP.

Analogously to the classical theory, we describe an algorithm to compute a Markov optimal policy for supra-MDPs... (read 5045 more words →)

An Introduction to Credal Sets and Infra-Bayes Learnability

Brittany Gelb

6mo

Introduction

Credal sets, a special case of infradistributions^[1] in infra-Bayesianism and classical objects in imprecise probability theory, provide a means of describing uncertainty without assigning exact probabilities to events as in Bayesianism. This is significant because as argued in the introduction to this sequence, Bayesianism is inadequate as a framework for AI alignment research. We will focus on credal sets rather than general infradistributions for simplicity of the exposition.

Defining Credal Sets

Recall that the total-variation metric is one example of a metric on $Δ X,$ the set of probability distributions over a finite set $X .$ A set is closed with respect to a metric if it contains all of its limit points with respect to the metric. For example, let $X_{0} = {0, 1} .$ The... (read 3668 more words →)

Proof Section to an Introduction to Credal Sets and Infra-Bayes Learnability

Brittany Gelb

6mo

This post accompanies An Introduction to Credal Sets and Infra-Bayes Learnability.

Notation

We use $Δ X$ to denote the space of probability distributions over a set $X$ , which is assumed throughout to be a compact metric space. We use $□ X$ to denote the set of credal sets over $X .$

Given $f : X \to R$ and $m \in Δ X$ , let $m (f) := E_{m} [f] .$

Let $C (X, Y)$ denote the space of continuous functions from $X$ to $Y .$

Proof of Lemma 1

Lemma 1: If $A$ and $O$ are finite, the set of countably infinite histories $(A \times O)^{ω}$ is a compact metric space under the metric $d (h, h^{'}) = γ^{t (h, h^{'})}$ where $γ \in (0, 1)$ and $t (h, h^{'})$ is the time of first difference between $h$ and $h^{'} .$

Proof. The space $A \times O$ is compact under the discrete topology since it is finite. Therefore, $(A \times O)^{ω}$ is compact under the product topology $P$ by Tychonoff's theorem. The stated metric induces a topology $M$ . By the definition of compactness, it is sufficient to show that all basis elements of $M$ are... (read 2932 more words →)

Proof Section to an Introduction to Reinforcement Learning for Understanding Infra-Bayesianism

Brittany Gelb

9mo

Introduction

This post accompanies An Introduction to Reinforcement Learning for Understanding Infra-Bayesianism. The goal of this introduction is to provide a high-level overview of the proofs contained in this post.

The proof of Proposition 1 is achieved through three lemmas. I believe the most insightful part of the proof is the use of the “epsilon over three” trick that lets us break the proof down into these lemmas. The first lemma uses the concept of the product topology on the space of policies, and I found this very useful for understanding better what convergence in the product topology on the space of policies actually means. The text Topology by James Munkres is a standard... (read 2536 more words →)

An Introduction to Reinforcement Learning for Understanding Infra-Bayesianism

Brittany Gelb

9mo

Introduction

The goal of this post is to give a summary of classical reinforcement learning theory that primes the reader to learn about infra-Bayesianism, which is a new framework for reinforcement learning that aims to solve problems related to AI alignment. We will concentrate on basic aspects of the classical theory that have analogous concepts in infra-Bayesianism, and explain these concepts using infra-Bayesianism conventions. The more technical proofs are contained in the proof section.

For the first part of this sequence and for links to other writings, see What is Inadequate about Bayesianism for AI Alignment: Motivating Infra-Bayesianism.

One special case of reinforcement learning is the case of stochastic bandits. For example, a bird may... (read 5780 more words →)

What is Inadequate about Bayesianism for AI Alignment: Motivating Infra-Bayesianism

Brittany Gelb

10mo

Introduction

Infra-Bayesianism is a mathematical framework for studying artificial learning and intelligence that developed from Vanessa Kosoy’s Learning Theoretic AI Alignment Research Agenda. As applied to reinforcement learning, the main character of infra-Bayesianism is an agent that is learning about an unknown environment and making decisions in pursuit of some goal. Infra-Bayesianism provides novel ways to model this agent’s beliefs and make decisions, which address problems arising when an agent does not or cannot consider the true environment possible at the beginning of the learning process. This setting, a non-realizable environment, is relevant to various scenarios important to AI alignment, including scenarios when agents may consider themselves as part of the environment, and... (read 2050 more words →)

LESSWRONG
LW

LESSWRONG
LW

Brittany Gelb

What is Inadequate about Bayesianism for AI Alignment: Motivating Infra-Bayesianism

Crisp Supra-Decision Processes

An Introduction to Credal Sets and Infra-Bayes Learnability

An Introduction to Reinforcement Learning for Understanding Infra-Bayesianism

Brittany Gelb

Formalizing Newcombian Problems with Fuzzy Infra-Bayesianism

Proof Section to Formalizing Newcombian Problems with Fuzzy Infra-Bayesianism

Proof Section to Crisp Supra-Decision Processes

Crisp Supra-Decision Processes

An Introduction to Credal Sets and Infra-Bayes Learnability

Proof Section to an Introduction to Credal Sets and Infra-Bayes Learnability

Proof Section to an Introduction to Reinforcement Learning for Understanding Infra-Bayesianism

FUNDAMENTALS OF INFRA-BAYESIANISM

Brittany Gelb

What is Inadequate about Bayesianism for AI Alignment: Motivating Infra-Bayesianism

Crisp Supra-Decision Processes

An Introduction to Credal Sets and Infra-Bayes Learnability

An Introduction to Reinforcement Learning for Understanding Infra-Bayesianism

Brittany Gelb

Formalizing Newcombian Problems with Fuzzy Infra-Bayesianism

Proof Section to Formalizing Newcombian Problems with Fuzzy Infra-Bayesianism

Proof Section to Crisp Supra-Decision Processes

Crisp Supra-Decision Processes

An Introduction to Credal Sets and Infra-Bayes Learnability

Proof Section to an Introduction to Credal Sets and Infra-Bayes Learnability

Proof Section to an Introduction to Reinforcement Learning for Understanding Infra-Bayesianism

FUNDAMENTALS OF INFRA-BAYESIANISM

Introduction

Introduction

Introduction

Defining Credal Sets

Notation

Proof of Lemma 1

Introduction

Introduction

Introduction