Outline

I develop some contents—previously introduced in the Value Learning sequence by Rohin Shah—more formally, to clarify the distinction between agents with and without a goal. Then I present related work and make some considerations on the relation between safety and goal-directedness. The appendix contains some details on the used formalism and can be skipped without losing much information.

A brief preliminary

In the first post of the Value Learning sequence, Shah compares two agents that exhibit the same behaviour (a winning strategy) when playing Tic-Tac-Toe, but are different in their design: one applies the minimax algorithm to the setting and rules of the game, while the other one follows a lookup table—you can think of its code as a long sequence of if-else statements.

Shah highlights the difference in terms of generalisation: the first one would still win if the winning conditions were changed, while the lookup table would not. Generalisation is one of the components of goal-directedness, and lookup tables are among the least goal-directed agent designs.

Here I want to point at another difference that exists between agents with and without a goal, based on the concept of algorithmic complexity.

Setup

Most problems in AI consist in finding a function $π \in A^{O}$ , called policy in some contexts, where $A = {a_{1}, \dots, a_{m}}$ and $O = {o_{1}, \dots, o_{n}}$ indicate the sets of possible actions and observations. A deterministic policy can be written as a string $π = a_{i_{1}} a_{i_{2}} \dots a_{i_{n}}$ with $a_{i_{k}}$ indicating the action taken when $o_{k}$ is observed.

Here I consider a problem setting as a triplet $(A, O, D)$ where $D$ stands for some kind of environmental data—could be about, for example, the transition function in a MDP, or the structure of the elements in the search space $O$ . Since I want to analyse behaviour across different environments, instead of considering one single policy I’ll sometimes refer to a more general function $g$ (probably closer to the concept of “agent design”, rather than just “agent”) mapping environments to policies on them: $(A, O, D) g \mapsto π_{(A, O, D)}$ .

Lookup table vs simple-reward RL

As written before, a lookup table is a policy that is described case-by-case, by explicitly giving the list of all observation-action pairs. Thus, a generic lookup table for a setting $(A, O, D)$ is expected to ...

Vanessa Kosoy's Shortform