338. Forward Induction

The dual of backward induction. Instead of computing the optimal cost-from each state, compute the optimal cost to arrive at each state from .

338.1. Setup

Define = minimum cost to reach state at stage from the start state .

Base case:

Inductive step: to land at at stage , you must come from some predecessor at stage and choose action with :

Optimal value: .

338.2. Algorithm

V[0][s₀] ← 0; V[0][s] ← ∞ for s ≠ s₀

For t = 0, 1, …, T-1:
    For each s ∈ S:
        For each action a ∈ A(s):
            s' ← f_t(s, a)
            cost ← V[t][s] + c_t(s, a)
            if cost < V[t+1][s']:
                V[t+1][s'] ← cost
                pred[t+1][s'] ← (s, a)  # for path reconstruction

Optimal value: min over s of (V[T][s] + c_T(s))
Trace back via `pred` to recover the optimal path.

Cost is the same as backward induction: .

338.3. Backward vs forward

Backward Forward
Variable = cost-to-go from = cost-to-arrive at
Direction
Best when Terminal cost known/small; want action at every state Starting state fixed; want best path to every state
Yields Optimal action at every Optimal path to every reachable state

Both compute the same optimum.

338.4. Example: shortest path on a DAG

The classic forward DP. Topologically sort the DAG; visit each node in order, computing as the minimum of over all predecessors .

This is exactly what Bellman-Ford / Dijkstra-on-DAGs does — see Dijkstra (which is a forward DP with priority-queue ordering).

338.5. When forward is the right choice

338.6. See also