Policy iteration for a finite MDP

Alternates iterative policy evaluation, sweeps of \(V(s) \leftarrow \sum_{s'} P(s'|s,\pi(s)) [r + \gamma V(s')]\) until the largest change is below tol, with greedy policy improvement, stopping when the policy is stable. This is the boxed algorithm in Sutton and Barto (2018), Section 4.3, p. 80; policy iteration is due to Howard (1960). Ties break to the lowest action index and a state counts as stable when the incumbent action value is within 1e-12 of the maximum, which removes the tie-flipping non-termination of the literal box, per their Exercise 4.4.

Usage

Mdppol(
  P,
  R,
  gamma,
  tol = 1e-12,
  max_eval = 100000L,
  max_improve = 1000L,
  pi0 = 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

Policy-evaluation sweep threshold.

max_eval

Cap on evaluation sweeps per improvement round.

max_improve

Cap on improvement rounds.

pi0

Optional initial 0-based deterministic policy, length S.

Value

List with estimate (values of the final policy), policy (0-based actions), q, n_improve, n_eval, policy_stable, method.

References

Sutton, R. S. and Barto, A. G. (2018). Reinforcement Learning: An Introduction, 2nd ed., MIT Press, Section 4.3, boxed algorithm p. 80. Howard, R. A. (1960). Dynamic Programming and Markov Processes, MIT Press.

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)
Mdppol(P, R, 0.5)$policy
#> [1] 0 0