[Aspiration-based designs] Outlook: dealing with complexity

Summary. This teaser post sketches our current ideas for dealing with more complex environments. It will ultimately be replaced by one or more longer posts describing these in more detail. Reach out if you would like to collaborate on these issues.

Multi-dimensional aspirations

For real-world tasks that are specified in terms of more than a single evaluation metric, e.g., how much apples to buy and how much money to spend at most, we can generalize Algorithm 2 as follows from aspiration intervals to convex aspiration sets:

• Assume there are $d>1$ many evaluation metrics $u_i$, combined into a vector-valued evaluation metric $u=(u_1,\dots ,u_d)$.

• Preparation: Pick $d+1$ many linear combinations $f_j$ in the space spanned by these metrics so that their convex hull is full-dimensional and contains the origin, and consider the $d+1$ many policies ${\pi }_j$ each of which maximizes the expected value of the corresponding function $f_j$. Let $V_j\left(s\right)$ and $Q_j(s,a)$ be the expected values of $u$ when using ${\pi }_j$ in state $s$ or after using action $a$ in state $s$, respectively (see Fig. 1). Let the admissibility simplices $V\left(s\right)$ and $Q(s,a)$ be the simplices spanned by the vertices $V_j\left(s\right)$ and $Q_j(s,a)$, respectively (red and violet triangles in Fig. 1). They replace the feasibility intervals used in Algorithm 2.

• Policy: Given a convex state-aspiration set $E\left(s\right)\subseteq V\left(s\right)$ (central green polyhedron in Fig. 1), compute its midpoint (centre of mass) $m$ and consider the $d+1$ segments ${\ell }_j$ from $m$ to the corners $V_j\left(s\right)$ of $V\left(s\right)$ (dashed black lines in Fig. 1). For each of these segments ${\ell }_j$, let $A_j$ be the (nonempty!) set of actions for which ${\ell }_j$ intersects $Q(s,a)$. For each $a\in A_j$, compute the action-aspiration $E(s,a)\subseteq Q(s,a)$ by shifting a copy $C_j$ of $E\left(s\right)$ along ${\ell }_j$ towards $V_j\left(s\right)$ until the intersection of $C_j$ and ${\ell }_j$ is contained in the intersection of $Q(s,a)$ and ${\ell }_j$ (half-transparent green polyhedra in Fig. 1), and then intersecting $C_j$ with $Q(s,a)$ to give $E(s,a)$ (yellow polyhedra in Fig. 1). Then pick one candidate action from each $A_j$ and randomize between these $d+1$ actions in proportions so that the corresponding convex combination of the sets $E(s,a)$ is included in $E\left(s\right)$. Note that this is always possible because $m$ is in the convex hull of the sets $C_j$ and the shapes of the sets $E(s,a)$ “fit” into $E\left(s\right)$ by construction.

• Aspiration propagation: After observing the successor state $s^{\prime }$, the action-aspiration $E(s,a)$ is rescaled linearly from $Q(s,a)$ to $V\left(s^{\prime }\right)$ to give the next state-aspiration $E\left(s^{\prime }\right)$, see Fig. 2.

(We also consider other variants of this general idea)

Fig. 1: Admissibility simplices, and construction of action-aspirations by shifting towards corners and intersecting with action admissibility simplices (see text for details).

Fig. 2: An action admissibility simplex $Q(s,a)$ is the convex combination of the successor states’ admissibility simplices $V\left(s^{\prime }\right)$, mixed in proportion to the respective transition probabilities $P_M(s^{\prime }|s,a)$. An action aspiration $E(s,a)$ can be rescaled to a successor state aspiration $E\left(s^{\prime }\right)$ by first mapping the corners of the action admissibility sets onto each other (dashed lines) and extending this map linearly.

Hierarchical decision making

A common way of planning complex tasks is to decompose them into a hierarchy of two or more levels of subtasks. Similar to existing approaches from hierarchical reinforcement learning, we imagine that an AI system can make such hierarchical decisions as depicted in the following diagram (shown for only two hierarchical levels, but obviously generalizable to more levels):

Fig. 3: Hierarchical world model in the case of two hierarchical levels of decision making.

[Roman Malov]

Pick $d+1$ many linearly independent linear combinations $f_j$
isn’t there at most $d$ linearly independent linear combinations of $u_i$?

[Roman Malov]

maybe you meant pairwise linearly independent (by looking at the graph)

[Jobst Heitzig]

You are of course perfectly right. What I meant was: so that their convex hull is full-dimensional and contains the origin. I fixed it. Thanks for spotting this!