2.997 Decision Making in Large Scale Systems, Lecture Note 16

2.997 Decision-Making in Large-Scale Systems April 5 Handout #20 Lecture Note 16 1 Linear Programming Approach to DP In previous lectures on dynamic programming, we have studied the value and policy iteration algorithms for solving Bellman’s equation. We now introduce a different algorithm, which is based on formulating the dynamic programming problem as a linear program. Consider the following optimization problem: cT J maxJ subject to (1) T J ≥ J, and suppose that vector c is strictly positive: c > 0. Recall the following lemma from Lecture 3: Lemma 1 For any J such that T J ≥ J, we have J ≤ J ∗ . It follows from the previous lemma that, whenever c > 0, J ∗ is the unique solution to problem (1). We refer to this problem as the exact LP. Note however that, strictly speaking, this problem is not a linear program; in particular, the constraints (T J)(x) ≥ J(x) ( min ga (x) + α a (2) X y Pa (x, y)J(y) ) ≥ J(x) are not linear in the variables J of the LP. However, (1) can easily be converted into an LP by noting that each constraint (2) is equivalent to X ga (x) + α Pa (x, y)J(y) ≥ J(x), ∀a ∈ Ax . y Note that the exact LP contains as many variables as the number of states in the system, and as many constraints as the number of state-action pairs. 1.1 Dual Linear Programming We can also find an optimal policy by solving the dual of the exact LP. For simplicity, we will consider average-cost problems in this section, but the analysis and underlying ideas easily extend to the discountedcost case. The dual LP has an interesting interpretation, and it can be shown that solving it iteratively via simplex or interior-point methods is equivalent to performing specific forms of policy iteration. 1 In the average-cost case, it can be shown that the dual LP is given as follows: X µ(x, a)ga (x) minµ (3) µ(x, a), ∀ x (4) x,a subject to XX y X µ(y, a)Pa (y, x) = X a a µ(x, a) = 1 x,a µ(x, a) ≥ 0, ∀ x, a For simplicity, let us assume that the system is irreducible under every policy. In order to analyze the dual LP, we consider the notion of randomized policies. So far, we have defined a policy to be a mapping from states to actions; in other words, for every state x a policy u prescribes a (deterministic) action u(x) ∈ A§ . Alternatively, we can consider an extended definition where, for any state action, a policy u prescribes a probability u(x, a) for taking each action a ∈ A x . Each policy u is now associated with a transition matrix Pu such that X Pu (x, y) = u(x, a)Pa (x, y), a and yields a stationary state distribution πu , which is the unique solution to πuT Pu = πuT X πu (x) = 1 x πu (x) ≥ 0. We can also verify that the state costs associated with policy u are given by X u(x, a)ga (x). gu (x) = a With these notions in mind, it can be shown that the variables µ(x, a) for any feasible solution to the dual LP can be interpreted as state-action frequencies for a randomized policy. Indeed, let X π(x) = µ(x, a), (5) a and u(x, a) = µ(x, a) , π(x) (6) if π(x) > 0, and u(x, ·) be an arbitrary distribution over Ax , otherwise. Note that in either case we have µ(x, a) = π(x)u(x, a), and u(x, a) is a randomized policy. Then we can show that π corresponds to the stationary state distribution P πu , and x,a µ(x, a)ga (x, a) corresponds to the average cost λu of policy u. Lemma 2 For every feasible solution µ(x, a) of the dual LP, let π(x) and u(x, a) be given by (??) and (6). P Then π = πu , and x,a µ(x, a)ga (x) corresponds to the average cost λu of policy u. 2 Proof: Consider constraints (4). Then we have XX X µ(y, a)Pa (y, x) = µ(x, a) y a XX y a π(y)u(y, a)Pa (y, x) = π(x) a X π(y)Pu (y, x) = π(x). y We also have π(x) ≥ 0 for all x, and X π(x) XX = x x = µ(x, a) a 1. We conclude that π is a stationary distribution associated with policy u. Since by assumption the system is irreducible under every policy, each policy has a unique stationary distribution, and we have π = π u . We now have X XX µ(x, a)ga (x) = πu (x)u(x, a)ga (x) x,a x = X a πu (x)gu (x) x = λu . 2 From the previous lemma, we conclude that each feasible solution of the dual LP is identified with a policy u, and the variables µ(x, a) correspond to the probability of observing state x and action a, in steady state. Consider using simplex or an interior-point method for solving the dual LP. Either method will generate a sequence of feasible solutions µ0 , µ1 , . . . , with decreasing value of the objective function. Interpreting this sequence with Lemma 2, we see that this is equivalent to generating a sequence of policies u 0 , u1 , . . . , with decreasing average cost, and solving the LP corresponds to performing policy iteration. 2 Approximate Linear Programming With an aim of computing a weight vector r̃ ∈ J ~ Φr J(1) J = Φr Figure 1: Graphical interpretation of approximate linear programming to make guesses about which states are desirable and therefore more likely to be visited often by reasonable policies, and which ones are typically avoided and rarely visited. We expect structures enabling this kind of procedure to be reasonably common in large-scale problems, in which desirable policies often exhibit some form of “stability,” guiding the system to a limited region of the state space and allowing only infrequent excursions from this region. 3 Approximation Error Analysis For the approximate LP to be useful, it should deliver good approximations when the cost-to-go function is near the span of selected basis functions. Figure 1 illustrates the issue. Consider an MDP with states 1 and 2. The plane represented in the figure corresponds to the space of all functions over the state space. The shaded area is the feasible region of the exact LP, and J ∗ is the pointwise maximum over that region. In the approximate LP, we restrict attention to the subspace J = Φr. In Figure 1, the span of the basis functions comes relatively close to the optimal cost-to-go function J ∗ ; if we were able to perform, for instance, a maximum-norm projection of J ∗ onto the subspace J = Φr, we would obtain the reasonably good approximate cost-to-go function Φr ∗ . At the same time, the approximate LP yields the approximate cost-to-go function Φr̃. In this section, we develop bounds guaranteeing that Φr̃ is not too much farther from J ∗ than Φr ∗ is. Note that, in general, we cannot guarantee that Φr̃ will be close to J ∗ , regardless of how close Φr ∗ is; for instance, Figure 2 illustrates a worst-case scenario, where even though Φr ∗ is close to J ∗ , the approximate LP does not even have a feasible solution. However, the following theorem shows that, with some mild conditions on the basis functions, a bound relating the distance between J ∗ and Φr ∗ to the distance between J ∗ and Φr̃ can be developed. Theorem 2 If Φv = e1 for some v, then we have kJ ∗ − Φr̃k1,c ≤ 1 Φv 2 min kJ ∗ − Φrk∞ . 1−α r = e means 5 State 2


































































 
  


































































 
   
























































































































































































































































































































T
J 

≥ 

J





































































































































































































































































































 J∗ No feasible Φr̃ Figure 2: A Special Case of ALP Before proving Theorem 2, we state and prove the following auxiliary lemma: Lemma 4 For all J, let 1+α J˜ = J − kJ − J ∗ k∞ e 1−α Then, we have T J˜ ≥ J˜ Proof: Let ² = kJ − J ∗ k∞ . Thus we have 1+α T J˜ = T (J − ²e) 1−α ∗ kT J − T J k∞ ≤ αkJ − J ∗ k∞ = α² 6 J = Φr Φr∗ State 1 Then T J˜ ≥ ≥ = = α(1 + α) ²e 1−α α(1 + α) ²e J − (1 + α)²e − 1−α α(1 + α) 1+α ²e − (1 + α)²e − ²e J˜ + 1−α 1−α ˜ J. J ∗ − α² − 2 We are now ready to finish the proof of Theorem 2. Let r ∗ = arg minr kJ ∗ − Φrk∞ . Let ² = kJ ∗ − Φr∗ k∞ . Then by Lemma 4, we have 1+α Φr̄ = Φr∗ − ²e 1−α is a feasible solution for the ALP. From Lemma 3, we have kJ ∗ − Φr̃k1,c ≤ = ≤ ≤ ≤ = kJ ∗ − Φr̄k1,c 1+α ²ek1,c 1−α 1+α ² kJ ∗ − Φr∗ k1,c + 1−α 1+α kJ ∗ − Φr∗ k∞ + ² 1−α 1+α ²+ ² 1−α 2 ² 1−α kJ ∗ − Φr∗ − 2 Theorem 2 establishes that when the optimal cost-to-go function lies close to the span of the basis functions, the approximate LP generates a good approximation. In particular, if the error min r kJ ∗ − Φrk∞ goes to zero (e.g., as we make use of more and more basis functions) the error resulting from the approximate LP also goes to zero. Though the above bound offers some support for the linear programming approach, there are some significant weaknesses: 1. The bound calls for an element of the span of the basis functions to exhibit uniformly low error over all states. In practice, however, minr kJ ∗ − Φrk∞ is typically huge, especially for large-scale problems. 2. The bound does not take into account the choice of state-relevance weights. As demonstrated in the previous section, these weights can significantly impact the approximation error. A sharp bound should take them into account. In the next lecture, we will show how the previous analysis can be generalized to take into account structure about the underlying MDP and address the aforementioned issues. 7