Engineered

Decision making under ambiguity by Etner, Jeleva and Tallon, Part 2

Here is the follow-up on my previous post on decision making under ambiguity. I stopped halfway through the section on non-Bayesian criteria with non-additive beliefs because the post had become humongous. Now the authors discuss how to determine the set of priors in the maxmin expected utility model. One formulation is called epsilon-contamination. "In this formulation, the decision maker has a probabilistic benchmark in the sense that he believes the probability distribution on the state space is a given distribution, say p. But he's not totally confident about this. The way to model this is to say that the set of priors he has in mind will be a combination between the 'probabilistic benchmark' on one hand and 'anything can happen' on the other hand." 

Hansen and Sargent (2001, 2008) also tackle model uncertainty using ideas inspired from robust control (something dear to my heart, since I studied control theory in college before moving on to operations research). In this robust preferences approach, agents rank acts according to a criterion that uses an estimated distribution p and also the relative entropy or Kullback-Leibler divergence between p and other distributions (capturing the possibility that p is not the right distribution). Hansen and Sargent's model can be interpreted in terms of variational preferences.  

Ellsberg's paradox, which basically says that people prefer situations where they have a known probability of winning rather than situations where the probability is unknown ("the devil they know"), can be explained using an extension of the Rank Dependent Utility to compound lotteries or two-layer expected utility. In this model, the decision maker has a set of priors in mind but also a prior over the set of priors, called a second-order belief, over which we take an expectation of distorted expected utilities.  

Jaffray (1989) "Generalizes the standard expected utility under risk to a framework in which the probabilities of the different states of nature are imperfectly known," belonging to given intervals. The authors explain that "to any set of probability distributions, it is possible to associate is lower envelope, associating to each event its lower probability compatible with the set of distributions." This lower envelope is a capacity (an increasing, non-necessarily additive set function). Then the value associated to a decision uses the minimal and maximal outcomes on events and the Mobius transform of the capacity makes an apparition, measuring the ambiguity of the event, i.e., the gap between the lower probability of this event and the sum of the lower probabilities of its sub-events. Oh, and to add to the fun, there is a pessimism-optimism index.

The paper continues with definitions of ambiguity aversion and complexities that arise from including dynamics. Many researchers have considered updating rules for preferences in maxmin expected utilities. There is also a section documenting the experimental evidence about decision makers' attitude toward ambiguity. Finally, the authors end with references about how these decision criteria have been used in finance and auctions. 

It was a very worthwhile read and I highly recommend it!

Decision making under ambiguity by Etner, Jeleva and Tallon, Part 1

This is one of the most interesting papers I've read in a while and it is in the Journal of Economic Surveys, not a journal we in operations research and management science typically look at. Plenty of concepts in this paper are relevant to the field of robust optimization, and of course many of my robust optimization colleagues will have heard of some of those concepts, it still feels that our two communities of management scientists and economists should talk together more often. I really enjoyed reading this paper and recommend that everyone read it too. Anyway, here is a summary.

The authors use the terms 'uncertainty' or 'ambiguity' equivalently, to represent non-probabilized uncertainty, as opposed to risk, which represents 'probabilized' uncertainty (you can be sure that sentence caught my interest, and I was still on the first page.) The authors explain: "We will thus concentrate on situations in which there is too little information to pin down easily probabilistic beliefs (as opposed to risky situations, in which objects of choice - lotteries - are already formulated in terms of probability distributions)." One thing you want to remember if you haven't looked at the economics literature in a while is that they view everything random in terms of lotteries when they can and imagine that the decision maker can choose between different lotteries to express his attitude toward risk. The lotteries typically only have two possible outcomes, and only one in a riskless case. 

The authors readily point out that they had to leave out some recent developments in the field, especially the concept of "unforeseen contingencies and more generally the issue of subjective state space" because it is too early to distinguish the main contributions from the rest. But their paper was first published about ten years ago so I was curious to discover the developments in those fields in 2020. Some articles about unforeseen contingencies include "Unforeseen Contingencies and Incomplete Contracts" by Eric Maskin and economics superstar Jean Tirole in the Review of Economics Studies 66(1): 83-114, 1999, who argue that what matters is that "agents can probabilistically forecast their possible future payoffs (even if other aspects of the state of the nature cannot be forecast). In other words, all that is required for optimality is that agents be able to perform dynamic programming, an assumption always invoked by the incomplete contract literature". The ability to perform dynamic programming is certainly a valuable skill for anyone to have in life. In "Static Choice in the Presence of Unforeseen Contingencies," by David M. Kreps, in the book "Economic Analysis of Markets and Games", Kreps presents a way to "model conceptually the idea that certain contingencies may be unforeseen", which gives rise to "an implicit representation theorem that is remarkably similar to the Savage model" - the 1954 model at the core of choice under uncertainty.

Savage developed subjective expected utility theory and characterized individual choice in presence of uncertainty as expected utility maximizing behavior. The most important axiom of his theory is known as the "sure thing principle". It says that "when comparing two decisions, it is not necessary to consider states of nature in which these decisions yield the same outcome." Another key axiom is the idea that the likelihood ranking of events does not depend on the consequences (such as receiving a car rather than receiving 100 euros). Savage's theory resembles von Neumann and Morgenstern expected utility under risk, meaning that "decision under uncertainty can in some sense be reduced to decision under risk, with one important caveat: beliefs are here a purely subjective construct."

Etner et al then discuss models generalizing Savage expected utility using non-Bayesian decision criteria. The first model is the Wald maxmin criterion, which evaluates decisions by looking exclusively at the worst possible consequence. It was generalized by Arrow and Hurwicz in 1972, who consider a convex combination of both the worst and the best outcomes (this is called the Arrow and Hurwicz alpha maxmin model). The weight of the worst outcome, denoted alpha, measures the decision maker's pessimism. The Arrow and Hurwicz model has been shown to be the only criterion susceptible to model choice under complete ignorance, i.e., the decision maker has no means to assess whether one event is more likely than another. Etner et al then present two "first-generation" models that use capacities to represent non-additive beliefs in the face of uncertain situations: the Choquet expected utility and the cumulative prospect theory. In the case of Choquet expected utility, beliefs are characterized not by a subjective probability but by a capacity, that is, a non-necessarily additive, increasing set function. Actions are then evaluated using Choquet integrals rather than standard Lebesgue integrals due to the non-additivity of the capacity. For decisions with a finite set of outcomes, "a decision maker evaluates a decision by considering first the lowest outcome and then adding to this lowest outcome the successive possible increments, weighted by his personal estimation of the occurrence of these increments." The cumulative prospect theory developed by Kahneman and Tversky in 1979 is related to the Choquet expected utility model but has a reference point and an asymmetry in the treatment of gains and losses. It introduces two different capacities, one for gains and one for losses.

The next generation of models of decision making under uncertainty "rests on the idea that when information is sccarce, it is too demanding to ask for precise subjectiee beliefs (a probability distribution) but maybe asking only for 'imprecise' subjective beliefs (i.e., a set of probability distributions) is more appropriate." This is known as having multiple priors. It is still possible to compute expected utilities, but now we have one value per prior. One possibility to compare two decisions is to say that an act f is preferred to an act g if all the expected utilities of f with respect to the distributions in the set of priors are higher than those of g. As a result, not all acts can be compared (f can be better than g for some priors and g can be better than f for others.) This is an example of incomplete preferences. It is possible to evaluate the multiple priors by considering their worst case, which gives rise to the maxmin expected utility of Gilboa and Schmeidler. Under an assumption of uncertainty aversion, "the Choquet expected utility model is a particular case of the maxmin expected utility model" and the set of priors over which the decision maker takes the minimum is the core of a convex capacity. The maxmin expected utility can also be generalized using a confidence function, using a threshold level under which priors are not taken into account in the evaluation.

A natural follow-up question is how to determine the set of priors in the maxmin expected utility model. That, and the rest of the paper, will be the subject of my next post!

One of the most useful features of the paper is a toy insurance example that runs throughout the paper to illustrate the various concepts.

1. An individual with initial wealth w is facing a risk of loss d. The state space is: {Loss, No Loss}. An act specifies what amount of money the decision maker has in each state of nature. The act of not buying insurance would be represented by f = (w-d, w). Buying full coverage at premium pi would yield g = (w - pi, w - pi). Buying partial coverage at premium pi' would lead to h = (w-d + I - pi'), w - pi') with I the indemnity paid in case of damage.
2. A decision maker following Savage's axioms would have a probability of loss p and a utility function u and would compute p*u(w-d)+(1-p)*u(w) for act f, u(w-pi) for act g and p*(w-d + I - pi')+(1-p)*u(w - pi') for act h.
3. If the DM's preferences are represented by the Choquet expected utility model, the decisions will be evaluated as: for act f, u(w-d)+v(NoLoss)*[u(w)-u(w-d)], for act g, u(w-pi) and for act h, u(w-d+I-pi')+v(NoLoss)*[u(w-pi')-u(w-d+I-pi')]
4. Incomplete preferences can be illustrated assuming that p (the probability of loss) is either 1/3 or 1/2 and taking w=3/2, d=1/2 and u(x)=x. If 4/3>3/2-pi >5/4, "it is sometimes better to get full insurance and sometimes better not to have any insurance" depending on the prior used.
5. If the individual's subjective set of beliefs is such that p is in the range [p',p''] and he decides using a maxmin expected utility model, then he evaluates f as p''u(w-d) + (1-p'')u(w), g as u(w-pi) and h as p''u(w-d+I-pi')+(1-p'')u(w-pi'). Note that the individual "evaluates acts only according to the worst possible prior in the set, that is, the highest loss probability p''."
6. Starting with the sixth part of the example the math starts being too cumbersome to retype so you will have to look up the rest in the paper itself!

Procurement with Unforeseen Contingencies by Herweg and Schmidt

 Today's post is on Procurement with Unforeseen Contingencies by Fabian Herweg and Klaus Schmidt, which was published last year in Management Science. This is about buyers who want to procure complex goods, whose designs they have made themselves. In price-only auctions, the seller/contractor who will make the product based on the design has no incentive to share his expertise, which would minimize design adjustment costs. The authors propose a mechanism that both "allocates the contract to the seller with the lowest cost and that induces all potential sellers to reveal any information that they may have about possible design flaws early (i.e., before the contract is assigned)." The authors' approach takes into account that, although the buyer knows the potential design may be flawed, he has "no idea what possible flaws look like and what their payoff implications are." 

The authors explain their mechanism as follows: sellers have to point out any design few they discovered to an independent arbitrator, who verifies the flaws, estimates their payoff consequences and assigns payments to the sellers as follows: "if a seller is the only one who reported a flaw, he will get a reward that is equal to the additional profit he cud have made if he had kept the information to himself, won the contract, and renegotiated with the buyer; otherwise, he gets nothing." Then "the revealed flaws are fixed and the improved design is allocated to the seller with the lowest cost in a sample Vickrey auction."  

A key contribution of the paper to the literature, besides the novel mechanism, is that it contributes to the literature on "robust implementation" (which is why it caught my attention), which requires mechanisms not to depend on unobservable beliefs and higher-oder beliefs of the participants. In addition, the authors' mechanism "does not require the mechanism designer to know all possible states of the world (i.e., the set of possible flaws and their payoff consequences)"; instead, it combines ex post incentive compatibility and ex post verifiability.     

A Survey of Multiple-Objectve Sequential Decision-Making by Roijers et al

Today's post is on a survey of multiple-objective sequential decision-making that appeared in the Journal of Artificial intelligence Research in 2013. The authors "identify three distinct scenarios in which converting such a problem to a single-objective one is impossible, infeasible or undesirable." They propose a classification of multi-objective methods that determines the nature of a optimal solution, "which can be a single policy, a convex hull or a Pareto front." 

They start by formalizing the problem as a multi-objective Markov Decision Process (MOMDP) and then motivate the multi-objective perspective on decision-making (rather than combining the multiple objectives into one function via scalarization). The three scenarios for which this makes sense are:

1. The unknown weights scenario, meaning that the weights are unknown when the planning happens. (For instance, the arises if you are trying to balance commuting time and pollution costs in a public transport system, and the price to offset pollution costs, traded on an open market, varies every day.) 
2. The decision support scenario, meaning that you cannot easily turn all the objectives into a common currency such as dollars. 
3. The known weights scenario, meaning that we could scalarize the muti-objective problem into a single-objective problem but this may not be desirable if the scalarization function is nonlinear, because the optimal policy could then be non-stationary or stochastic, which cannot happen in single-objective, additive, infinite-horizon MDPs. As a result, standard methods are not applicable and the MDP can be difficult to solve.  

They present "a novel taxonomy that organizes multi-objective problems in terms of their underlying assumptions and the nature of the resulting solutions" in Table 1 p. "75" of the paper I linked above (page 1 is numbered p.67, so don't let those numbers scare you.) They discuss the set of undominated policies for the MOMDP and the concept of coverage set, i.e., a subset of undominated policies for which, for each weight vector, at least one policy in the subset is optimal.

The authors consider two types of scalarization functions: linear (which are more intuitive) and monotonically increasing (which can express more accurately the user's preferences). For linear scalarization functions they define the convex hull of policies and for monotonically increasing scalarization functions they define the concepts of Pareto front and Pareto coverage set. It is also important to distinguish between deterministic and stochastic policies.

In single-objective MDPs, the manager can restrict his search to deterministic stationary policies. This is also true of MOMDPs when the scalarization function is linear. The authors show that "in the multiple-policy setting when only deterministic policies are allowed and [the scalarization function] is nonlinear, non-stationary policies may be better than the best stationary ones." When stochastic non-stationary policies are allowed, the manager can use stochastic stationary policies instead of deterministic non-stationary ones. Hence, the authors explain, the manager "can employ a mixture policy and selects the i-th policy for this set with probability p_i."  

Finally, they survey MOMDP planning methods, i.e., "computing an optimal policy or the coverage set of undominated policies given a complete model of the MOMDP", and MOMDP learning methods, when a complete model of the MOMDP is not available. In that case, multi-objective reinforcement learning (MORL) can be used. The majority of approaches in that field is on single policies, learnt through standard temporal-difference (TD) methods such as Q-learning. Linear scalarization is often considered but is, again, not always appropriate.

The four main classes of single-policy MORL with non-linear secularization are:

a. TD methods without modification (heuristics not guaranteed to converge),

b. modified TD algorithm or state representation to avoid non-additive returns,

c. TD methods to learn multiple polices using linear scalarization with different values for the weight vector,

d. policy-search methods.

In the case of multiple-policy learning with linear scalarization, running TD multiple times wth different weight vectors is inefficient, and more sophisticated approaches to learn multiple policies in parallel through online learning or to implement offline a multi-objective extension of the Fitted Q-Iteration algorithm.

The last sections survey the applications that have used multi-objective methods for planning and learning and discuss future work. Overall, a good read, highly informative.    

Sustainable inventory with robust periodic-affine policies and application to medical supply chains by Bandi et al

Today's post is about "Sustainable inventory with robust periodic-affine policies and application to medical supply chains" by Chaithanya Bandi, Eojin Han and Omid Nohadani, published in Management Science in 2019. They introduce a new class of adaptive policies called periodic-affine policies that do not require distributional assumptions and model uncertain, correlated demand via sets. Their definition of sustainability is time consistency, which may not be the first definition of sustainability that comes to the reader's mind, because "they warrant optimality both within sub periods and over the entire planning horizon." They apply their approach to data from one of India's largest pharmacy retailers. 

In the authors' setting, unfulfilled orders are backlogged. They consider multiperiod robust newsvendor networks and adaptive policies that are affine functions of realized uncertainties and convert the multiperiod problem into a two-stage problem, which is computationally intractable. They also extend the concept of affine policies to affine approximation policies, the coefficients of which can be determined through linear programming but which only provides suboptimal solutions to affine policies. Then they introduce the concept of periodic-affine policies, "where the overall time horizon is separated into sub periods, which are interconnected by the preceding surplus to become the proceeding demand. In this approach, the order quantities are determined as an affine function of past demands realized only within its sub period, as opposed to affine and affine-approximation policies where all previous demands are considered." They show this approach is computationally more tractable than affine policies using a dynamic programming formulation and describe how to extend their framework to multi-station networks. Their numerical experiments considering one of India's largest pharmacy retailers indicate that they are able to increase the profits by up to 17% over basestock policies. Capturing demand correlation can sizably affect performance.     

"Optimal learning" tutorial by Warren Powell and Peter Frazier

As a follow-up to my previous post on a unified framework to stochastic optimisation, here is a 2008 TutORial in Operations Research by Warren Powell and Peter Frazier on Optimal Learning, which seeks to solve the problem of optimally collecting information with which to make decisions.

There are two types of learning: online and offline. Online learning describes a setting where we incur the cost of traveling a link at the same moment as we learn about the cost. ("Measurements occur as we operate the system.") Offline learning refers to a case where we first have a budget to learn the information and then we operate the system with the best design we have found. The authors describe many examples of learning, especially the learning shortest path problem, where the costs of traveling the arcs can be revealed in three different ways: (1) only after traversing the link, (2) when the traveler arrives at the origin node of the arc he is about to travel, (3) at the beginning, before the traveler starts his trip. The more challenging problem is posed by Type-(2) networks.    

The authors point out that optimal learning is not the same as stochastic (data-driven) optimization. Optimal learning is about using observations "to improve our distribution of belief about the stochastic process driving the problem". The authors add: "A central feature of optimal learning problems is the ability to make decisions that reveal information, which is then used to reduce the overall level of uncertainty about the system." They describe the elements of a learning problem, including the states of the system, the types of decision, exogenous information. They also discuss transition functions for the frequentist view (data-driven view, where we begin with no information about the state of the system) and the Bayesian view (where we begin with a prior distribution of belief about the unknown parameters, take measurements and update our distribution into a posterior distribution). (When we end up with the same class of distribution that we started with, we say we have a conjugate family. Alternatively, we may impose conjugacy as an approximation.)

Then Powell and Frazier discuss objective functions: how to evaluate whether we are making better decisions with our measurements and how we are managing the economics of measurement and the evaluation of the solution. They state: "There are two broad settings in which optimal learning arises: (1) conducting a series of measurements to design a process or a system, where we are restricted by some sort of a measurement budget; (2) controlling a system where we collect information as we are managing the system." The first case is called offline learning and the second case is called online learning. 

The objectives themselves that we might use in optimal learning can belong to a vast range. A possible choice would be the expected value, maximizing the expected value of choice after the measurements. Another one would be the probability of correct selection. Yet another one would be "to maximize the likelihood that we make a choice that is almost as good as the best," which is known as indifference zone selection and is related to some current research ideas of mine. A fourth and fifth types of objective are least square error and entropy minimization. ("Entropy is a measure of uncertainty that can be used for numeric and nonnumeric data... The entropy is largest when the density is closest to the uniform distribution. If the entropy is zero, then we know [the parameter] perfectly. Thus we can try to take measurements that reduce the entropy of the distribution that describes our knowledge about a parameter.")  

The authors then discuss measurement policies, i.e., "rules that tell us which action we should take next in order to serve something new." They distinguish between deterministic policies (where the manager decides what he is going to measure before he begins making any measurements) and sequential policies, "where the decision of what to measure next may depend on past measurements." They present Bellman's equations characterizing the optimal action but point out that those equations are virtually impossible to solve even for very small problems. They describe heuristic policies for discrete selection problems:

• Pure exploration (to "estimat[e] the value of each choice, as opposed to making a good economic decision"
• Pure exploitation (making the best decision given our current set of estimates every time)
• Mixed exploration and exploitation: a strategy where we explore with a given probability (that doesn't change with the number of observations) and exploit with the complementary probability
• Epsilon-greedy exploration: this strategy takes into account the number of iterations by noting that "in the beginning, it is better to explore. As we build confidence in our estimates, we would prefer to exploit more." 
• Boltzmann exploration (sampling each measurement with a probability that maximises the soft max)
• Interval estimation (my favorite, which maximises the upper limit of a confidence interval of the value of a measurement. This was pioneered by Kaelbling, L.P., Learning in Embedded Systems, MIT Press, Cambridge, MA, 1993.)

Stopping problems are, in the authors' words, "a simple but important class of learning problems." A well-known classic problem is known as the secretary problem, involves the challenge of interviewing a sequence of candidates for a secretarial position. "The problem involves the tradeoff between observing candidates (which allows us to collect information) and making a decision (exploiting the information)". The authors remind the readers, based on Puterman's work, that if we have N candidates to interview, we should interview m before offering anyone the job. "The first m candidates, then, are used to learn something about the quality of the candidates. After interviewing m candidates, then the best strategy is to take the first candidate who is the best candidate interviewed so far."

Multiarmed bandit problems are one of the best known problems in information collection. (It is motivated by playing slot machines.) This leads to the basic theory of Gittins indices. The authors' Section 8 is devoted to this problem. They then describe ranking and selection problems and provide an overview of methods, going in detail over the knowledge-gradient method, first for independent measurements and then correlated measurements.

Independent measurements arise when measuring one choice does not tell us anything about measurements about another choice. For instance, if two new technologies are radically different, measuring the efficiency of one tells us zero about the efficiency of another. The idea behind the knowledge gradient is to consider a myopic policy where we choose an action now to maximize the expected value of the next state, rather than picking the best option right now. We can think of it as maximising the incremental value (or gradient with respect to the measurement) given the current state. This was first introduced by Gupta and Miescke in 1996 and studied further by Frazier, Powell and Dayanik in 2008 (they are the ones who coined the term knowledge gradient). Powell and Frazier in their tutorial also explain how to compute the normalised influence of a certain decision and the knowledge gradient index. It is possible to show that the knowledge gradient policy is asymptotically optimal.

Correlated measurements refer to the case where making one measurement (for instance demand for an item at a certain price) tells us something about what we will observe if we make other measurements (observing demand at other prices). This setting was investigated by Frazier, Powell and Dayanik in 2009, assuming knowledge of the covariance matrix. They discuss how to write the updated mean from making a measurement using the vector version of the Bayesian updating formulas, the Sherman-Woodbury equations and an analytical form. They provide the equation to compute the knowledge gradient policy for correlated measurements, but the expected value in the formula is a lot harder to compute due to correlation. While an approximation using Monte Carlo methods is possible, the authors describe a procedure by computing a sequence of lines with increasing slopes and finding the range for which a particular choice dominates. This allows for a simple analytical expression to compute the expected value as a sum of well-chosen terms. The authors also discuss how to compute the knowledge gradient in the case of online learning.     

Some references:

Gittins, JC. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society, Series B, 14:148-177, 1979.

Frazier, P, W. Powell and S Dayanik. A Knowledge-Gradient Policy for Sequential Information Collection. SIAM Journal on Control and Optimization. 47(5):2410-2439, 2008.

Frazier, P, W. Powell and S Dayanik. The Knowledge-Gradient Policy for Correlated Normal Beliefs. INFORMS Journal on Computing. 21(4):599-613, 2009. Available here.

 

"A unified framework for stochastic optimization" by Warren Powell

Over the break I finally found the time to read A unified framework for stochastic optimization by Warren Powell, which was published online in European Journal of Operations Research in July 2018.

This paper provides a highly valuable overview of the field with plenty of great references. This is particularly useful for doctoral students, as I've noticed that some doctoral students struggle with identifying quality papers and discounting papers published in no-name journals. Powell's paper also connects multiple topics and highlights research directions in the field, and represents an outstanding starting point for university courses such as an undergraduate-level course (Sequential Decision Analytics and Modeling) and a graduate-level course (Stochastic Optimization and Learning) at Powell's home institution of Princeton University.

Powell articulates multiple classes of policies, from policy search to lookahead approximations and from state-independent problems to state-dependent problems. He discusses optimisation of the final reward vs optimisation of the cumulative reward and explains that the multiarmed bandit problem can be viewed as a derivative-free stochastic search problem. He also argues that "classical algorithms such as stochastic gradient methods can be viewed as dynamic programs, opening the door to addressing the challenge of designing optimal algorithms." 

The paper discusses the following topics: decision trees, stochastic search, optimal stopping, optimal control, Markov decision processes, approximate/adaptive/neuro-dynamic programming, reinforcement learning, online algorithms, model predictive control, stochastic programming, robust optimization, ranking and selection, simulation optimisation, multiarmed bandit problems and partially observable Markov decision processes. Powell then provides three solution strategies: deterministic strategies for problems that exhibit special structure, sampled models (when the expectation in the objective cannot be computed exactly but where the original set of outcomes can be replaced with a sample) and adaptive algorithms (the most widely used approach, which sequentially samples random information). He then describes how to design policies through policy search (policy function approximations or cost function approximations) or lookahead approximations (value function approximations or direct lookaheads).  

The rest of the paper goes over learning challenges, modelling uncertainty, policies for state-independent problems (derivative-based and derivative-free, where the belief model is represented either through lookup tables, parametric models or nonparametric models; the article goes on describing four classes of policies: policy function approximations, cost function approximations, value functions and direct lookahead policies) and policies for state-dependent problems (illustrated through the example of an energy storage problem, considering policy function approximations, cost function approximations, value function approximations and direct lookahead approximations). 

The paper ends with a classification of problems and a discussion of research challenges. The references list contains over two hundred references. I particularly enjoyed seeing references of John Tsitsiklis's work, who served on my PhD dissertation committee back in the days, and of course references of my PhD advisor Dimitris Bertsimas. Here are some references for those of you who would like some reading suggestions. 

Bayraksan, G. and Love, D. K. (2015) Data-driven stochastic programming using Phi-divergences. INFORMS TutORials on Operations Research 2014, 1-19.

Bayraksan, G. and Morton, D. (2011) A sequential sampling procedure for stochastic programming. Operations Research 59(4), 898-913

Bertsimas, D., Iancu, D. A., and Parrilo, P. A. (2011) A hierarchy of near-optimal policies for multistage adaptive optimisation. IEEE Transactions on Automatic Control, 56(12), 2809-2824.

Fliege, J. and Werner, R. (2014) Robust multiobjective optimisation and applications in portfolio optimisation. European Journal of Operational Research, 234(2): 422-433. 

Shapiro, A. (2012) Minimax and risk averse multistage stochastic programming. European Journal of Operational Research, 219(3): 719-726.

On "Robust Fluid Processing Networks" by Bertsimas, Nasrabadi and Paschalidis (2015)

Citation: Dimitris Bertsimas, Ebrahim Nasrabadi and Ioannis Paschalidis. (2015) Robust Fluid Processing Networks IEEE Transactions on Automatic Control, 60(3):715-728. Paper

Summary: Fluid networks provide a deterministic approximation to multiclass processing networks, making them much more tractable than their stochastic counterpart; however, the manager completely disregards randomness and there might be value in incorporating such uncertainty in the decision-making process. The authors' robust optimization approach aims at doing just that by combining the tractability of fluid networks and the practical relevance of including uncertainty in the modeling framework through an approach (robust optimization) that has a track record of leading to reformulated problems of complexity similar to that of the deterministic problems.

Specifically, the authors show that the robust fluid model preserves the computational tractability of the classical fluid problem and retains its original structure. They derive a scheduling policy determining how various classes should be processed at the servers of the network using complementary slackness optimality conditions. They also develop a polynomial-time algorithm under certain conditions. Simulation results demonstrate that the robust fluid policies are near-optimal when the optimal policies can be computed and outperform heuristics when the optimal policies cannot be computed in a tractable manner.

Outline:

I. Introduction

II. Problem description and fluid model

A. Criss-cross network

This is a simple network where one type goes through two servers (becoming class 1 and then class 3) but must compete with another type (class 2) at the first server. The second type doesn't go through the second server and simply exits the system.

B. A general formulation

The authors define the general problem, formulate its dual and write out the complementary slackness conditions.

III. Robust fluid model

A. Modeling the uncertainty

Uncertainty is incorporated on the arrival and service times (the lambda's and the 1/mu's) using Bertsimas-and-Sim uncertainty sets bounding the deviation from the nominal value by a total amount Gamma_j at server j at each time. 

B. Robust counterpart problem

The authors define the robust problem and re-formulate it in a tractable manner using strong duality arguments. 

C. Robust policies

The authors translate the optimal solution of the robust problem into a dynamic scheduling policy for the control of stochastic networks.  The idea is to give priority on each server to classes with the highest value of a new parameter between 0 and 1 computed using the optimal control found by solving the robust fluid problem.  

IV. A single-server system

In this section the authors show how they can find an optimal control for the robust fluid problem in polynomial time. They show they need to solve at most n linear optimization problems in the single-server case because they pick a class to serve until that class is depleted. Then an optimal policy is to serve each class with service rate the arrival rate and no job will be held in the network. This leads to a piecewise-constant solution with breakpoints the times where a class becomes depleted. 

A. Klimov's problem

All the results can carry over to a single server queue with probabilistic feedback.

V. Simulation results 

The goal is to compare the performance of the robust fluid policy to that of the optimal policy in small-size networks (when the optimal policy can be computed), and to that of reasonable heuristics on moderate to large-size networks. The authors also investigate the sensitivity of the robust policy to the parameter Gamma.

A. Computational remarks

B. Network examples

The authors consider four different network types: the criss-cross network and three types of reentrant networks, where at least one type of jobs cycles back to a server it had already visited. 

VI. Conclusion

Why I like this paper: First, there is the obvious reason that this paper provides a tractable approach to incorporating uncertainty in fluid networks, filling an important gap in the literature between (deterministic) fluid networks and stochastic networks. Also, over 15 years ago when I first started my PhD on robust optimization I did research on fluid networks for about a year before moving to inventory theory. It is fun to see that someone finally solved the problem, and the results are very elegant. I also love anything that uses strong duality or complementary slackness. 

Further reading:

• Malcolm C. Pullan (1996) A duality theory for separated continuous linear programs. SIAM Journal on Control and Optimization, 34:931-965. The title says it all.
• Mathieu Ricard (1995) Optimization of Queueing Networks: An Optimal Control Approach. PhD dissertation, MIT. It doesn't have anything about robust optimization in it but the threshold policies derived for various complex settings are impressive.

On "Project Management Under Risk: Using the Real Options Approach to Evaluate Flexibility in R&D" by Huchzermeier and Loch (2001)

In an effort to better remember the papers I read, I'm starting a new section about my blog devoted to short summaries of papers I find interesting. It's called "Analytics Corner". 

Citation: Arnd Huchzermeier, Christoph H. Loch, (2001) Project Management Under Risk: Using the Real Options Approach to Evaluate Flexibility in R&D. Management Science 47(1):85-101. Link

Summary: The authors consider a situation where a manager developing a new product can either abandon, continue or improve the product during development. Theyanalyze the setting using dynamic programming, study the impact of five types of uncertainty on the real options value  and obtain results counterintuitive to prevailing knowledge in option pricing theory, due to the unique features of the R&D real options framework. This paper contributes to improved risk management in R&D projects.

Outline:

1. Introduction and Literature Overview 

2. Five types of operational uncertainty

Market payoff variability, (R&D) budget variability, performance variability, market requirement variability, schedule variability (project may finish ahead of or behind schedule.

3. The basic model

3.1 Contingent claims analysis

Motivation of the use of dynamic programming, justification of discounting at the risk-free rate.

3.2 A dynamic programming model of an R&D project

T discrete stages corresponding to regular design reviews, leading to market introduction. Market success is determined by product performance, modeled by a one-dimensional parameter i. Performance uncertainty is captured in the variability of a probability distribution, measured by higher variance given same mean. This causes product (expected final) performance to drift between review period. Hence the authors define transition probabilities from expected performance state i to expected performance stage j. 

Performance may unexpectedly improve with probability p or deteriorate with probability 1-p. Improvement or deterioration are spread equally over the next N states. For instance the probability of improvement is p/N for j=i+1/2, i+1, ..., i+N/2. The parameters N and p can be chosen to approximate a distribution using its first two moments. At each time period, the manager can decide to abandon, continue or improve the project. (The originality of the paper comes from having the possibility to improve.) Improvement results of a mean shift of the transition probabilities by 1 (the index of each state j is increased by 1, both for improvement and deterioration.)

Expected payoff if the product is launched in state i is given by m+F(i)*(M-m) where m is the smaller margin if the project misses the performance level and competes only on cost and M is the profit margin if the project exceeds this performance level, and F(i) is the probability that performance i exceeds the market requirement D. This payoff function of i is assumed convex-concave increasing. 

The authors then formulate the manager's problem as a dynamic programming problem, writing out Bellman's equations from T back to time 0, evaluating the value of three actions (abandon, continue and improve) at each time period. They characterize the optimal policy as follows, assuming the payoff function is convex-concave increasing: there exists three functions L_u(t)>=L_m(t) and L_d(t) such that it is optimal to abandon if i<=L_d(t), and if i>L_d(t): continue if i>L_u(t) or i<=L_m(t) and improve if L_m(t)<i<=L_u(t). This is presented visually in Figure 4.

4. Uncertainty and the Value of Flexibility

This section studies the impact of increasing the variance of certain key drivers, to see whether the intuition that higher uncertainty in project payoff increases the real option value extends to other types of uncertainty faced by R&D managers.

4.1 Market payoff variability

4.2 Budget variability

4.3 Performance variability

4.4 Market requirements variability

4.5 Schedule variability

5. Conclusion

Why I like this paper: I like the use of dynamic programming in a managerial context (this is one of the papers I gave to read to the doctoral students in my PhD course on nonlinear programming) and the visual nature of the optimal policy shown in Figure 4. 

Further Reading: Real options: Managerial flexibility and strategy in resource allocation by Lenos Trigeorgis (1996)