Controller Abstractions

Chapter 1: FSC Structure

A finite state controller is a tuple (X, ψ, η) where:

Execution: at node x, sample action a ~ ψ(·|x). Environment produces observation o. Transition to x' ~ η(·|x, a, o). Repeat forever. The policy is entirely encoded in (ψ, η) — two lookup tables.

For the crying baby problem, a simple 2-node controller captures the intuitive policy:

Chapter 2: Evaluating FSCs

Given a controller, how much reward does it actually get? We need to compute V_x(s) = expected discounted return starting in state s and controller node x.

The evaluation is defined by a system of linear equations — one per (x, s) pair. For a stochastic controller:

This looks complicated, but for a fixed controller it's just a linear system: |X|·|S| equations in |X|·|S| unknowns. Solve it once (e.g., with Gaussian elimination) and you have the value of the controller from every (x, s) pair.

julia
function evaluate_controller(pomdp, fsc)
    nS, nX = length(states(pomdp)), length(fsc.nodes)
    # Build linear system: V = R + γ T O η V
    # Row idx: (x-1)*nS + s. Build (nX*nS) × (nX*nS) matrix.
    A = zeros(nX*nS, nX*nS)
    b = zeros(nX*nS)

    for (xi, x) in enumerate(fsc.nodes)
        for (si, s) in enumerate(states(pomdp))
            row = (xi-1)*nS + si
            A[row, row] = 1.0  # V[x,s] coefficient
            exp_r = 0.0
            for a in actions(pomdp)
                pa = fsc.ψ(a, x)
                exp_r += pa * reward(pomdp, s, a)
                for (si2, s2) in enumerate(states(pomdp))
                    for o in observations(pomdp)
                        for (xi2, x2) in enumerate(fsc.nodes)
                            col = (xi2-1)*nS + si2
                            A[row, col] -= discount(pomdp) * pa *
                                transition(pomdp,s,a,s2) *
                                obs(pomdp,a,s2,o) *
                                fsc.η(x2,x,a,o)
                        end
                    end
                end
            end
            b[row] = exp_r
        end
    end
    V_flat = A \ b
    return reshape(V_flat, nS, nX)  # V[s, x] = value at state s, node x
end

Chapter 3: Policy Iteration for Controllers

We know how to evaluate a given controller. Now: how do we improve it? Policy iteration for FSCs alternates between evaluation and a greedy improvement step — the same structure as MDP policy iteration.

The improvement step: given the current value function V_x(s) and the current controller (ψ, η), find new distributions (ψ*, η*) that maximize the value at each (x, s):

where b_x(s) is the probability of being in state s at node x (the stationary distribution over (x,s) pairs). This is a linear program in the controller parameters: maximize a linear objective over the simplex constraints ∑_a ψ(a|x)=1 and ∑_x' η(x'|x,a,o)=1.

Chapter 4: Node Expansion

Policy iteration with a fixed n-node controller finds the best policy expressible with n nodes. But what if n is too small? The controller might be fundamentally limited, unable to represent anything near the optimal policy regardless of what (ψ, η) we choose.

Node expansion increases n when the current controller has converged to a local optimum. The idea: add a new node x_new and initialize it with a useful purpose. The most effective strategy is to initialize x_new as a copy of the existing node that is most frequently visited weighted by missed value.

After adding x_new, run policy iteration again. The new node gives the optimization more freedom to represent policies that require more "memory." Repeat expansion until the value increase per expansion is below threshold.

Chapter 5: Nonlinear Programming Formulation

Policy iteration for FSCs requires solving an LP in the improvement step. But LPs assume a fixed evaluation. What if we want to jointly optimize both the evaluation and the improvement, treating (ψ, η, V) as one big optimization problem?

The FSC optimization over a fixed n can be written as a nonlinear program (NLP). The optimization variables are:

• ψ_a,x = probability of taking action a at node x. Constraints: ψ_a,x ≥ 0, ∑_a ψ_a,x = 1 for all x.
• η_x',x,a,o = probability of transitioning to x' from x after (a,o). Constraints: η ≥ 0, ∑_x' η_x',x,a,o = 1 for all x, a, o.
• V_x,s = value at (x,s). Must satisfy the Bellman equations as constraints.

The objective: maximize V_x0·b₀ = ∑_s b₀(s) V_x0(s) for an initial belief b₀ and starting node x₀.

python (NLP formulation sketch)
from scipy.optimize import minimize
import numpy as np

def fsc_nlp(pomdp, n_nodes, b0):
    # Pack ψ and η into a single parameter vector θ
    nS, nA, nO = pomdp.nS, pomdp.nA, pomdp.nO
    nX = n_nodes

    def unpack(theta):
        # ψ: (nX, nA) softmax'd per row
        psi_raw = theta[:nX*nA].reshape(nX, nA)
        psi = softmax(psi_raw, axis=1)
        # η: (nX, nA, nO, nX) softmax'd per (x,a,o)
        eta_raw = theta[nX*nA:].reshape(nX, nA, nO, nX)
        eta = softmax(eta_raw, axis=3)
        return psi, eta

    def objective(theta):
        psi, eta = unpack(theta)
        V = evaluate_controller(pomdp, psi, eta)  # solve linear system
        return -np.dot(b0, V[0, :])  # maximize value at node 0

    theta0 = np.random.randn(nX*nA + nX*nA*nO*nX) * 0.1
    result = minimize(objective, theta0, method='L-BFGS-B')
    return unpack(result.x)

Chapter 6: Gradient Ascent for Controllers

NLP solvers (L-BFGS, SLSQP) require computing gradients. For FSCs, we need ∂V_x0(b₀) / ∂ψ and ∂V_x0(b₀) / ∂η. These can be computed by differentiating through the linear system that defines V.

The gradient of V with respect to controller parameters can be derived from the Bellman equations. Let L = I − γP be the matrix defining the linear system LV = r (where r is the expected reward vector and P encodes the transition and controller dynamics). Then:

where θ represents any controller parameter (ψ_a,x or η_x',x,a,o). This can be computed efficiently by: (1) solving LV = r for V (forward pass), (2) computing the right-hand side, (3) solving L^⊤λ = c for an adjoint vector (backward pass). The full gradient costs O(2 · |X||S| linear system solve).

Chapter 7: SHOWCASE — FSC Running Live

Watch a finite state controller execute on the crying baby POMDP over 50 steps. The controller's internal node is shown as the active node in the graph. You can see how the controller responds to crying vs. quiet observations, feeding when appropriate and listening to gather information. Compare with the belief-based policy: both make similar decisions, but the controller never computes a probability.

Chapter 8: Connections

Finite state controllers sit at the intersection of several important areas. Understanding these connections reveals when FSCs are the right tool and when to use something else.

Chapter 9: Summary

Finite state controllers offer a compelling alternative to belief-based POMDP policies. Here's the complete picture of what we covered: