Contents

• POMDP
• Rewards
• The reward learning posterior
• The reward learning prior A putative new idea for AI control; index here.

Along with Jan Leike and Laurent Orseau, I’ve been working to formalise many of the issues with AIs learning human values.

I’ll be presenting part of this at NIPS and the whole of it at some later conference. Therefore it seems best to formulate the whole problem in the reinforcement learning formalism. The results can generally be easily reformulated for general systems (including expected utility).

POMDP

A partially observable Markov decision process without reward function (POMDP\R), \mu = (\mathcal{S}, \mathcal{A}, \mathcal{O}, T, O, T_0) consists of:

• a finite set of states \mathcal{S},

• a finite set of actions \mathcal{A},

• a finite set of observations \mathcal{O},

• a transition probability distribution T: \mathcal{S} \times \mathcal{A} \to \Delta\mathcal{S},

• a probability distribution T_0 \in \Delta \mathcal{S} over the initial state s_0.

• an observation probability distribution O: \mathcal{S} \to \Delta\mathcal{O}.

The agent interacts with the environment in cycles: in time step t, the environment is in state s_{t-1} \in \mathcal{S} and the agent chooses an action a_t \in \mathcal{A}. Subsequently the environment transitions to a new state s_t \in \mathcal{S} drawn from the distribution T(s_t \mid s_{t-1}, a_t) and the agent then receives an observation o_t \in \mathcal{O} drawn from the distribution O(o_t \mid s_t). The underlying states s_{t-1} and s_t are not directly observed by the agent.

An observed history h_t = a_1 o_1 a_2 o_2 \ldots a_t o_t is a sequence of actions and observations. We denote the set of all observed histories of length t with \mathcal{H}_t := (\mathcal{A} \times \mathcal{O})^t.

For a given horizon m, call \mathcal{H}m the set of full histories; then \mathcal{H}{<m}=\bigcup_{t<m} \mathcal{H}t is the set of partial histories. For t'>t, let a{t:t'} be the sequence of actions a_{t}a_{t+1}\ldots a_{t'}, let o_{t:t'} be the sequence of observations o_{t}o_{t+1}\ldots o_{t'}, and let s_{t:t'} the sequence of states s_{t} s_{t+1}\ldots s_{t'}.

The set \Pi is the set of policies, functions \pi: (\mathcal{A} \times \mathcal{O})^* \to \Delta\mathcal{A} mapping histories to probability distributions over actions. Given a policy \pi and environment \mu, we get a probability distribution over histories:

• \mu(a_1 o_1 \ldots a_t o_t \mid \pi) := \sum_{s_{0:t} \in \mathcal{S}^t} T_0(s_0)\prod_{k=1}^t O(o_k \mid s_k) T(s_k \mid s_{k-1}, a_k) \pi(a_k \mid a_1 o_1 \ldots a_{k-1} o_k).

The expectation with respect to the distributions \mu and \pi is denoted \mathbb{E}^\pi_\mu.

Rewards

Rewards in this case can be seen as functions R: \mathcal{O} \to \mathbb{R} from observations to real numbers.

The agent’s goal is to maximize total reward \sum_{t=1}^m R(o_t) up to the horizon m. We assume that \mathcal{S} and \mathcal{A} are known to the agent. The reward function R is unknown, but there is a finite set of candidate reward functions, \mathcal{R}. The agent has to learn a reward function in the process of interacting with the environment.

The reward learning posterior

There are a variety of algorithms that act as reward function learning processes. It might be the cooperative learning algorithm, or some interactive question and answers sessions, or simply learning from observation of human behaviour/​human generated data. In all cases, at the end of m turns, the agent will have an estimate of the probability of the various reward functions.

Thus a universal definition of the process of reward learning is given by a posterior P: \mathcal{H}_m \to \Delta \mathcal{R}, mapping histories to distributions over possible rewards. This posterior is equivalent with the definition of the algorithm.

Now, anything that gives a distribution over \mathcal{H}_m can therefore give a distribution over \mathcal{R}.

This allows the construction a value function for any policy \pi corresponding to the reward learning posterior:

• V^\pi_P(h_t):= \mathbb{E}^\pi_\mu\big[\sum_{R \in\mathcal{R}} P(R \mid h_m) \sum_{k=1}^m R(o_k)\big| h_t \big].

The reward learning prior

Some reward learning algorithms (though not all) will also have a reward learning prior \widehat{P} over \mathcal{R}. Given a partial history h_t \in\mathcal{H}_t with t\leq m, this gives the agent’s current estimate as to what the final distribution over \mathcal{R} will be: \widehat{P}(\cdot \mid h_t).

For consistency, when t=m, set \widehat{P}(\cdot\mid h_m)=P(\cdot\mid h_m) (so that when all the history is in, the prior is the posterior).

This prior is often used in practice to estimate the value function V^\pi_P(h_t).