Dynamic programming and model-based control

When the transition model and reward function of an MDP are known, the Bellman equations can be solved by computation rather than by trial and error. The family of methods that does this is called dynamic programming. It matters to robot learning for three reasons. It gives the cleanest view of what reinforcement learning algorithms are trying to approximate. It connects reinforcement learning to the optimal control you met in ROB-300, where the linear quadratic regulator turns out to be dynamic programming for a special class of problems. And it is the core of model-based reinforcement learning, in which a robot learns a model of its dynamics from data and then plans with it.

Value iteration

Value iteration starts with an arbitrary value estimate, often all zeros, and repeatedly applies the Bellman optimality equation as an update to every state:

Each sweep is called a Bellman backup. Because the update is a contraction when \( \gamma < 1 \), the error shrinks by at least a factor of \( \gamma \) on every sweep, so the estimates converge to \( V^* \) from any starting point. After convergence, the optimal policy is read off by choosing the action that achieves the maximum in each state. In practice, iteration stops when the largest change in any state's value falls below a small tolerance.

A useful way to see value iteration is as information spreading outwards from rewarding states. After one sweep, only states adjacent to the goal know that the goal is nearby. After \( k \) sweeps, states up to \( k \) steps away have useful values. This is why sparse, distant rewards make learning slow: information about success has to propagate through many states.

# Value iteration on a 4x4 gridworld with slippery moves
import numpy as np
n, gamma, slip = 4, 0.95, 0.1
goal, trap = (0, 3), (1, 3)
moves = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
def step(s, d):
    r, c = s[0] + d[0], s[1] + d[1]
    return (r, c) if 0 <= r < n and 0 <= c < n else s
def reward(s2):
    return 10.0 if s2 == goal else (-10.0 if s2 == trap else -0.4)
V = np.zeros((n, n))
for sweep in range(1, 200):
    Vn = V.copy()
    for r in range(n):
        for c in range(n):
            s = (r, c)
            if s in (goal, trap):
                continue
            best = -1e9
            for a, d in moves.items():
                # intended move with prob 1-slip, otherwise stay put
                q = 0.0
                for d2, p in ((d, 1 - slip), ((0, 0), slip)):
                    s2 = step(s, d2)
                    q += p * (reward(s2) + gamma * (0 if s2 in (goal, trap) else V[s2]))
                best = max(best, q)
            Vn[s] = best
    delta = np.abs(Vn - V).max(); V = Vn
    if delta < 1e-6:
        break
print("sweeps to converge:", sweep)
print(np.round(V, 2))

sweeps to converge: 16
[[7.98 8.91 9.9  0.  ]
 [7.09 7.98 8.91 0.  ]
 [6.26 7.09 7.98 7.09]
 [5.47 6.26 7.09 6.26]]

Policy iteration

Policy iteration alternates two steps. Policy evaluation computes \( V^\pi \) for the current policy, either by solving the linear Bellman expectation equations directly, as in lesson 2, or by iterating them. Policy improvement then makes the policy greedy with respect to that value function. The policy improvement theorem guarantees that the new policy is at least as good as the old one in every state, and strictly better unless the old policy was already optimal. Because a finite MDP has finitely many deterministic policies, policy iteration terminates, usually in surprisingly few iterations, often fewer than ten even for large problems.

Value iteration and policy iteration sit at two ends of a spectrum. Value iteration does one cheap backup per state before improving; policy iteration evaluates the policy completely before improving. Generalized policy iteration describes any scheme that interleaves partial evaluation and improvement, and almost every reinforcement learning algorithm in lessons 4 and 5 fits that description: actor-critic methods, for example, keep improving a policy (the actor) against an imperfect but steadily updated value estimate (the critic).

The curse of dimensionality

Dynamic programming over a table of states works beautifully for gridworlds and fails badly for robots. A seven-joint arm with positions and velocities has a 14-dimensional state. Discretizing each dimension into just 20 values gives \( 20^{14} \approx 1.6 \times 10^{18} \) states, far beyond any computer's memory. Richard Bellman, who introduced dynamic programming in the 1950s, called this the curse of dimensionality.

There are three main escapes. One is to exploit structure, as LQR does, so that the value function has a closed form. Another is to represent value functions and policies with function approximators, such as neural networks, that generalize across similar states; this is the basis of deep reinforcement learning. The third is to plan only locally, around the robot's current state and over a short horizon, as model-predictive control does, rather than computing a global policy for every possible state.

Dynamic programming meets optimal control: LQR

ROB-300 introduced the linear quadratic regulator for systems with linear dynamics \( x_{t+1} = A x_t + B u_t \) and quadratic cost \( x^\top Q x + u^\top R u \). LQR is dynamic programming in disguise. Because the dynamics are linear and the cost quadratic, the optimal value function is itself quadratic, \( V(x) = x^\top P x \), and the Bellman equation becomes a matrix equation for \( P \): the discrete-time Riccati equation. Iterating it backwards from the final time step is exactly value iteration, carried out on a function rather than a table:

The optimal action is linear feedback, \( u = -K x \), with \( K = (R + B^\top P B)^{-1} B^\top P A \). This connection is worth remembering. When a robot's dynamics are close to linear around an operating point and the task can be written as a quadratic cost, LQR gives the optimal policy immediately, with no learning at all. Reinforcement learning earns its keep when dynamics are nonlinear, contact-rich or unknown, and when the reward is not quadratic.

# LQR as value iteration: scalar system x' = a x + b u, cost q x^2 + r u^2
a, b, q, r = 1.1, 0.5, 1.0, 0.1   # unstable open loop (a > 1)
P = 0.0
for k in range(1, 100):
    Pn = q + a * P * a - (a * P * b) ** 2 / (r + b * P * b)
    if abs(Pn - P) < 1e-10:
        break
    P = Pn
K = (b * P * a) / (r + b * P * b)
print(f"iterations: {k}, P = {P:.4f}, K = {K:.4f}")
print(f"closed-loop pole a - bK = {a - b*K:.4f} (stable if |.| < 1)")
x, cost = 1.0, 0.0
for t in range(20):
    u = -K * x
    cost += q * x * x + r * u * u
    x = a * x + b * u
print(f"simulated cost from x0=1: {cost:.4f}  vs  V(x0) = P = {P:.4f}")

iterations: 10, P = 1.3749, K = 1.7042
closed-loop pole a - bK = 0.2479 (stable if |.| < 1)
simulated cost from x0=1: 1.3749  vs  V(x0) = P = 1.3749

Model-based reinforcement learning

Dynamic programming needs a model. In model-free reinforcement learning, covered in lessons 4 and 5, the agent learns values or policies directly from experience without ever building a model. In model-based reinforcement learning, the agent uses its experience to learn a dynamics model \( \hat{f}(s, a) \approx s' \) and then uses that model to plan or to generate extra training data. The appeal for robots is data efficiency: a model can be queried many times at no physical cost, so each real interaction teaches more.

A common pattern combines a learned model with model-predictive control. At each control step, the robot uses the model to simulate many candidate action sequences over a short horizon, scores them with the reward function, executes the first action of the best sequence, observes the result and repeats. Sampling-based optimizers such as the cross-entropy method or model-predictive path integral control are popular because they need no gradients through the model. The new data are added to the training set, and the model is periodically retrained.

The danger is model error. A planner will find and exploit any place where the model is wrong in its favor, such as a predicted shortcut through a wall that does not exist in reality. Practical systems reduce this by keeping planning horizons short, re-planning at every step, training an ensemble of models and treating their disagreement as uncertainty to be avoided, and collecting more data in exactly the places where the model is uncertain. Learned world models, which predict future observations from images, extend these ideas to high-dimensional inputs and return in lesson 10.

When dynamic programming is enough

For many industrial problems, dynamic programming in one of its forms is the complete answer. Grid-based path planners in ROB-350, such as Dijkstra and A*, are dynamic programming on deterministic graphs. LQR and its nonlinear extensions handle balancing and trajectory tracking. Discrete scheduling problems, such as choosing the order of picks in a bin, can often be solved exactly. The lessons that follow assume you reach for learning only when the model is unknown, too expensive or too inaccurate, and they repeatedly borrow dynamic programming ideas: Bellman backups, generalized policy iteration and planning with models.