Performance Analysis of Online Anticipatory Algorithms for Large Multistage Stochastic Integer Programs

1 Introduction

Online stochastic algorithms for solving large multistage stochastic integer programs have attracted increasing interest in recent years. They are motivated by applications in which different types of requests arrive dynamically, and it is the role of the algorithm to decide which requests to serve and how. Unlike traditional online algorithms, these applications assume that the uncertainty is stochastic and that distributions of the requests are given.

Consider the packet scheduling problem from [Chang et al., 2000]. A router receives a set of packets at each time step and must choose which packet to serve. Packets can be served only for a limited time and they are characterized by a value. The goal is to maximize the values of the served packets. The packet distributions are specified by Markov models whose states specify arrival frequencies for the packet type.

Online reservation systems [Benoist et al., 2001] are another such application. Customers place requests in real time for some service at a fixed date. The resources are modeled by a multiknapsack constraint. (Think of tour operators requesting rooms in hotels for a group: the choice of a specific hotel is not pertinent for the group but all group members must be allocated to the same hotel). Customers must be immediately notified of acceptance or rejection of their requests, and accepted requests must be satisfied. Accepted requests must also be assigned to a specific resource at reservation time and this choice cannot be reconsidered. The goal is to maximize the profit of the served requests which come from different types with different characteristics and arrival frequencies.

Online multiple vehicle routing with time windows [Bent and Van Hentenryck, 2003] captures an important class of applications arising in transportation and distribution systems. In these problems, a fleet of vehicles serve clients which are located in many different locations and place request for service in real-time in specific time windows. Clients must be immediately notified of acceptance or rejection of their requests, and all accepted requests must be satisfied. Routing decisions however can be delayed if necessary. The goal is to maximize the number of satisfied requests.

All these problems share several characteristics. First, they can be modeled as multistage integer stochastic programs. Second, the number of stages is large. In packet scheduling, time is discrete by nature, and experiments were made with 200,000 stages. For the two other applications, time is continuous but a reasonable discretization of time would require 200 stages. Third, the set of feasible decisions at each stage is finite. Finally, these applications require fast decision-making. These characteristics prohibit the use of a priori methods for (Partially Observable) Markov Decision Processes and for Stochastic Programs. Indeed, [Chang et al., 2000] and [Benoist et al., 2001] have shown that (PO)MDPs do not scale on these applications. Moreover, successful algorithms for 2-stage stochastic optimization, such as the Sample Average Approximation method, are shown to require a number of samples exponential in the number of stages [Shapiro, 2006], precluding their use on these applications.

Interestingly, high-quality solutions to these applications have been obtained by online algorithms that relax the nonanticipativity constraints in the stochastic programs. These online anticipatory algorithms make decisions online at a time t in three steps:

1. sample the distribution to obtain scenarios of the future;
2. optimize each scenario for each possible decision;
3. select the best decision over all scenarios.

It is clear that this strategy is necessarily suboptimal, even with many scenarios. However, experimental results have been surprisingly good, especially with the Regret algorithm [Bent and Van Hentenryck, 2004; Hentenryck et al., 2006] which is an efficient way of implementing step 2. Our goal in this paper is to demystify these results by providing a theoretical analysis of these algorithms. Section 2 describes the model and the algorithm. Section 3 analyses the performance of the online anticipatory algorithm and isolates two fundamental sources of error: a sampling error and a quantity called the global anticipatory gap which is inherent to the problem. Section 4 shows how to bound the anticipatory gap theoretically and experimentally. Section 5 analyzes the effect of approximating the optimization problem. Section 6 compares the anticipatory gap to the expected value of perfect information. Section 7 presents directions for future research.

2 Model and Algorithm

We consider finite stochastic integer programs of the form

where ξ is a stochastic process, with ξt being the observation at time t, (with ξ1 being deterministic), st = (x1..t-1, ξ1..t) is the state at time t, X maps states to non-empty subsets of a finite set X of decisions (so the max's are well-defined), and f is the utility function bounded by Fmax. We denote respectively x and ξ the vectors x1..T and ξ1..T .

A decision process is a stochastic process x such that ∀t : xt ∈ X (st). We can assume that the computation of each xt requires exactly one random variable γt. These variables are independent and independent of ξ.

In practice, decisions cannot be made based on future observations. A decision process x is non-anticipative if xt is a deterministic function of γ1..t and ξ1..t (that is, if x is adapted to the filtration Ft = σ(γ1..t, ξ1..t)). We can rewrite the stochastic program as

A scenario is a realization of the process ξ. The offline problem is the problem a decision maker would face if, in a given state st, the future observations are revealed; we define

Note that these two problems are deterministic.

Finally, the expected value of the clairvoyant (EVC) is defined as the expected utility of a clairvoyant decision maker, that is, EVC = E [O(s 1 , ξ)]. The problems discussed in the introduction all fit in this model: in particular, the utility is bounded thanks to capacity constraints. The model can also be generalized to the case in which f(x, ξ) has finite first and second moments for every x.

The anticipatory algorithm studied here is Algorithm MakeDecision, parametrized by the number of scenarios m, whose successive decisions form a non-anticipative process:

Function MakeDecision(st, γt)

3 Analysis of the Anticipatory Algorithm

We compare the performance of the anticipatory algorithm with the offline, a posteriori solution in the expected sense, as is typically done in online algorithms [Borodin and El-Yaniv, 1998]. In other words, for the decision process x produced by the anticipatory algorithm, we bound EVC - E [f (x , ξ)], which we call the expected global loss (EGL).

3.1 Local and Global Losses

We first show that the EGL is the sum of the expected losses of the stages.

Definition 1 Let st be a state. The expected local loss of decision x ∈ X (st) is defined as

Note that conditioning on a state st does not provide any information on γt: when reading an expression of the form E [. . . |st], keep in mind that there is uncertainty on ξt+1, . . . , ξT and on γt, . . . , γT .

Lemma 1 (Global Loss = Sum of Local Losses) For any decision process x,

Proof. Let Ct be the random variable O(st, xt, ξ) and At = E [Ct - f(x, ξ)]. Then AT = 0 and, for t < T ,

The last equality comes from decomposing and re-assembling amongst all possible values of xt. Finally EVC - E [f (x , ξ)] = E [C 0 - f (x , ξ)] = A 0 . ✷

3.2 Decomposition of the Local Loss

We now show that the local loss at a state st consists of a sampling error and the anticipatory gap.

Definition 2 The anticipatory gap of a state st is defined as

The choice error of x wrt st is defined as

The anticipatory gap is inherent to the problem and independent of the decision process x. An equivalent definition is

This expression shows that this gap can be interpreted as the cost of commuting of E and max. We now bound Δc(st, x).

Lemma 2 (Sampling Error) Let xt be computed by the anticipatory algorithm using m samples per decision. Let st be a state and x⋆ be argmax E [O(st, x, ξ) |st ] (break ties arbitrarily). Then

where σ(st, x) is the standard deviation of O(st, x, ξ) O(st , x⋆ , ξ) given st.

-

Proof. Here all probabilities and expectations are implicitly conditional on st. The left-hand side can be decomposed as

Due to the argmax in MakeDecision, the event xt = x implies ∀x′ ∈ X (st), g(x′ ) ≤ g(x). Therefore P (xt = x) ≤ P (g(x) ≥ g(x⋆ )). Since f is bounded, O(st, x, ξ) - O(st , x⋆ , ξ) has a finite expectation and variance. Now,

and, by the central limit theorem, this difference is normally distributed for m large enough, with mean -Δc(st, x) and variance 1m σ(st, x)2 . Finally, if X ∼ N (μ, σ2 ) with μ < 0, then P (X ≥ 0) ≤ exp (- μ2 2σ2 ) (Chernoff bound). ✷

3.3 Performance of the Algorithm

We now assemble the previous results.

Definition 3 The Global Anticipatory Gap of the problem is

Once again, this quantity is inherent to the problem.

Theorem 1 The expected global loss of the anticipatory algorithm satisfies

where m is the number of samples per decision and

Proof. We have

The termGAG comes from

and the global sampling error satisfies

An important consequence of this theorem is that the sampling error can be made smaller than some constant a by choosing m ≥ 1/K log (2/aT |X| Fmax). [Shapiro, 2006] argues that the SAA method does not scale to multistage problems, because the number of samples to achieve a given accuracy grows exponentially with T . The anticipatory algorithm only requires m to grow logarithmically with T |X|, which makes it highly scalable. Of course, it only produces highquality decisions when the anticipatory gap is small.

4 Bounding the Global Anticipatory Gap

This section provides theoretical and experimental results on the anticipatory gap, explaining why anticipatory algorithms are effective in the applications mentioned in the introduction.

4.1 Theoretical Proof on Packet Scheduling

We first show how to compute an upper bound on GAG for a simplified version of the packet scheduling problem. Suppose that there are k types of packets whose values are v1 < . . . < vk respectively. At each step from 1 to T - 1, a packet of type i arrives with probability pi. All these random variables are independent. Each packet has a lifetime of 2, meaning a packet received at time t can be scheduled either at time t or at time t+1. The utility is the sum of scheduled packets over the T stages. All packets take a single time step to serve. For convenience, we introduce a packet type 0 with value v0 = 0 and probability p0 = 1. It should be clear that this problem satisfies all assumptions above. In particular, the utility is bounded (0 ≤ f ≤ T vk).

Why is the GAG small on this problem? We show that Δg is rarely high, inducing a small GAG. For st a state and x, y ∈ X (st), we say that x dominates y if O(st, x, ξ) ≥ O(st, y, ξ) almost surely given st. Studying Δg(st) only requires to focus on non-dominated decisions: there are at most two non-dominated decisions for a given state, which consists of scheduling

• the most valuable packet, of type i, received at time t - 1 and not already scheduled; or
• the most valuable packet, of type j, received at time t.

Moreover, if i ≥ j, then choosing j is dominated, since i is more valuable and will be lost if not chosen now. Also, if i < j but the second most valuable packet received at t is of type k ≥ i, then choosing i is dominated. If one of these two conditions holds, a decision dominates all the other ones, and thus Δg(st) = 0.

Suppose now that st does not satisfy any of them. By the dominance property, scenarios can be partitioned into those where scheduling i (resp. j) is the unique offline, optimal decision and those on which there is a tie. Introduce the random variable yt, taking values i, j or ⊥ in these three respective cases. We then have

and symmetrically

Now, if i is scheduled and the optimal offline solution was to schedule j, then the loss cannot exceed vj - vi, since the rest of the optimal offline schedule is still feasible. Hence E [O(st, ξ) -O(st, i, ξ) |st, yt = j ] ≤ vj - vi. Moreover, for the optimal offline schedule to choose j at time t, it is necessary to have a packet of value greater than vi arriving at t+1 and thus P (yt = j) ≤ 1 - ∏k>i qk where qk = 1 - pk. Finally, we find

The other case is harder to study, but a trivial upper bound is Δ(st, j) ≤ vi. Now it remains to bound the expectation of Δg(st) = min(Δ(st, i), Δ(st, j)) by enumerating the possible values of i and j and weighting each case with its probability of occurrence. This weight is, in fact, bounded by the product of the probabilities of the 3 following events:

• a packet of type i arrived at time t - 1;
• the most valuable packet arrived at t is of type j;
• no packet of type i ≤ k < j arrived at time t.

Here is a numerical example. Suppose there are 4 types of packets, with the following values and emission probabilities:

The upper bound on Δg depending on i and j, is

We find that E [Δg(st)] ≤ .125. On the other hand, a simple lower bound on the EVC is the expectation of the value of the most valuable packet arriving at each stage multiplied by the number of stages. In this case, that leads to EVC ≥ 2.25T. As a result, the ratio of GAG over EVC on this problem is less than 5.55%. Because this analysis is not tight - especially the lower bound of the EVC-, the anticipatory algorithm is likely to have an even better expected global loss. This analysis also hints at why online anticipatory algorithms are so effective on packet scheduling and why they outperform competitive algorithms on these instances.

4.2 Discussion on Practical Problems

The previous section shows how to bound the GAG on a particular problem: study dominance properties between the decisions, bound the loss of making a non-optimal (in the offline sense) decision, and bound the probability of this event. We are currently applying this method on more complex problems but proofs quickly become very cumbersome. As an alternative, we discuss another, empirical way to argue that the GAG of a problem is small.

We have emphasized in the theoretical discussion the importance of bounding the probability that the chosen decision is not a posteriori optimal. We call P (O(st, xt, ξ) =O(st, ξ) |st ) the consensus rate. This quantity can be estimated easily during the computation of an anticipatory algorithm. It suffices to count howmany scenarios make the same decision, i.e.,

[Hentenryck et al., 2006] kindly gave us some of these statistics on online reservation systems: they depict the consensus rate (min/max/avg) as a function of the number of scenarios.

On this class of instances, there are 6 possible decisions in each state. Therefore, one could expect an average consensus rate of 20%, but it is actually much higher, at about 80%. Moreover the maximal offline loss of a bad decision can easily be bounded in this problem. By Markov inequality, the GAG is low. Similar observations were made in the packet scheduling problem, where the measured average consensus was about 90%, and in the vehicle routing problem, where the rate varies among the stages, exhibiting an increasing trend from 65 to 100%. This argument, however, would be useless when Fmax is high, e.g. problems with high penalty states.

More generally, the following theorem gives a way to measure the anticipatory gap of a state.

Theorem 2 Let st be a state. Define ̂Δg(st) as

then this is a strongly consistent estimator of Δg(st), i.e.,

Proof. Apply the strong law of large numbers to O(st, x, ξ) for all x and conclude with the finiteness of X (st). ✷

̂Δg can be computed by the online anticipatory algorithm at no additional cost.

5 Approximating the Offline Problem

Theorem 1 explains why the anticipatory algorithm provides good results when the GAG is small. However, practical implementations use a variant of Algorithm 1 in which O is replaced by a fast approximation ˜ O. This is the case for the three applications mentioned earlier which use an approximating technique called Regret [Bent and Van Hentenryck, 2004; Hentenryck et al., 2006]. The Regret algorithm can be seen as a discrete version of sensitivity analysis: instead of computing O(st, x, ξ) for each for each x ∈ X (st), the idea is to compute x∗ = argmaxx(O(st, x, ξi )) first and then to compute a vector of approximations ( ˜ O(st, x, ξi ))x∈X (st)

using x∗ . Each entry in this vector is derived by approximating the loss of selecting a specific x in X (st) instead of the optimal decision x∗ . As a result, the Regret algorithm ensures (i) ˜ O ≤ O and (ii) maxx( ˜ O(st, x, ξi )) = maxx(O(st, x, ξi )). See [Bent et al., 2005] for a discussion on the complexity of computing this approximated vector.

It is not easy to provide tight theoretical bounds on the expected global loss for the Regret approximation. We thus measured the empirical distribution of O - ˜ O on online stochastic reservation systems from [Hentenryck et al., 2006]. The difference O - ˜ O is zero in 80% of the cases and its mean is very small (around .2 while the typical values of O are in the range [400,500]), although it can occasionally be large. This intuitively justifies the quality of Regret, whose expected global loss is not significatively different from the anticipatory algorithm for the same sample size.

Finally, recall that, on online reservation systems, the consensus rate is very high on average. Let x⋆ = argmaxx ∑mi=1 O(st, x, ξi ) and let the consensus rate be α. By properties (i) and (ii) of Regret, the approximated "score" ∑mi=1 ˜ O(st, x⋆ , ξi ) of decision x⋆ may only exhibit errors in (1 - α)m scenarios and hence will be very close to ∑αm i=1 O(st , x⋆ , ξi ). Moreover, other decisions have an approximated score where (almost all) the terms of the sum has a negative error. Therefore the approximated decision is biased toward consensual decisions and a high consensus rate tends to hide the approximation errors O - ˜ O of Regret.

In summary, a high consensus rate not only makes the AG small but also allows Regret to produce decisions close in quality to the exact anticipatory algorithm. This does not mean that a brutal Regret approximation, e.g., assigning zero to each non-optimal decision, would be as effective [Bent and Van Hentenryck, 2004].

6 GAG Versus EVPI

This section studies the relationships between the anticipatory gap and the expected value of perfect information (EVPI ). Since these concepts are seemingly close, it is useful to explain how they differ and why we chose to introduce the notion of anticipatory gap.

Consider the following two maps assigning values to states: the offline value and the online value of state st, respectively denoted by φ(st) and π(st) and defined by

Note that φ(st) ≥ π(st) for all state st. The difference

is the (local) expected value of perfect information (EVPI ). The expected value of perfect information of the problem is η(s1), that is, the advantage, in the expected sense, of a clairvoyant over a non-clairvoyant (both with infinite computational resources). The next lemma relates the offline problem and φ and shows that the operators max and E commute for clairvoyant decision processes.

Proof. Let x⋆ be a decision process maximizing E [f(x, ξ)|st]. Then for all ξ, O(st, ξ) ≥ f(x⋆ , ξ), and, as E is non-decreasing, E [O(st, ξ)|st] ≥ E [f (x⋆ , ξ)|st)] = φ(st). Inversely, let xξ be a decision process maximizing f(x, ξ) with xξ1..t-1 = x1..t-1. Define x⋆ by aggregation: x⋆ does the same thing as xξ on the scenario ξ. Then φ(st) ≥ E [f (x⋆ , ξ)|st] = E [O(st, ξ)|st]. ✷

In two-stage stochastic programming, a low EVPI makes the problemmuch easier because an optimal decision is also a good one for each specific scenario [Birge and Louveaux, 1997, ch. 4]. However, this is no longer true in the multistage case. Consider the three-stage problem depicted in Figure 1. Black dots represent decisions variables x1 and x2. Stochastic variables ξ1 and ξ2 have no influence and are not represented. The white dot represents ξ3 which take values 0 and 1 with equal probability. Leaves are tagged with their utilities and a is large positive number. The value of the EVPI and the anticipatory gap Δg for each state are the following:

On this problem, the EVPI is ε: an optimal solution has a score of ε, whatever the scenario. The expected value of the optimal policy is zero. However, the online anticipatory algorithm always chooses x1 = 0 and thus has an expected utility of 1/2(ε - a). Therefore anticipatory algorithms may behave poorly even with a low EVPI . Moreover, in this case, the inequality of Theorem 1 is tight when m converges to +∞, since the GAG equals 1/2(ε + a).

The phenomenon comes from the fact that the EVPI of the problem is low although the EVPI of the node (x1 = 0) is ε - 1/2(ε - a) = 1/2(ε + a) and thus much larger. This does not contradict the super-martingale property of [Dempster, 1998] because Dempster considers optimal decision processes, which is not the case of anticipatory algorithms. As a result, the expected global loss of the anticipatory algorithm cannot be bounded by the root EVPI . The example may suggest that the maximum of the EVPIs at each node of the tree gives an upper bound of the EGL, but this is not true either. Figure 2 presents a stochastic program, where 'Sub' are clones of the problem in Figure 1, with variables indices shifted. On this problem, the optimal solutions to the scenarios have an expected expected utility of ε, and those of the anticipatory algorithm (with m = ∞) have expected utility 1/4(-3a+ε); the EGL thus equals 3/4(a+ε). By Theorem 1, the GAG is not smaller than the EGL (m = ∞: no sampling error). As a result, the GAG is greater than the maximum of the EVPI over all nodes, which is equal to 1/2(ε + a).

Finally, the following theorem gives one more reason why the concept of anticipatory gap is of interest.

Theorem 3 For any state st, we have η(st) ≥ Δg(st) and there exist cases in which the inequality is strict.

Proof. η(st) = φ(st) - π(st). Recall that π(st) is the optimal expected utility of a non-anticipative decision process given st. Because of non-anticipativity and because X (st) is finite, there exists an optimal decision x⋆ ∈ X (st) such that π(st) = E [π(st+1) |st, xt = x⋆ ]. Now

and thus, using lemma 3,

This proves the inequality. The second part of the theorem is proven by the example of Figure 1, on which the root node s1 satisfies η(s1) = ε > 0 = Δg(s1). ✷

7 Conclusion and Research Perspectives

Anticipatory algorithms have been shown experimentally to be successful in tackling a variety of large multistage stochastic integer programs which were outside the scope of a priori methods such as (PO)MDPs and multistage stochastic programming. This paper studied the performance of anticipatory algorithms in terms of their sampling error and the anticipatory gap of the problems. It showed that, whenever the anticipatory gap is small, anticipatory algorithms are scalable and provide high-quality solutions in the expected sense with a logarithmic number of samples in the problem size. The paper also studied how to bound the anticipatory gap both theoretically and experimentally, showing that a simple packet scheduling problem admits a small anticipatory gap and providing experimental evidence on several large multistage stochastic programs. Finally, the paper indicated that the anticipatory gap is an important concept and studied its relationships with the expected value of perfect information.

There are many research directions opened by this research. First, It is desirable to to deepen the understanding of the problem features (both combinatorial and statistical) which lead to small (or large) anticipatory gaps. Second, it is also important to study novel anticipatory algorithms for applications with non-negligible anticipatory gaps. Here an interesting direction is to borrow ideas from Real-Time Dynamic Programming [Barto et al., 1995; Paquet et al., 2005].

Indeed, because the estimation of φ(st) obtained by relaxing non-anticipativity constraints is an upper bound of its online value π(st) with high probability, a RTDP approach can produce increasingly tighter approximations of the optimal policy until decision time. Despite negative complexity results ([Kearns et al., 1999]), we believe that, if the GAG is not too large, high-quality decisions could be obtained in reasonable time. Indeed, since the far future is unlikely to be as important as the near future for the current decision, we may hope that small trees will be sufficient for many applications.

Acknowledgments

This research is partly supported by NSF Award DMI0600384 and ONR DEPSCOR Award N000140610607. Thanks to the reviewers for their interesting suggestions.