Value iteration with the Bellman contraction audited — morie_bellman

For rewards r (states by actions), transitions p (an array states by actions by states) and discount gamma, the Bellman operator contracts the sup norm by gamma (Research.P4.Bellman.bellman_lipschitz) and has a unique fixed point (optimal_value_exists_unique), found by iteration. The greedy three-state example is returned by morie_myopic_example.

Usage

morie_bellman_value(r, p, gamma, iter = 1000L, tol = 1e-10)

Arguments

r: Reward matrix.
p: Transition array.
gamma: Discount in [0, 1).
iter, tol: Iteration cap and tolerance.

Value

A list: value, policy, iterations, contraction_ratio (largest observed step ratio, at most gamma) and converged.

References

Puterman ML (1994). Markov Decision Processes, Theorem 6.2.3. Wiley.

Examples

r <- matrix(c(1, 0.5, 1, 0, 0.5, 1), nrow = 3)
p <- array(0, c(3, 2, 3)); p[1, 1, 2] <- 1; p[1, 2, 3] <- 1
p[2, , 2] <- 1; p[3, , 3] <- 1
morie_bellman_value(r, p, gamma = 0.9)
#> $value
#> [1]  9  5 10
#> 
#> $policy
#> [1] 2 1 1
#> 
#> $iterations
#> [1] 220
#> 
#> $contraction_ratio
#> [1] 0.9
#> 
#> $converged
#> [1] TRUE
#> 
#> attr(,"theorem")
#> [1] "Research.P4.Bellman.bellman_contracting"