Tabular Q-learning on an explicit finite MDP

The boxed algorithm of Sutton and Barto (2018), Section 6.5, p. 131, with the update of their eq. 6.8: \(Q(S,A) \leftarrow Q(S,A) + \alpha [R + \gamma \max_a Q(S',a) - Q(S,A)]\) with epsilon-greedy behaviour. Convergence to the optimal action values is the theorem of Watkins and Dayan (1992). Q(terminal, .) stays 0. Determinism conventions, mirrored bit-exactly against the Python arm: greedy ties break to the lowest action index; each step consumes, in order, one uniform for the epsilon test, one for the uniform action when exploring (floor of u times A), one for the next-state draw by inverse CDF on the transition row, all from the shared SplitMix64 stream.

Usage

Qlearn(
  P,
  R,
  gamma,
  alpha = 0.1,
  epsilon = 0.1,
  n_episodes = 100L,
  start = 0L,
  terminal = integer(0),
  max_steps = 1000L,
  seed = 0,
  Q0 = 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.
alpha: Step size in 0 to 1.
epsilon: Exploration probability.
n_episodes: Number of episodes.
start: 0-based start state.
terminal: Integer vector of 0-based absorbing terminal states.
max_steps: Step cap per episode.
seed: SplitMix64 seed.
Q0: Optional (S, A) initial action values.

Value

List with estimate (the learned (S, A) Q table), policy (0-based greedy actions), v, n_steps, n_episodes, method.

References

Sutton, R. S. and Barto, A. G. (2018). Reinforcement Learning: An Introduction, 2nd ed., MIT Press, Section 6.5, boxed algorithm p. 131, eq. 6.8. Watkins, C. J. C. H. and Dayan, P. (1992). Q-learning. Machine Learning 8, 279-292.

Examples

P <- list(matrix(c(0, 1, 0, 1), 2, byrow = TRUE))
R <- matrix(c(1, 0), 2)
Qlearn(P, R, 0.9, alpha = 0.5, epsilon = 0, n_episodes = 3,
       terminal = 1L)$estimate
#>       [,1]
#> [1,] 0.875
#> [2,] 0.000