Professor Powell’s decision analytics series — Topics 1–19

This is a series of posts on LinkedIn that describe different elements of sequential decision problems — any sequential decision problem. Applications might be transportation and logistics, energy, finance, e-commerce, health, or even laboratory sciences (what experiment to run next).

I post these each week, and I had been making them available on google docs. I am moving the series to medium. Each week I will add that week’s post on LinkedIn.

Topics 20 onward can be found here.

Introduction to the series

Posted: July 3 2020

I am going to be making a series of posts on the topic of analytics for sequential decisions under \uncertainty, with the goal of applying modern AI to real (and possibly complex) decision problems. My work has grown out of projects in freight transportation, logistics, energy systems, e-commerce, health and finance, and spans theory, computation and real-world implementations. This is the next level of AI, where we move past the current fixation on learning and classification (neural networks anyone?) to making decisions (What price? What path? What treatment?). Each post will fall under one of the categories: decision analytics, knowledge representation, learning and forecasting, uncertainty quantification, metrics, and implementation. I will label each post by the category and a subtopic. The posts will be made on Fridays and Tuesdays. But my next post (to follow this one) is going to start with the simple question: what is AI?

Questions and comments are welcome! I will do my best to respond.

Decision analytics

Topic: 1 — Decision analytics: What is AI?

Posted: July 3 2020

The most common types of AI come in three flavors: rules, machine learning, and making decisions (“optimization”). Rules are used for guiding computers to identify patterns or make recommendations, and have to be designed by people. This is how AI was done in the 1970’s. Learning involves using an external dataset to fit a statistical model. For large models (such as neural networks) we need huge datasets, which often are not available. Making decisions, on the other hand, requires a model of the physical system, and metrics that tell us how well we are doing, but does not require a training dataset. Making decisions is the most advanced form of AI. A simple decision problem is finding the shortest path to a destination, but some, such as scheduling an airline, can be very high dimensional. Others involve making decisions sequentially over time as new information arrives; these problems arise when making medical or financial decisions, managing robots, and playing games which are popular applications of reinforcement learning. The most complex problems are both high-dimensional and uncertain, such as allocating medical resources for COVID or managing a fleet of trucks. For more, see http://www.castlelab.princeton.edu/what-is-ai/

Topic: 2 — Decision analytics: Making decisions

Posted: July 7 2020

While neural networks have attracted considerable attention, these are primarily good for identifying patterns, but not making decisions. In the 1990s, the hot topic was “optimization” which referred to the emergence of powerful tools called linear and integer programming for large (but deterministic) decision problems such as scheduling airlines. In the 2000s, “reinforcement learning” attracted attention when it was used to solve Chinese Go, and has been applied to robots, games and medical decisions. However, none of these tools can optimize complex problems such as energy systems, health services, supply chains, or managing fleets of vehicles that introduce different forms of uncertainty.

In the late 2010’s, I introduced a new unified framework that pulled together over 15 distinct fields that address decision problems under uncertainty, which fall under the broad umbrella of “stochastic optimization” (see jungle.princeton.edu). The unified framework identifies four classes of “policies” (methods for making decisions) that are robust and scalable, and can be used to solve *any* sequential decision problem under uncertainty. Stay tuned!

Making decisions

Topic: 3 — Identifying decisions

Posted: July 10 2020

Before you optimize decisions, you need to identify the decisions you are making! Sometimes this is easy: buying stocks, routing truck drivers, and choosing medical treatments are all decisions that are easy to identify. Decisions might change the physical system (as these do), but other decisions might collect information from an experiment or conducting a survey. But what decisions do you make when you want to reduce COVID deaths, or improve sales? The English word “idea” often means “a decision we might make.”

Decisions occur on different time scales. Strategic planning covers decisions implemented farther in the future (where to source a product, how many drivers to hire). Tactical planning might be days or weeks (sometimes months) into the future (should I accept an order, what price to charge, ordering inventory). Real-time decisions are implemented right now (which ride-sharing driver to assign to a passenger, buying/selling a stock).

Remember: if you want better performance, you need to make better decisions — make sure you know what decisions you are making.

Topic: 4 — The four classes of policies

Posted: July 14 2020

Any time you make a decision, you use some method (or rule, or strategy) that we call a “policy.” This might be a simple rule (buy low, sell high), or something that requires looking into the future. Whatever method you use, it belongs to one of four (meta)classes of policies: PFAs (“policy function approximations”), CFAs (“cost function approximations”), VFAs (policies based on “value function approximations”), and DLAs (“direct lookahead” policies). PFAs and CFAs are the simplest. PFAs are simple rules such as buy-low, sell-high, while CFAs are simple optimization problems such as choosing the vendor with the lowest price, as long as their service meets some cutoff. Both PFAs and CFAs have tunable parameters that have to be tuned (the buy-low, sell high points, or the service cutoff). VFAs and DLAs are both policies that make a decision now using some sort of approximation of the impact of the decision on the future. A simple DLA is your navigation system that plans a path to the destination to determine what turn you should make now. Any method you use to make a decision will use one of these four classes (or a hybrid).

Topic 5: Designing policies

Posted: July 17 2020

We just introduced four classes of policies: policy function approximations (PFAs), cost function approximations (CFAs), policies based on value function approximations (VFAs), and direct lookahead policies (DLAs). How do we choose which to use? Often the characteristics of a problem suggests a natural approach. We might have a simple inventory problem where we place an order if the inventory falls below little s, and we order up to big S (these are called (s,S) policies, a form of PFA). But this will not work if we are placing orders with long lead times and have to manage holidays. In this case, we need to plan into the future (a lookahead). If the time for an order to arrive has considerable uncertainty (say, shipping times from China), we need to plan with an uncertain future (a form of stochastic DLA), or we can build in buffers, which gives us a CFA. Just remember: any policy you choose will fall in one of these four classes, or they may be a hybrid of two or more classes. And while it is natural to want the policy that works best, issues such as transparency and computational complexity are also important.

Topic 6: Policy evaluation

Posted: July 25

We may decide that there are two classes of policies that seem natural, or we may pick one (a PFA or CFA) that require tuning parameters. We need a method for finding the best values of the tunable parameters, as well as comparing different classes of policies. To find the best policy, you need a method to evaluate the policy, which means watching how it performs over time. There are two ways to do this: in a simulator on a computer (or in a physical lab), or in the real world. There are pros and cons to each. Simulators can be expensive to build, and always involve approximations. The real world is very real, but it is also very slow, and you can only observe what actually happens, which means you cannot simulate new scenarios, such as increasing energy from renewables, or raising the price of a product or service.

Topic 7: Lagged decisions under uncertainty

Posted: July 31, 2020

Complex resource allocation problems, such as energy systems, supply chains, or fleets of trucks, require making decisions over multiple time scales. When planning an energy system, strategic planning would cover how many generators to have, decisions that have to be planned years into the future. Then, the decision to turn a generator on or off might have to be made a day in advance, down to an hour (or less), depending on the generator. Finally, there are real-time adjustments we can make every five minutes (or every two seconds). Differences in lead times are one of the most powerful tools for dealing with uncertainty. We do not need precise forecasts for planning energy generation a day in advance if I have access to generators that can be turned on or off with an hour’s notice.

Lagged decisions, when a decision now is implemented in the future, represent one of the most difficult problems for people, or computers. They arise in energy, finance, freight transportation, and supply chain management.

Topic 8: Coordinating across decision-makers

Posted: August 9 2020

There are many problems where there is more than one decision-maker that we call agents. An agent can be a truck driver or a trucking company; a doctor or hospital; state and federal governments; a manufacturer; a utility or a grid operator. It is not unusual to model complex systems as a single, large system — this is common practice when people build large optimization models. Big mistake!

Each agent should be modeled as a separate system with its own decisions, using the information available to the agent. It is important to understand how agents communicate, and how the decisions of one agent affect the others. I call this “modeling the organization and flow of decisions and information.”

We can coordinate in several ways: 1) Using a central agent that makes at least some of the decisions; 2) Sharing information; and 3) Making sure the agents use a common goal.

When we are designing how each agent makes decisions, be sure to consider all four classes of policies that we first mentioned under topic 4.

Knowledge representation

Topic 9: State variables

Posted: August 14 2020

Without question, the most misunderstood element of sequential decision problems is the “state variable.” If you are moving over a network, you might model the state as the node where you are located. If you are managing the inventory of cars, the state would be the number of cars you have to sell. These are physical states. But the state variable can include weather, prices, the medical history of a patient or the forecast of demands. And if we do not know something (at least not perfectly), we can model beliefs which capture what we do know, and how well we know it. Just as a decision such as moving from one location to another or ordering inventory can change our physical state, running an experiment can change our beliefs. In a nutshell, state variables represent everything we need to know to model the system from a point in time onward. Understanding your state variable helps you understand what data you need to manage your system.

Topic 10: Belief modeling

Posted: August 21 2020

When making decisions in dynamic environments under uncertainty, there are going to be quantities or parameters that we just do not know perfectly. In health, it might be how well a drug will work. In business, it could be the probability that a customer will buy a product, or how the market will respond to changes in price. It could also be the travel time on a path. We can capture what we know using a statistical model that reflects not just our best estimate (say, of the performance of a medical treatment) but also the uncertainty in this estimate. We can update these beliefs using observations, but for these problems, what we observe depends on what decisions we make. We call this “active learning.” There are pure learning problems, where decisions only change the belief state, but we may have a combination of beliefs along with physical states, such as inventory.

Topic 11: Visibility and communication

Posted: August 28 2020

Large, complex systems that arise in supply chains, freight transportation, energy systems, and businesses often introduce the dimension that something may be perfectly observable to one agent but unknown to others who might still need this information. For example, how many available ICU beds do different hospitals have? A state coordinating officer will not know precisely, but the hospitals will know. A phone call could fix the problem, but only if we trust the answer (and this is a major issue). Sensors on the bed would be instantaneous and reliable, but expensive. These issues arise in so many settings. Grid operators for energy systems struggle because they may not know whether a generator is on or off, while freight brokers have to make endless phone calls to truck fleets to learn who can handle a load. “Visibility” refers to the ability of one agent to see the state of another agent.

Learning and forecasting

Topic 12: Learning

Posted: September 4, 2020

The reason that there is so much attention right now given to machine learning is that real problems are full of unobservable quantities that have to be estimated, and for this we draw on the tools of machine learning. There are three broad classes of statistical models: lookup tables (e.g. the response to each type of drug), parametric models (profit might be a continuous function of price) and nonparametric models (think of these as local approximations of complex functions). Neural networks are a kind of parametric model, but often with many thousands, or millions, of parameters to be estimated, which is the reason that they need such big datasets to fit these models. Their flexibility is both their strength, and their weakness, since they may not reflect known behaviors (such as demand decreasing as we increase price). When fitting models in the presence of noisy data, large neural networks may just fit the noise. We will return to machine learning strategies later.

Topic 13: Batch vs. online learning

Posted: September 12, 2020

The most common approach to estimating a statistical model (especially neural networks) is to take a large dataset and then run specialized algorithms to fit the best model. When you get new data, you do this all over again with a new batch of data. With more complex models (such as neural networks) small changes to the data can actually result in significant changes to the estimated model (an annoying property of nonlinear models such as neural networks). An alternative approach is to use adaptive learning where old models are updated with new data, but without reoptimizing from scratch. Also, in operational, or online, settings, data is arriving continuously over time, and the underlying process creating the data (such as demand responding to online advertising) is often changing, which means we should discount estimates based on older data (which is not possible with batch learning).

Topic 14: Probabilistic forecasting

Posted: Sept 18 2020

A common mistake is to assume that “forecasting” something such as a demand, price, or travel time means to make a best guess of a single value. Then, when the forecast does not come true (which happens almost 100 percent of the time), everyone then emphasizes reducing the error. The problem is — the real world is a messy place, and there are many settings where the uncertainty will never go away! [Hint: see Wall St.] A different approach is to forecast the distribution of demands, prices or travel times, and then make decisions that recognize that the future is uncertain. I call this probabilistic forecasting, and this requires transitioning to a whole new level of sophistication, since you can add point forecasts, but you cannot add distributions. We need to learn to live with uncertainty, which means we need to learn how to make decisions in the presence of uncertainty. Our four classes of policies are designed specifically to handle uncertainty.

Topic 15: Sources of uncertainty

Posted: October 3, 2020

One of the most difficult challenges when modeling systems under uncertainty is identifying all the different sources of uncertainty. For many real applications, the list can be long, and can occur on a range of time scales. Purchases made on an e-commerce website will vary minute-by-minute, but customer behavior can reflect changes that span days, weeks and months, reflecting changes in competitive behaviors, new products, or events such as COVID-19. Some events will follow familiar bell-shaped curves (the normal distribution), but there will be bursts (such as when a new product is discovered), spikes (perhaps responding to a weather event) and rare events (hurricanes, earthquakes, and pandemics). Whatever sources of uncertainty we can think of goes in our list of “known unknowns,” leaving everything we did not think of as the “unknown unknowns.”

Topic 16: Correlations

Posted: October 9 2020

The biggest challenge with probabilistic forecasting is capturing correlations. The wind at one location may be positively correlated with nearby locations. The number of loads of freight from St. Louis to Cleveland may be negatively correlated with the number of loads going from St. Louis to Dallas. If one customer purchases an unusual product, it may indicate the start of a burst as that customer shares their experience with friends. Probabilistic modeling is fundamental to modeling systems under uncertainty, but capturing correlations is what is going to keep you up at night. If someone insists that they are modeling uncertainty, ask them how they are handling correlations, and make sure they don’t blink!

Topic 17: Soft and hard metrics

Posted: October 23, 2020

It is nice when we have a simple goal such as minimizing costs, but this rarely happens with real problems. Businesses use key performance indicators (KPIs), and these can describe productivity of people and equipment, inventory turns, and service to the customer (a single company may use hundreds of KPIs). The problem is that when computers make decisions, they need a single metric to identify which decision is best. One widely used strategy is to create a “utility function” which uses a weighted sum of different metrics, leaving the problem of finding the weights. Alternatively, we may focus on one primary metric (Cost? Profit? Covid infections?) that we minimize or maximize, but then look for solutions where the other metrics are never above or below some point (perhaps a target level of service).

Topic 18: Risk

Posted: October 31, 2020

When we are evaluating policies, we typically optimize the average (or expected) performance over many possible realizations. However, there are many settings where we need to avoid specific events, such as running out of money, running out of ICU beds in the hospital, or not meeting the demand for energy. Managing these more extreme events means that we are dealing with risk. Measuring risk first means that we have to put careful attention to modeling uncertain events. Then, we have to evaluate performance capturing how we wish to limit our exposure to extreme events. We might do this by putting a high penalty when they happen, or insisting that they do not happen too frequently.

Topic 19: Implementation issues: From manual to automated decisions

Posted: November 8, 2020

If you are using analytics to automate a manual dispatch process, keep in mind the following:

1. Don’t assume that just because a decision comes from the computer that it is a good decision. Getting a computer to make effective decisions requires using everything I have been teaching in these posts.
2. Get ready for a lesson in what information is in the computer, and what is in the heads of the people making decisions. Watch out for phone calls, emails and texts that communicate unstructured information.
3. Don’t expect much if computer-generated decisions are just recommendations for people to use as they wish. Make sure you are confident that your policy is effective, but then start cutting back on people making decisions so they are forced to focus on exceptions.