ECE 555 Control of Stochastic Systems Fall 2005 Handout: Reinforcement learning

In this handout we analyse reinforcement learning algorithms for Markov decision processes. The reader is referred to [2, 10] for a general background of the subject and to other references listed below for further details. This handout is based on [5]. Stochastic approximation In lecture on November 29th we considered the general stochastic approximation recursion, θ(n+ 1) = θ(k) + an[g(θ(n)) + ∆(n+ 1)], n ≥ 0, θ(0) ∈ R d. (1) Here we provide a summary of the main results from [5]. Associated with the recursion (1) are two O.D.E.s, d dt x(t) = g(x(t)) (2) d dt x(t) = g∞(x(t)), (3) where g ∞ : R d → Rd is the scaled function, lim r→∞ r−1g(rx) = g∞(x), x ∈ R d. We assumed in lecture that this limit exists, along with some additional properties, (A1) The function g is Lipschitz, and the limit g∞(x) exists for each x ∈ R d. Furthermore, the origin in Rd is an asymptotically stable equilibrium for the O.D.E. (3). (A2) The sequence {∆(n) : n ≥ 1} is a martingale difference sequence with respect to Fn = σ(θ(i),∆(i), i ≤ n). Moreover, for some σ2 ∆ < ∞ and any initial condition θ(0) ∈ R d, E[‖∆(n + 1)‖2 | Fn] ≤