advertisement

Ses #16 2.997 Decision­Making in Large­Scale Systems MIT, Spring 2004 Handout #20 Problem Set 4 1. Consider an MDP where actions A are vectors (A1 , . . . , An ) ∈ An , for some set A. Therefore in each time stage the number of actions to be considered is exponential in the number n of action variables. Show that this MDP can be converted into an equivalent one with A actions in each time stage but a larger state space. (This problem shows that complexity in the action space can be traded for complexity in the state space, which is addressed by value function approximation methods.) 2. Show that the VC dimension of the class of rectangles in �d is 2d. 3. Another value function approximation algorithm based on temporal diﬀerences is called λ least squares policy evaluation (λ­LSPE). We successively approximate the cost­to­go function J ∗ by J ∗ ≈ Φrk , k = 1, 2, . . . . Recall that φ(x) is the row vector whose ith entry corresponds to φi (x). Deﬁne the temporal diﬀerence relative to approximation rk : dk (x, y) = g(x) + αφ(y)rk − φ(x)rk . Then λ­LSPE updates rk based on r̃k = argmin r rk+1 k � � φ(xm )r − φ(xm )rk − m=0 k � �2 l−m (αλ) dk (xl , xl+1 ) l=m = rk + γ(r̃k − rk ). The updates can be rewritten recursively as rk+1 = rk + γBk−1 (Ak rk + bk ), where Bk = k � φ(xm )φ(xm )� , m=0 Ak = k � zm (αφ(xm+1 ) − φ(xm )), m=0 bk zm = = k � zm g(xk ), m=0 m � (αλ)m−l φ(xl ). l=0 (a) Show that lim EAk k→∞ lim Ebk k→∞ lim EBk k→∞ T = A = Φ D(αP − I) ∞ � (αλP )m Φ, m=0 = b = ΦT D ∞ � m=0 = B = ΦT DΦ. 1 (αλP )m g, , (b) It can actually be shown that Ak /k → A, bk /k → b and Bk /k → B, with probability 1, and rk converges to r = −A−1 b. Compare r with the limiting value of rk achieved by TD(λ). (c) The main disadvantage of λ­LSPE is that it requires inverting matrix Bk in each iteration. Note that Bk ∈ �p×p , where p is the number of basis functions. However, there is an eﬃcient incre­ mental scheme for inverting Bk which only requires explicitly inverting scalars in each iteration. i. (Matrix Inversion Lemma) Show that, for all matrices M and N , (I + M N )−1 = I − M (I + N M )−1 N. ii. Propose an iterative scheme for computing Bk that only requires scalar inversion on all iterations k = 2, 3, . . . (assume that Bk is invertible for every k). 2