MAXQ Value Function Decomposition

Instead of solving one huge task all at once, MAXQ splits it into a tree of smaller jobs where each job only watches the details it needs.

Parent Get compares navigate at minus 3.0 against early pickup at minus 13.0 and picks navigation

Why Does This Exist?

Flat control picks one primitive move at every step. In a taxi job with pickup then delivery, that means thousands of steering choices before any payoff, and credit has to travel all the way back. Learning is slow and exploration wanders.

Temporal extension helps but not enough. The options framework packages a skill as one long action, yet it still scores that skill with a flat value over the full state. Nothing tells the navigation skill to ignore passenger status or delivery address.

MAXQ, from Dietterich in 2000, splits the value itself. Each parent scores a child as work done inside the child plus work left to finish the parent. That split is what lets a subtask throw away irrelevant state and be reused elsewhere. This page covers the split and the taxi numbers. For the manager worker view see hierarchical RL, and for plain values see value functions.

You need one idea first. A value is expected future reward from some point onward. A Q value does the same but after fixing the next action too.

Think of It Like This

Building a house with separate crews

A builder splits the house into frame, wiring, and paint crews under one foreman. The wiring crew lays cable and leaves when the outlets test live. Its work ticket shows two numbers: pay earned while wiring, plus expected pay left to finish the whole house after wiring ends.

The wiring lead ignores paint color and tile choice. Those details do not change any outlet test, so they stay off the crew sheet. That is state abstraction. The same wiring crew can later wire a different house plan without retraining.

Where the analogy stops: house plans are fixed and steps rarely fail. In RL the world is stochastic, so the foreman rechecks both numbers at every state and may call a different crew next time.

How It Actually Works

Write $i$ for a parent subtask, $s$ for state, $a$ for a child the parent can call, and $N$ for how many primitive steps that child runs. Let $V(a, s)$ be expected reward earned inside child $a$ until it stops. Let $C(i, s, a)$ be expected reward to finish parent $i$ after $a$ stops. Let $\gamma$ in $[0, 1]$ discount the future and $P(s', N \mid s, a)$ give the chance the child ends in state $s'$ after $N$ steps.

The MAXQ split is:

$Q(i, s, a) = V(a, s) + C(i, s, a)$

In words: total parent value equals child work plus remaining parent work. The child term recurses, so a subtask child calls its own $Q(a, s, \pi_a(s))$ while a primitive child pays its one step reward. The completion term looks ahead:

$C(i, s, a) = \sum_{s', N} P(s', N \mid s, a) \, \gamma^N Q(i, s', \pi_i(s'))$

The parent policy picks the child with the largest sum:

$\pi_i(s) = \arg\max_{a} [V(a, s) + C(i, s, a)]$

Each subtask $M_i$ also carries a termination check $T_i(s)$ that says when it stops, an allowed child set $A_i$ , and an optional pseudo reward that marks good stopping states. Its abstraction map $\phi_i(s)$ keeps only the state parts the subtask needs. A navigation map keeps taxi position and target and drops passenger status.

Worked example

Taxi at $(1, 1)$ , passenger at $(1, 3)$ , step cost $-1.0$ , illegal pickup $-10.0$ . Parent $M_{\text{Get}}$ must get the passenger aboard. Two children:

Child Navigate to passenger. Manhattan distance is $|1-1| + |3-1| = 2$ steps. So $V = 2 \times (-1.0) = -2.0$ . After arrival one legal pickup remains, so $C = -1.0$ . Total $Q = -2.0 + (-1.0) = -3.0$ .
Child Pickup now. No passenger here, so $V = -10.0$ . The job still needs 2 moves plus 1 legal pickup, so $C = 2 \times (-1.0) + 1 \times (-1.0) = -3.0$ . Total $Q = -10.0 + (-3.0) = -13.0$ .

The parent keeps the max, $\max(-3.0, -13.0) = -3.0$ , and calls Navigate. The diagram draws these two bars and the winning $-3.0$ .

Code

The snippet adds the two parts and picks the larger total.

1def q_value(child: float, completion: float) -> float:2    """One MAXQ total: child work plus remaining parent work."""3    return child + completion4
5
6if __name__ == "__main__":7    nav = q_value(-2.0, -1.0)8    pick = q_value(-10.0, -3.0)9    print(round(nav, 2))10    print(round(pick, 2))11    print(round(max(nav, pick), 2))

1# -> expected output:2-3.03-13.04-3.0

Watch Out For

Settling for locally best subtasks and missing the global route

The symptom: each subtask looks perfect alone but the full trip is long. A navigation skill sees two doors out of a room, both 3 steps, and picks one at random. The other door sits next to the passenger and would save 10 steps later, but the child cannot see that future.

The fix: add pseudo rewards that mark parent friendly stopping states, so the child prefers the door near the next job. Then fine tune the stack jointly once the pieces work.

Abstracting away a variable the child actually needs

The symptom: navigation ignores a traffic flag or passenger status to shrink the table, then fails whenever that flag changes the cost. Values look clean in training and break on the first new map.

The fix: add back any variable that changes reward or transitions for that subtask, even if it feels like parent detail. Shrink only what you have tested as irrelevant.

The Quick Version

MAXQ writes parent value as child value plus completion value: $Q(i, s, a) = V(a, s) + C(i, s, a)$ .
The parent acts by max over children, then recurses until a primitive move fires.
State abstraction lets a subtask ignore variables that do not change its own reward or transitions.
In the taxi example Navigate totals $-3.0$ and early Pickup totals $-13.0$ , so the parent picks Navigate.
The guarantee is recursive optimality per subtask, not global optimality, unless pseudo rewards align the boundaries.