# Modeling Sequential Decision Problems

## Introduction
Sequential decision problems involve making a series of interconnected decisions over time. The outcome of each decision influences the subsequent states and available choices. These problems are characterized by the following sequence:

`State -> Decision -> New Information -> State -> Decision -> New Information -> ...
`

### Key Elements
* **State:** The state of the system captures all the information needed to make a decision at a particular time. This can include physical resources, information, and beliefs about uncertain quantities.
* **Decision:** The decision is the action taken based on the current state.
* **New Information:** This is the information that arrives after a decision is made and influences the next state.
* **Policy:** A policy is a method or rule for making decisions. It can be a simple rule of thumb or a complex algorithm.

### Examples
* **Business:** Deciding what products to sell, what prices to charge, and how to manage inventory.
* **Finance:** Choosing which stocks to invest in and when to buy or sell them.
* **Healthcare:** Determining the best treatment plan for a patient based on their medical history and current condition.
* **Engineering:** Designing systems that can adapt to changing conditions, such as traffic control systems or energy management systems.

### Challenges & Approaches
The uncertainty inherent in sequential decision problems poses a significant challenge. The outcomes of decisions and the arrival of new information are often random, making it difficult to determine the optimal course of action.

Common approaches include:
* **Dynamic programming:** Breaks down the problem into smaller, manageable subproblems.
* **Reinforcement learning:** Learns optimal strategies through trial and error.
* **Stochastic programming:** Formulates the problem as a mathematical optimization problem.

## A Six Step Modeling Process
1. **The narrative:** Describe the problem in plain language, outlining the sequence of events and decisions.
2. **Core elements:** Identify the key metrics, decisions, and sources of uncertainty.
3. **Mathematical model:** Define state variables, decision variables, exogenous information, transition function, and objective function.
4. **Uncertainty model:** Specify how uncertainties are represented and incorporated into the model.
5. **Policy design:** Develop strategies (policy search, lookahead policies) to map states to decisions.
6. **Policy evaluation:** Assess the performance of different policies under various scenarios to identify the optimal one.

## The Mathematical Modeling Framework
A core aspect of solving sequential decision problems is formulating a mathematical model. This model comprises several key elements:

### State Variables
The state variable $S_t$ encapsulates all necessary and sufficient information to model the system from time t onwards. It includes information needed to calculate costs/contributions, constraints on decisions, and the system's evolution over time.

$S_t$ consists of three types of information:

* **Physical state $R_t$:** This represents the controlled resources or quantities within the system (e.g., inventory levels, resource allocations). $R_t$ can be a scalar or a vector, where each element might correspond to a specific resource type or location.
* **Other information $I_t$:** This encompasses any deterministic information not included in $R_t$, such as prices, demand forecasts, or known parameters. While often evolving exogenously, $I_t$ may also be influenced by decisions.
* **Belief state $B_t$:** This captures information about probability distributions describing uncertain parameters or quantities. $B_t$ may include the mean and variance of a normal distribution for a demand forecast or represent probabilities associated with various events.

### Decision Variables
Decision variables represent the choices available at each time step $t$. These can take various forms:

* **Binary:** Yes/no decisions (e.g., whether to sell an asset).
* **Discrete:** Selecting from a finite set of options (e.g., which product to advertise).
* **Continuous:** Variables that can take on any value within a range (e.g., prices, temperatures).
* **Vectors:** Collections of binary, discrete, or continuous variables (e.g., resource allocation across multiple locations).
* **Categorical:** Selecting from a set of non-ordered categories (e.g., features to highlight in an advertisement).

### Exogenous Information
This is the information that arrives after a decision $x_t$ is made. We let $W_{t+1}$ be any new information that first becomes known at time $t+1$ (that is, between $t$ and $t+1$), where the source of the information is from outside of our system (which is why it is "exogenous"). When modeling specific variables, we use "hats" to indicate exogenous information. Thus, $\hat{D}_{t+1}$ could be the demand that arises between $t$ and $t+1$, or we could let $\hat{p}_{t+1}$ be the change in the price between $t$ and $t+1$.

### Transition Function
The transition function $S^M$ governs the evolution of the system state over time:

$$
S_{t+1} = S^M(S_t,x_t,W_{t+1})
$$

This function describes how the current state, decision, and new information combine to determine the subsequent state. It might capture:

* Changes in physical resources (e.g., inventory updates, resource movements).
* Information updates (e.g., changes in prices, weather).
* Updates to beliefs about uncertain parameters (e.g., adjusting demand forecast distributions).

### Objective Function
The objective function quantifies the decision-maker's goal. While various formulations exist, a common approach is to maximize the expected total contribution over a finite horizon:

$$
\max_{\pi} \mathbb{E}\left\{ \sum_{t=0}^T C_t(S_t, X^\pi_t(S_t)) | S_0 \right\}
$$

where:
* $C_t$ is the contribution function at time $t$.
* $X^{\pi}(S_t)$ represents the decision made at time $t$ under policy $\pi$.

This framework provides a structured way to represent and analyze sequential decision problems, incorporating uncertainties, decisions, and their consequences over time.

## Modeling Uncertainty
Uncertainty is a key aspect of sequential decision problems. It can arise from various sources, including unknown quantities, parameters, and future events. In the modeling process, uncertainty is incorporated through two mechanisms:

1. **The initial state variables $S_0$:** These variables can capture the parameters of probability distributions that describe quantities or parameters that are not known with certainty. For example, the initial state might include the mean and variance of a demand distribution, reflecting the uncertainty in future demand.
2. **The exogenous information process $W_1, \dots, W_T$:** This process represents new information that arrives over time, such as actual demand, market prices, or patient responses to treatment. This information is often random and can significantly impact the system's state and the subsequent decisions.

To test and evaluate policies under uncertainty, we need to generate samples of the exogenous information process. This can be done using historical data, real-time observations, or simulations based on mathematical models. Each sample path represents a possible sequence of future events, and by evaluating a policy over multiple sample paths, we can assess its average performance and robustness to uncertainty.

## Example: A Simple Inventory Problem
**The Narrative:** A pizzeria needs to decide how many pounds of sausage to order at the end of each day $t$. Leftover sausage can be stored for the next day. The sausage cost and selling price are known in advance, but the daily demand is uncertain.

### Core Elements
* **Metric:** Maximize net income (profit minus cost).
* **Decision:** Determine the order quantity.
* **Sources of Uncertainty:** Daily demand for sausage.

### Mathematical Model
* **State Variable:** Inventory level at the end of day $t$, denoted as $R_{t}^{inv}$. Hence, $S_{t} = R_{t}^{inv}$.
* **Decision Variable:** Order quantity at time $t$, denoted as $x_t$. The decision is made using a policy $X^\pi(S_t)$ that will be designed later.
* **Exogenous Information:** Random demand for the next day, denoted as $\hat{D}_{t+1}$. Thus $W_{t+1} = \hat D_{t+1}$.
* **Transition Function:** $$R_{t+1}^{inv} = \max\left\{0, R_t^{inv} + x_t - \hat{D}_{t+1} \right\}$$ This equation describes the evolution of inventory over time, considering the previous inventory, order quantity, and demand.
* **Objective Function:** The contribution function is given by $$C(S_t, x_t, D_{t+1}) = -c x_t + p \min\{R_t^{inv} + x_t, \hat{D}_{t+1}\}$$ This function calculates the net income, subtracting the cost of ordering from the revenue generated by sales (up to the demand or available inventory). Given a sequence of demands $\hat{D}_1, \dots, \hat{D}_T$ the performance of a policy $\hat F^{\pi}$ would be $$\hat{F}^\pi = \sum_{t=0}^T C(S_t, X^\pi(S_t), \hat{D}_{t+1})$$ Since demand is random, we take the expectation: $$F^\pi = \mathbb{E}\left\{\sum_{t=0}^T C(S_t, X^\pi(S_t), \hat{D}_{t+1}) | S_0\right\}$$

### Uncertainty Model
We assume that the demand follows a normal distribution with known mean $\bar D$ and standard deviation $\bar{\sigma}$:

$$
\hat{D}_{t+1} \sim N(\bar{D}, \bar{\sigma}^2)
$$

To estimate the value of a policy, we can generate multiple demand sequences, each representing a possible scenario.

### Designing Policies
A common strategy for inventory problems is the "order-up-to" policy:

$$
X^\pi(S_t | \theta) =
\begin{cases}
\theta^{max} - R_t & \text{if } R_t < \theta^{min}, \\
0 & \text{otherwise},
\end{cases}
$$

where $\theta = (\theta^{min}, \theta^{max})$ are parameters that need to be tuned. The policy orders enough sausage to bring the inventory up to $\theta^{max}$ if the current inventory is below $\theta^{min}$.

### Evaluating Policies
Since we cannot compute the exact expectation in the objective function, we use the generated demand sequences to approximate it:

$$
\bar{F}^\pi(\theta) = \frac{1}{N} \sum_{n=1}^N \sum_{t=0}^T C(S_t, X^\pi(S_t | \theta), \hat{D}_t^{n+1})
$$

This allows us to compare different policies and choose the one with the highest estimated average performance.

## Designing Policies
Designing effective policies is a central challenge in sequential decision problems. Policies are essentially functions that map the current state of the system to a decision. There are two fundamental strategies for creating policies:

1. **Policy search:** This strategy involves searching over a family of functions to find the one that performs best on average over time. This can be done by simulating the performance of different policies under various scenarios and selecting the one that yields the best results.
2. **Lookahead policies:** These policies optimize the current decision by considering both its immediate impact and an approximation of its future consequences. This necessitates a model that can forecast the future state of the system based on the current state and decision.

These two strategies can be further divided into four classes of policies:

1. **Policy function approximations (PFAs):** These are analytical functions that directly map a state to an action. Examples include simple rules of thumb or linear models.
2. **Cost function approximations (CFAs):** These are parameterized optimization models that are designed to adapt and improve over time.
3. **Value function approximations (VFAs):** These policies approximate the long-term value of being in a particular state, and then choose actions that maximize this value.
4. **Direct lookahead approximations (DLAs):** These policies involve optimizing over a planning horizon, considering the potential future states and actions.

The choice of policy depends on the specific problem and the available computational resources. In practice, a combination of different policy classes may be used to achieve the best performance.

## Reference
* Chap 1 of Warren B. Powell (2022), "Sequential Decision Analytics and Modeling: Modeling with Python" [link](https://castle.princeton.edu/sdamodeling/)
* Chap 1 of Warren B. Powell (2022), "Reinforcement Learning and Stochastic Optimization: A Unified Framework for Sequential Decisions" [link](https://castle.princeton.edu/RLSO/)