Forward Induction

341. 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 $𝑠_{0}$ .

341.1. Setup

Define $𝑉_{𝑡} (𝑠)$ = minimum cost to reach state $𝑠$ at stage $𝑡$ from the start state $𝑠_{0}$ .

Base case:

𝑉_{0} (𝑠_{0}) = 0, 𝑉_{0} (𝑠) = + \infty for 𝑠 \neq 𝑠_{0}

Inductive step: to land at $𝑠^{'}$ at stage $𝑡 + 1$ , you must come from some predecessor $𝑠$ at stage $𝑡$ and choose action $𝑎$ with $𝑓_{𝑡} (𝑠, 𝑎) = 𝑠^{'}$ :

𝑉_{𝑡 + 1} (𝑠^{'}) = min_{(𝑠, 𝑎) : 𝑓_{𝑡} (𝑠, 𝑎) = 𝑠^{'}} {𝑉_{𝑡} (𝑠) + 𝑐_{𝑡} (𝑠, 𝑎)}

Optimal value: ${min}_{𝑠} [𝑉_{𝑇} (𝑠) + 𝑐_{𝑇} (𝑠)]$ .

341.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: $𝑂 (𝑇 | 𝒮︀ | | 𝒜︀ |)$ .

341.3. Backward vs forward

	Backward	Forward
Variable	$𝐽_{𝑡} (𝑠)$ = cost-to-go from $𝑠$	$𝑉_{𝑡} (𝑠)$ = cost-to-arrive at $𝑠$
Direction	$𝑇 \to 0$	$0 \to 𝑇$
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.

341.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).

341.5. When forward is the right choice

Single source, all-targets: e.g., shortest paths from $𝑠_{0}$ to every other node
Streaming or layered processing: data arrives stage by stage, can’t see the end
Predecessor tracking is natural: reconstruct paths via pred[t][s]

341.6. See also

Backward Induction — dual
Bellman Equation
Dijkstra — forward DP with priority queue
Bellman-Ford — forward DP, handles negative edges