Value iteration for a finite Markov decision process

Repeats the Bellman optimality sweep V(s) <- max_a sum_s2 P(s2|s,a) [ r(s,a) + gamma V(s2) ] until the largest change in a sweep falls below tol, then returns the deterministic greedy policy with ties broken to the lowest action index (Sutton & Barto 2018, Sec. 4.4 boxed algorithm, p. 83).

Usage

morie_mdpval(P, R, gamma, tol = 1e-10, max_iter = 1e+05, V0 = NULL)

Arguments

P

List of A transition matrices, each (S, S), rows summing to 1; P[[a]][s, s2] = P(s2 | s, a).

R

Reward: (S, A) matrix of r(s, a), or a list of A (S, S) per-transition reward matrices averaged under P.

gamma

Discount factor.

tol

Sweep-change threshold.

max_iter

Maximum sweeps.

V0

Optional initial value vector.

Value

A list with elements estimate (V), policy (0-based actions), q, n_iter, delta, converged, method.

References

Sutton, R. S. and Barto, A. G. (2018). Reinforcement Learning: An Introduction, 2nd ed. MIT Press, Section 4.4.

Examples

morie_mdpval(P = 1, R = 5L, gamma = 0.5)
#> $estimate
#> [1] 10
#> 
#> $policy
#> [1] 0
#> 
#> $q
#>      [,1]
#> [1,]   10
#> 
#> $n_iter
#> [1] 37
#> 
#> $delta
#> [1] 7.275958e-11
#> 
#> $converged
#> [1] TRUE
#> 
#> $method
#> [1] "Value iteration (Bellman optimality sweeps) for a finite MDP"
#>