Repeats the Bellman optimality sweep
\(V(s) \leftarrow \max_a \sum_{s'} P(s'|s,a) [r + \gamma V(s')]\)
until the largest change in a sweep drops below tol, then
outputs the deterministic greedy policy (ties to the lowest action
index). This is the boxed algorithm in Sutton and Barto (2018),
Section 4.4, p. 83, their eq. 4.10; the method originates with
Bellman (1957) and is Puterman (1994), Section 6.3.
Usage
Mdpval(P, R, gamma, tol = 1e-10, max_iter = 100000L, V0 = NULL)
Arguments
- P
List of A transition matrices, each (S, S) row-stochastic.
- R
Matrix (S, A) of expected rewards, or a list of A (S, S)
per-transition reward matrices averaged under P.
- gamma
Discount factor in 0 to 1.
- tol
Sweep-change threshold.
- max_iter
Cap on sweeps.
- V0
Optional initial value function, length S.
Value
List with estimate (optimal values), policy
(0-based greedy 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, boxed algorithm p. 83, eq. 4.10.
Bellman, R. (1957). Dynamic Programming, Princeton University Press. Puterman, M.
L. (1994). Markov Decision Processes, Wiley, Section 6.3.
Examples
P <- list(matrix(c(1, 0, 0, 1), 2, byrow = TRUE),
matrix(c(0, 1, 0, 1), 2, byrow = TRUE))
R <- matrix(c(1, 0, 0, 0), 2, byrow = TRUE)
Mdpval(P, R, 0.5)$estimate
#> [1] 2 0
