oak architecture

Richard Sutton
The Alberta Plan for AI Research
RLC Talk

• The greatest advances in AI are still to come
  • The race is more like a marathon than a sprint
  • ASI will be an unalloyed good for the world;
  • The path to intelligent agents is through RL
  • The biggest bottleneck is very crude / inadequate learning algorithms.
• You have to be able to learn at runtime (big world)
  • Big world
    • → appears non-stationary
      • → nothing the agent learns can be exact or optimal, everyhting must be approximate (value funcs, policies, transition models, states)
    • pre-requisite for open-ended discovery of abstractions
    • Thing can also be learned / baked in at design-time (I’m thinking outer-loop/developmental encoding)… but why not worry about trying to get a head-start, and make a conceptually simple design?!
    • meta-learning has to happen at runtime (too)
    • Domain general
    • contains nothing specific to any world; should not reflect the world in whicch it is expected to be used
    • details matter for specific task performance, not for the general architecture, and should be learned at runtime
    • the world out there is arbitrarily complex; you don’t want to bake the intricate complex details into the model if you want a conceptual understanding of how the mind works as opposed to something that works right away
    • experiential / streaming
    • grows from runtime experiencee, not from a special training phase
    • open-ended
    • unlimited in sophistication (other than by computational resources)
    • → at least as impactful of than the origin of life
    • he says reward is enough, which I’m not so sure about? like in a practical sense (Why Greatness Cannot Be Planned etc.)
    • Nvm: they’re claims about different layers. “Reward is enough” says a scalar criterion suffices to define all of intelligence, without the need for multi-objective.
    • WGCBP is about the search strategy: optimizing directly toward the objective fails on deceptive landscapes, because stepping stones don’t resemble the destination.
    • Both can be true at once: reward as criterion, not as search heuristic.
    • (I suggest reading the below bullets after reading the rest of the note)
    • OaK is actually doing stepping stone collection: subproblems come from interesting features (play), not from reward gradients.
    • Though… if $\kappa$ prunes subproblems that cost too much reward, and in a truly deceptive world the crucial stepping stones might be exactly the expensive ones … that’s exactly what WGCBP argues against “a little bit of false compass” doesnt improve your navigation.
    • But fully ignoring reward (~infinitely large $\kappa$) fails empirically: subtasks that ignore reward learn options like “leap off the cliff to touch the feature”, and planning with their models performs worse. Stepping stones must be usable by an agent that lives in the reward stream.
    • Several $\kappa$ per feature can coexist (cheap and expensive versions of attainment), each yielding its own option; curation then keeps the options whose models prove useful in planning. How much reward a stepping stone may cost doesn’t have to be decided when posing the subproblem, it’s settled afterwards by usefulness.
    • Reward also influences which features get subproblems in the first place: the feedback loop ranks features by their usefulness to play, prediction, and planning, and planning maximizes reward. So even with generous $\kappa$, the choice of stepping stones isn’t reward-free.
    • If the reward encodes only survival constraints and high-signal proxies (like evolution’s hardwired primary rewards, such as body damage or energy/food) rather than granular goals, then respecting reward amounts to avoiding self-destruction while collecting stepping stones, and there is no conflict with WGCBP.

From The Bitter Lesson:

… the actual contents of minds are … part of the arbitrarily, intrinsically-complex outside world. They are not what should be built in, as their complexity is endless;

instead we should build in only the meta-methodsd that can find and capture arbitrary complexity…

We want AI agents taht can discover like we can, not which contain what we discovered.

Note how LLMs heavily bias on the latter.

model-free: Basic RL: The agent constructs an approximate policy and/or value function, both a function of the world’s state.
non-markov: Better: The agent constructs its state representation (e.g. as a feature vector)
model-based: Better: The agent constructs a transition model fo the world, and uses it to plan a better policy and/or value function
OaK:

• The agent poses auxiliary subproblems for attaining individual features
• These enable the discovery of higher and higher levels of abstraction, limited only by computational resources (open-ended abstractions)

“OaK” → Options and Knowledge

option pair $(\pi ,\gamma )$

• a policy $\pi :\text{States}\to \mathrm{Pr}(\text{Actions})$ … a way of behaving
• a termination condition $\gamma :\text{States}\to [0,1]$ … a way of terminating the behavior

The agent has lots of options and learns knowledge about what happens when each is followed until termination.
→ Knowledge = verifiable predictions about experience
→ The agent learns a high-level transition model of the world, that enables planning with longer jumps and hopefully “carves the world’s dynamics at its joints”

OaK involves 8 steps performed in parallel at runtime:

• Learn the policy and the value function for maximizing reward
  • Would be done if we could to continual learning and meta learning
• Generate new state features from existing state features
  • Lots of ideas but no specific proposal. Candidates are generate-and-test (continual backprop) and step-size meta-learning (IDBD).
• Rank-order the features
  • Seems easy but can’t be done before the rest is done
  • Nothing to rank by until options and models exist, so the first posing runs on interestingness (a feature that spiked once, unexpectedly); usefulness feedback refines the ranking from there.
• Create subproblems, one for each highly-ranked feature
  • Seems done (see below)
• Learn solutions to subproblems (options and sub-value functions)
  • Open: How to do it with continual deep learning.
• Learn transition models of the options and actions
  • Open: How to do it with continual deep learning.
• Plan with the transition models
  • ~Understood: approximate value iteration with option models (see below)
• Maintain meta-data on the utility of everything; curate
  • Fixed compute budget: low-utility features / subproblems / options / models get retired, their slots recycled for new candidates (same generate-and-test scheme continual backprop uses for neurons).

How to create sub-problems in a domain-general way?
“e.g. reward-respecting subproblems of feature attainment”

A feature is a single entry of the state vector: one scalar, ${\varphi }_i(s)$ is the $i$th number in the vector perception computes from the sensorimotor stream. In deep-net terms a feature is one unit of the representation layer, its value the unit’s activation. (“rattle sound present” for a baby, “standing in a doorway” in a gridworld, “gripper holds object” for a robot)

OaK creates a subproblem from a feature $i,\kappa$ (an interesting sound / bright light / …), by in each state $s$:

$$\underset{\pi ,\gamma }{\max }\mathbb{E}\left[\kappa \varphi (S_T)+\sum _{k=t+1}^T{R}_k+\hat{v}(S_T)\mid S_t=s\right]$$

$i$ … feature number
$\kappa$ … how intensely we want the feature, balanced against foregoing rerward

• The subproblem is to drive the world to a state where the features is high without loosing too much in terms of reward.
• The solution to a subproblem is an option: We want to find an option $\pi ,\gamma$ that maximizes the value of the $i^{\text{th}}$ feature, at termination, while respecting rewards and value (of the state you end up in).
• The $\hat{v}(S_T)$ term prices in where you end up: walking along the cliff edge and “terminating” mid-air collected perfectly fine rewards; the crash landing only shows up in the value of the termination state.

How to structure mental development with features, Options, and Knowledge:

• You’re foraging for useful features (highly ranked)
• Attaining a feature is a subproblem
• Options are the solutions to subproblems (know-how); their transition models are the knowledge (know-what)
• Planning composes the models into improved values and policies; which models earn their keep in planning feeds back to rank options, and in turn features
• Usefulness is measurable at each consumer: a feature by how much the predictors that take it as input rely on it (weight magnitude, per-feature step size), an option by whether its model wins the $\max$ in backups and changes values during planning.

Perception ←→ Feature construction (representation learning)
Feature-attainment ←→ Play (problem posing and solving) → Options (behaviors)
Transition models ←→ Prediction (learning predictive knowledge; consequences of choosing option o for k steps) → Planning → Adaptive behavior

Why call predictions "knowledge" knowledge is a verifiable prediction about experience. "The station is 10 minutes away" cashes out, for an agent, as: "if I execute walk-to-station, I terminate in a state with station-features active, with ${\gamma }^k$ reflecting ~10 minutes, near-zero reward en route." That statement is checkable by the agent itself: run the option, compare, correct with the TD error. No labels, no human in the loop. In a big world everything the agent believes is approximate and the world appears non-stationary, so knowledge must be continually maintained. Predictions can be maintained autonomously because the maintenance signal (the agent's own experience stream) never runs out. Knowledge stored as text cannot be checked against the agent's own experience (or at least not as easily, you need to first interpret it / bring them into a verifyable form; RLVR), which is one of Sutton's complaints about LLMs as a path to agents.

Sutton’s epistemic stance:

The processes of play, prediction and planning feed back to perception how useful a feature was:

Transition models also trickles back feedback to which options are useful which trickles back to the choice of feature-attainment subproblems.

“Anything that can be learned, can also be planned”
→ Everything you can learn from environmental rewards, you can also plan ahead, via value functions / value iteration.

GVF learning algorithms can be used for all prediction learning

• value functions for the main problem (getting reward)
• value functions for the sub-problems of feature attainment
• transition models of the options

Why plan? Why jumpy models? (jumpy models = temporally abstract transition models, i.e. option models)

The world changes → the correct values change. And it is often easier to get the model right than the values right → keep the model current, and re-derive values from it by planning:

• The real world is big, changing, but with stable large-scale structure → model only the large-scale, stable, purposive dynamics (failure mode: modeling at the wrong level (pixels, single steps)), and let planning determine the frequently changing values:
• A value aggregates everything between you and all future reward; whether it’s right is never directly observable. A model entry (“this option, run from here, lands me there, takes this long”) is a local fact: run the option once, compare where you actually land.
• Change is sparse and local in model-space but dense and global in value-space: a café closes → one transition fact changed, but the value of every state from which you might have walked there shifted overnight. Local model damage is cheap to repair from experience; global value damage would take forever by trial and error, but planning re-derives it in a few backups.
• The reward function is part of the world and ~as fixed as the dynamics (hardwired primary reward: sugar stays sweet, injury still hurts). What changes is where reward can currently be obtained, i.e. the values. “It’s always true that I can walk over there and find the restroom; it’s not always true that I want to.”
• “To prepare for this, we get ready for different values” → which subproblems are useful: attain stable features (landmarks); the skill “reach the doorway” and its model stay valid whichever room is valuable this week.

Planning is approximate value iteration: whenever there is compute to spare, select a state $s$ (search control) and perform a backup with the learned model:

With option models in place of action models, each backup jumps a whole behavior instead of one timestep. The equation is unchanged except that no $\gamma$ appears in front of the sum: an option’s $\hat{p}$ already carries the discount ${\gamma }^k$ for the $k$ steps the option takes:

With function approximation $V(s)$ becomes $\hat{v}(s,\mathbf{w})$ and the model becomes parametric too; a backup computes the backed-up value $b(s,a,\mathbf{w})$ and takes a gradient step of $\mathbf{w}$ towards it (this and the next slides are written with one-step action models again, hence the explicit $\gamma$: for a single step the discount is the same for every next state and can be pulled out in front of the sum):

Besides the outer loop over states (search control), there are two loops inside each backup. The $\max$ over options is manageable even with many options (incrementally: keep best-so-far, check new candidates against it). The ${\sum }_{s^{\prime }}$ is the problem when the world is stochastic: lots of possible next states.

The solution is to use an expectation model: output only the expected next feature vector instead of a distribution over next states.
If $\hat{v}$ is linear in the features, expectation and value commute, i.e. $\mathbb{E}[\hat{v}(s^{\prime })]=\hat{v}(\mathbb{E}[s^{\prime }])$, and the expected action value becomes a single inner product, cheap and exact → linear value functions at the planning level, on top of learned nonlinear features:

Arguably the first plausible mechanistic answers to some old questions:

• Where do concepts come from? Features that proved useful to play, prediction and planning.
• What is perception? Constructing state features grounded in experience, without reference to human labels or an external ontology.
• What is play for? Posing and solving subproblems, which structure cognition.
• What is reason? Planning with (option) models.