MAXQ Value Function Decomposition

Why Does This Exist?

Flat reinforcement learning algorithms scale poorly in long-horizon problems with complex subgoal structures. When an agent must navigate across rooms, pick up objects, unlock doors, and deliver cargo, choosing from raw primitive motor commands at every single time step leads to exponential sample complexity and sluggish exploration.

While the Options framework (Sutton et al., 1999) introduced temporally extended actions, options treat subpolicies as black boxes without breaking down the value function itself. An option still evaluates values across the full global state space, offering no built-in mechanism to ignore irrelevant state dimensions.

MAXQ Value Function Decomposition (Dietterich, 2000) solves this limitation by decomposing the core Markov Decision Process into a directed acyclic graph of subtasks. Crucially, MAXQ splits the value function itself into:

1. Child Execution Values $V(a, s)$: The reward earned while executing an immediate child subtask.
2. Completion Functions $C(i, s, a)$: The expected future reward of completing the rest of the parent task after the child subtask terminates.

By explicitly formalizing completion functions and state abstraction, MAXQ enables subtasks to ignore irrelevant state variables, dramatically compressing the state space and facilitating modular subtask reuse across different parent routines.

Think of It Like This

How It Actually Works

MAXQ Task Graph and Recursive Value Decomposition

The overall MDP is decomposed into a hierarchy of subtasks $\{M_0, M_1, \dots, M_K\}$, where $M_0$ represents the root task. The hierarchy forms a Directed Acyclic Graph (DAG) called the MAXQ Task Graph.

1. Formal Subtask Definition

Each subtask node $M_i$ is defined by a tuple $M_i = \langle T_i, A_i, \tilde{R}_i \rangle$:

• Termination Predicate $T_i(s)$: A boolean condition that determines whether subtask $M_i$ has completed (e.g., $T_{\text{Nav}}(s) = \text{True}$ when taxi coordinates match destination coordinates).
• Child Actions $A_i$: The set of actions that $M_i$ can invoke. Children can be other subtasks or primitive actions.
• Pseudo-Reward Function $\tilde{R}_i(s)$: An optional intrinsic reward function used to shape subtask policies toward desirable terminal subgoals.

2. Value Function Decomposition

Let $Q^\pi(i, s, a)$ be the expected cumulative discounted reward of executing child action $a \in A_i$ from state $s$ within parent subtask $M_i$.

MAXQ decomposes this value function recursively:

where:

• $V^\pi(a, s)$ (Child Value): The expected cumulative reward earned during the execution of child action $a$ until $a$ terminates: $$V^\pi(a, s) = \begin{cases} \sum_{s'} P(s' \mid s, a) R(s' \mid s, a) & \text{if } a \text{ is primitive} \\ Q^\pi(a, s, \pi_a(s)) & \text{if } a \text{ is a subtask} \end{cases}$$
• $C^\pi(i, s, a)$ (Completion Function): The expected cumulative discounted reward of completing the rest of parent subtask $M_i$ after child action $a$ terminates: $$C^\pi(i, s, a) = \sum_{s', N} P(s', N \mid s, a) \, \gamma^N Q^\pi(i, s', \pi_i(s'))$$ where $P(s', N \mid s, a)$ is the probability that child subtask $a$ terminates in state $s'$ after $N$ environment steps.

3. Recursive Policy Execution

At any subtask level $M_i$, the agent selects the child action that maximizes the sum of child value and parent completion value:

Execution recurses down the task graph until a primitive motor action is dispatched to the environment.

4. State Abstraction

Each subtask $M_i$ is equipped with an abstraction mapping $\phi_i(s)$ that filters out state dimensions irrelevant to $M_i$. For example, a navigation subtask $M_{\text{Nav}}$ only requires the current $(x, y)$ coordinates and target coordinates $(x_{\text{target}}, y_{\text{target}})$, completely ignoring passenger status or final delivery destination. This shields lower-level subtasks from exponential state explosion.

Worked numerical example

Consider the classic Taxi environment where a taxi must pick up a passenger and drop them off at a destination.

Setup:

• Current state: $s = \langle \text{taxi\_pos}=(1, 1), \, \text{pass\_loc}=(1, 3), \, \text{dest}=(4, 4) \rangle$.
• Step cost: $r = -1.0$ per move. Illegal action penalty: $r = -10.0$.
• Parent subtask: $M_{\text{Get}}$ (pickup passenger).
• Candidate child actions for $M_{\text{Get}}$:
  1. Subtask $M_{\text{Nav}}(s, \text{pass\_loc})$: Navigate to passenger.
  2. Primitive action Pickup: Attempt pickup at current location.

Step 1: Evaluate Child Action 1 ($M_{\text{Nav}}$)

• Child Value $V(M_{\text{Nav}}, s)$: Taxi is at $(1, 1)$ and passenger is at $(1, 3)$. Manhattan distance is $|1 - 1| + |3 - 1| = 2$ steps North. $$V(M_{\text{Nav}}, s) = 2 \times (-1.0) = -2.0$$
• Completion Function $C(M_{\text{Get}}, s, M_{\text{Nav}})$: Once $M_{\text{Nav}}$ completes, the taxi arrives at $(1, 3)$. To terminate parent subtask $M_{\text{Get}}$ (passenger inside taxi), the agent must execute 1 legal Pickup step: $$C(M_{\text{Get}}, s, M_{\text{Nav}}) = 1 \times (-1.0) = -1.0$$
• Total Q-value: $$Q(M_{\text{Get}}, s, M_{\text{Nav}}) = V(M_{\text{Nav}}, s) + C(M_{\text{Get}}, s, M_{\text{Nav}}) = -2.0 + (-1.0) = -3.0$$

Step 2: Evaluate Child Action 2 (Immediate Pickup)

• Child Value $V(\text{Pickup}, s)$: Taxi attempts to pick up at $(1, 1)$ where no passenger is present. The environment incurs an illegal action penalty: $$V(\text{Pickup}, s) = -10.0$$
• Completion Function $C(M_{\text{Get}}, s, \text{Pickup})$: Because the illegal pickup failed, the passenger remains at $(1, 3)$. Completing $M_{\text{Get}}$ still requires navigating 2 steps and executing 1 legal pickup: $$C(M_{\text{Get}}, s, \text{Pickup}) = 2(-1.0) + 1(-1.0) = -3.0$$
• Total Q-value: $$Q(M_{\text{Get}}, s, \text{Pickup}) = V(\text{Pickup}, s) + C(M_{\text{Get}}, s, \text{Pickup}) = -10.0 + (-3.0) = -13.0$$

Step 3: Action Selection

Evaluating the decision rule:

The hierarchical policy selects $M_{\text{Nav}}$, correctly prioritizing navigation over an illegal premature pickup.

Code

1from dataclasses import dataclass2from typing import List, Tuple3
4
5@dataclass6class SubtaskOption:7    """Represents a candidate child subtask or primitive action."""8
9    name: str10    is_primitive: bool11    child_value_v: float12    completion_value_c: float13
14    @property15    def total_q_value(self) -> float:16        return self.child_value_v + self.completion_value_c17
18
19class MAXQTaskGraphEvaluator:20    """Demonstrates MAXQ Value Function Decomposition (Dietterich 2000):21
22    Q(i, s, a) = V(a, s) + C(i, s, a)23    """24
25    def __init__(26        self, step_cost: float = -1.0, illegal_penalty: float = -10.027    ) -> None:28        self.step_cost = step_cost29        self.illegal_penalty = illegal_penalty30
31    def compute_nav_child_value(32        self,33        current_pos: Tuple[int, int],34        target_pos: Tuple[int, int],35    ) -> float:36        """Computes V(M_Nav, s) using Manhattan distance step costs."""37        distance = abs(current_pos[0] - target_pos[0]) + abs(38            current_pos[1] - target_pos[1]39        )40        return distance * self.step_cost41
42    def compute_pickup_child_value(43        self,44        taxi_pos: Tuple[int, int],45        pass_pos: Tuple[int, int],46    ) -> float:47        """Computes V(Pickup, s): legal pickup cost or illegal penalty."""48        if taxi_pos == pass_pos:49            return self.step_cost50        return self.illegal_penalty51
52    def evaluate_m_get_subtask(53        self,54        taxi_pos: Tuple[int, int],55        pass_pos: Tuple[int, int],56    ) -> List[SubtaskOption]:57        """Evaluates child choices under parent subtask M_Get."""58        # 1. Option: Call Navigation child M_Nav59        v_nav = self.compute_nav_child_value(taxi_pos, pass_pos)60        # Completing M_Get after arriving requires 1 pickup step61        c_nav = self.step_cost62        opt_nav = SubtaskOption(63            name="M_Nav",64            is_primitive=False,65            child_value_v=v_nav,66            completion_value_c=c_nav,67        )68
69        # 2. Option: Call primitive Pickup immediately70        v_pickup = self.compute_pickup_child_value(taxi_pos, pass_pos)71        # Completing M_Get after illegal pickup requires 2 nav steps + 1 legal pickup72        dist = abs(taxi_pos[0] - pass_pos[0]) + abs(taxi_pos[1] - pass_pos[1])73        c_pickup = (dist + 1) * self.step_cost74        opt_pickup = SubtaskOption(75            name="Pickup",76            is_primitive=True,77            child_value_v=v_pickup,78            completion_value_c=c_pickup,79        )80
81        return [opt_nav, opt_pickup]82
83    @staticmethod84    def select_best_subtask(options: List[SubtaskOption]) -> SubtaskOption:85        """Selects argmax_{a} [ V(a, s) + C(i, s, a) ]."""86        return max(options, key=lambda opt: opt.total_q_value)87
88
89# Test scenario matching the worked numerical example90evaluator = MAXQTaskGraphEvaluator(step_cost=-1.0, illegal_penalty=-10.0)91taxi_start = (1, 1)92passenger_location = (1, 3)93
94options = evaluator.evaluate_m_get_subtask(taxi_start, passenger_location)95
96for opt in options:97    print(98        f"Child: {opt.name:<6} | V(a, s): {opt.child_value_v:5.1f} | "99        f"C(i, s, a): {opt.completion_value_c:5.1f} | Q(i, s, a): {opt.total_q_value:5.1f}"100    )101# -> Child: M_Nav  | V(a, s):  -2.0 | C(i, s, a):  -1.0 | Q(i, s, a):  -3.0102# -> Child: Pickup | V(a, s): -10.0 | C(i, s, a):  -3.0 | Q(i, s, a): -13.0103
104best_choice = evaluator.select_best_subtask(options)105print(106    f"Selected Subtask: {best_choice.name} (Q = {best_choice.total_q_value:.1f})"107)108# -> Selected Subtask: M_Nav (Q = -3.0)109
110# Verification assertions111assert options[0].name == "M_Nav"112assert options[0].child_value_v == -2.0113assert options[0].completion_value_c == -1.0114assert options[0].total_q_value == -3.0115
116assert options[1].name == "Pickup"117assert options[1].child_value_v == -10.0118assert options[1].completion_value_c == -3.0119assert options[1].total_q_value == -13.0120
121assert best_choice.name == "M_Nav"

Watch Out For

The Quick Version

• MAXQ decomposes complex Markov Decision Processes into a hierarchical Directed Acyclic Graph (DAG) of reusable subtasks with localized termination predicates $T_i(s)$.
• The core value decomposition splits action-values into child execution value $V(a, s)$ and parent completion value $C(i, s, a)$: $Q(i, s, a) = V(a, s) + C(i, s, a)$.
• State abstraction shields lower-level subtasks by filtering out state variables irrelevant to their local objectives, exponentially shrinking the effective state space.
• MAXQ achieves recursive optimality rather than global optimality; child subtasks optimize local subgoals independently of global parent contexts unless guided by pseudo-rewards.

What to Read Next

• Hierarchical RL
• The Options Framework
• Feudal Networks (FuN)