value iteration

We can rewrite the

Bellman Equation of the value function

$$\begin{array}{r}V(s)=\underset{a}{\max }\mathbb{E}(r+\gamma V(s^{\prime }))\end{array}$$

The value of a state equals the best immediate reward plus the discounted value of the next state.

Link to original

to this (literally the same thing, just making $a$ and $P$ explicit):

$$V(s)=\underset{a}{\max }\sum _{s^{\prime }}P(s^{\prime }\mid s,a)(R(s^{\prime },s,a)+\gamma V(s^{\prime }))$$

(If the MDP was deterministic, we could drop the sum)
We can initialize this value function/table poorly, and recursively / iteratively refine it.
Once that’s converged, we can extract the optimal policy:

$$\pi (s,a)=\arg \underset{a}{\max }\sum _{s^{\prime }}P(s^{\prime }\mid s,a)(R(s^{\prime },s,a)+\gamma V(s^{\prime }))$$

Here, we have to know the transition probabilities $P$, the next state $s^{\prime }$ and reward $R(s^{\prime },s,a)$, so this is model-based. We need some explicit model of the environment that tells us the expected next state and reward given the current state and action.

This is a type of dynamic programming. Given perfect information about the environment, we can find the optimal solution by DP. You can just code this algorithm up to solve low dimensional problems (e.g. tic tac toe), without neural nets.

# Given: states S, actions A(s), transition model P(s'|s,a), reward R(s',s,a), discount gamma in [0,1), tolerance theta
V = {s: 0.0 for s in S}			# arbitrary init; 0 works
while True:
	delta = 0.0
	for s in S:
		if is_terminal(s):
			V[s] = 0.0			 # nothing left to earn
			continue
		v_old = V[s]
		V[s] = max(
			sum(P(s2, s, a) * (R(s2, s, a) + gamma * V[s2]) for s2 in successors(s, a)) 
			for a in A(s)
		)
		delta = max(delta, abs(v_old - V[s]))
	if delta < theta:			  # largest change this sweep is tiny -> stop
		break
 
# Policy extraction: one more greedy step over the converged V
pi = {
	s: argmax(a in A(s),
			  sum(P(s2, s, a) * (R(s2, s, a) + gamma * V[s2])
				  for s2 in successors(s, a)))
	for s in S if not is_terminal(s)
}