How to solve Dynamic Resource Allocation problems using RL

Sets

Before defining the State variable, let’s specify the sets:

• \(B\): Set of blood types
  (blood_type, age)}: {(A+, 0), (A+, 1), …, (B-, 0), (B-, 1), …, (O-, 6)}
• \(D\): Set of demand types plus hold blood for next period (\(d^\phi\))
  {blood_type, urgent, substitution_allowed}: {(A+, True, True), (A+, True, False), …, dº}

State variable (\(S_t\))

What do we need to know at time t?

\(S_t=(R_t,D_t)\)

where

• \(R_{tb}\): Units of blood of type \(b \in B\) available to be assigned or held at time \(t\). \(R_t=(R_{tb})_{b \in B}\)
• \(\hat{D}_{td}\): Units of demand of type \(d \in D\) that arose between \(t-1\) and \(t\). \(\hat{D}{t}=(\hat{D}_{td})_{d \in D}\)

Decision variables

What are our decisions at time \(t\)?

\(x_{tbd}\): Number of units of blood \(b \in B\) to assign to demand \(d \in D\) at time \(t\). \(x_t=(x_{tbd})_{b \in B d \in D}\)

Constraints (\(\chi_t\))

What constrain our decisions at time \(t\)?

\[ \sum_{d \in D}x_{tbd} = R_{tb}\qquad \forall b \in B \tag{1} \] \[ \sum_{b \in B} x_{tbd} \leq \hat{D}_{td}\qquad \forall d \in D \tag{2} \]

\[ x_{tbd} \in ℤ_0^+ \qquad \forall b \in B, d \in D \tag{3} \]

Equation (1) states that the sum of all units of blood allocated to all demand types must be equal to the available blood (\(R_{tb}\)) for each blood type \(b \in B\). Equation (2) guarantees that the summation of blood units allocated to a specific demand-type \(d\) must be less or equal to its demand in the current period (\(\hat{D}_{td}\)). Finally, (3) defines the integer nature of the decision variables.

Exogenous information(\(W_{t+1}\))

What do we learn for the first time between t and t+1?

\(W_{t+1} = (\hat{R}_{t+1},\hat{D}_{t+1})\)

where

• \(\hat{R}_{tb}\): Number of new units of blood of type \(b \in B\) donated between \(t-1\) and \(t\).
• \(\hat{D}_{td}\): Units of demand of type \(d \in D\) that arose between \(t-1\) and \(t\).

Transition function (\(S^M(.)\))

How does the problem evolve from t to t+1?

\[ \begin{aligned} S_{t+1} &= S^M(S_t, x_t, W_{t+1}) \\ &= (R_{t+1},\hat{D}_{t+1}) \end{aligned} \]

where \(S^M(.)\) denotes the transition function and depends on the current state \(S_t\), the decision vector \(x_t\), and the exogenous information \(W_{t+1}\).

This function states that \(S_{t+1} = (R_{t+1},\hat{D}_{t+1})\) but to get to this expression we need to also define a how or resource (blood supply) \(R_{t+1}\) evolves, i.e. the Resource transition function. In respect to the demand \(\hat{D}_{t+1}\), there is no need to model its evolution due to it completely depends on exogenous factors.

Resource transition function

\[ \begin{aligned} & R_{t+1} = (R_{t+1b'})_{b' \in B} \\ & R_{t+1b'} = R_{tb'}^x + \hat{R}_{t+1b'} \\ & R_{tb'}^x = f_R^T(x_{tbd^\phi}) \end{aligned} \]

where \(f_R^T(.)\) is the transition function between the number of units held as inventory (\(d^\phi\)) from type \(b \in B\) to the next period’s updated type \(b' \in B\). In our case, this model how the blood ages, i.e. blood age increases +1.

Objective function

What are we minimizing/maximizing and how?

In this problem, the objective is to maximize the summation of the expected total contribution along \(T\) weeks (periods). This can be expressed as

\[ \max_{\pi \in \Pi}\sum_{t \in T}\mathbb{E}[C_t(S_t,X^\pi(S_t))] \] Where,

• \(X^\pi(S_t)\) is a policy that determines \(x_t \in \chi_t\) given \(S_t\).
• \(C_t(S_t,x_t)\) is the total contribution at time \(t\). \[ C_t(S_t,x_t) = \sum_{b \in B}\sum_{d \in D}c_{bd}x_{tbd} \]

Next step

Until this point, the mathematical formulation of the problem was presented but it was never defined how to define our solution strategy (\(X^\pi(S_t)\)). The next section describes some alternative solution strategies and deep dives into two of them.

Handle an embedded expectation (\(\mathbb{E}\))

The new expectation (\(\mathbb{E}\)) makes our problem harder to solve. While in a single-period optimization we solve a simple linear optimization problem, the expectation value makes the problem stochastic. To address this issue we could sample scenarios but this can also complicate the optimization problem. However, there is a more elegant approach we could use named post-decision states.

Given that \(S_t\) is the state of the system immediately before making a decision, we can call it the pre-decision state variable,

\(S_t = (R_t, \hat{D}_t)\).

Now, let \(S_t^x\) be the state immediately after we make a decision but before any new exogenous information has arrived, this can be called the post-decision state variable. Therefore, in our case, the post-decision state can be defined as

\(S_t^x=(R_t^x)\)

where \(R_t^x = (R_{tb}^x)_{b \in B}\) is the number of units of blood of type \(b \in B\) held as inventory at time \(t\) to be available on \(t+1\). Notice that the dimensions of the post-decision state are reduced, compared to the pre-decision state, due to we are no longer considering the demand component.

Likewise, if it is possible to define a post-decision state, we can also define a post-decision value function approximation.

Let \(\bar{V}^x_t(S_t^x)\) be the approximated value of being at state \(S^x_t\) after making the \(x_t\) decision.

Using this new concept, it is possible to define our VFA policy as

\[ X^\pi(S_t) = \underset{x_t \in \chi_t}{\mathrm{argmax}}(\sum_{b \in B}\sum_{d \in D}c_{bd}x_{tbd} + \gamma\bar{V}^x_{t}(S^x_{t})) \]

Where,

• \(\bar{V}^x_{t}(S^x_{t})\) is an appropriately chosen approximation of the value of being at state \(S_t^x\).
• \(S_t^x\) is the post-decision state defined as \(S_t^x=(R_{tb}^x)_{b \in B}=(x_{tbd^\phi})_{b \in B}\)
• \(x_{tbd^\phi}\) is the number of units from type \(b \in B\) held as inventory \(d^\phi\) between \(t\) and \(t+1\).

If you want more details about how and why this works, please refer to Powell’s Approximate Dynamic Programming. 2nd Edition - Chapter 4. He provides the details and the logic behind the post-decision states.

Define a function for value approximation (\(\bar{V}_t\))

Lets remember that \(\bar{V}^x_{t}(S^x_{t})\) is an appropriately chosen approximation of the value of being at post-decision state \(S_t^x\). Then, we can define \(\bar{V}_t^x(S_t^x)\) as a separable piecewise-linear approximation.

\[ \bar{V}^x_t(S_t^x) = \bar{V}^x_t(R_t^x)=\sum_{b \in B}\bar{V}_{tb}(R_{tb}^x) \] Where

• \(\bar{V}_{tb}(R_{tb}^x)\) is the scalar piecewise-linear function for blood type \(b \in B\) at time \(t\).
• \(\bar{V}_{tb}(0) = 0\) for all \(b \in B\).

In other words, the approximated value of the post-decision state (\(\bar{V}^x_t(S_t^x)\)) is the summation of the approximated value function for each blood type \(b \in B\) considering \(R_{tb}^x\) units, i.e. \(\bar{V}_{tb}(R_{tb}^x)\) (notice the \(b\) index). Likewise, each of the blood type’s function can be defined as a scalar piecewise-linear function and can be expressed as:

\[ \bar{V}_{tb}(R_{tb}^x)=\sum_{r=1}^{R_{tb}^x}\bar{v}_{tb}(r) \]

It is important to understand that this function is determined by the set of slopes \(\bar{v}_{tb}(r)\) for \(r=0,1, ..., R_{\text{max}}\). where \(R_{\text{max}}\) is an upper bound on the number of blood supply units of a particular type. The following figure shows an example of one \(\bar{V}_{tb}( )\) scalar piecewise-linear function for resource type \(b\). In the figure, it is possible to see that the value of the function depends on the slopes\(\bar{v}_{tb}\).

Figure. Scalar piecewise value function (\(\bar{V}_{tb}(R_{tb}^x)\)) for a particular resource type \(b\)

In summary, our value function approximation, i.e. the separable piecewise linear function, instead of directly estimating the value of a given state, will estimate the marginal value (slopes) for each potential number of units for each resource/blood type. Using this approximation has two advantages 1) it is a linear approximation that can be exploited using a linear optimization algorithm, and 2) it is possible to get an estimate of the slope for each type of resource all at the same time (Powell, 2022).

Choose a solution method to efficiently find \(x_t\) on each decision period \(t\)

Based on the post-decision state definition and the separable piece-wise value function approximation, it is possible to model our policy (\(X^\pi(S_t)\)) as a Network Flow problem and solve it using a minimum-cost flow solving algorithm (but aiming to maximize our reward).

The following figures show the network representation of the problem. The first figure shows the network model without the piecewise linear value approximation. It comprises three main layers: 1) Supply blood types nodes (\(R_t\)), 2) Demand nodes (\(D_t\)), and 3) Inventory nodes (\(R^x_t\)). The bold node between the second and third layers is a sink node. The arcs between the first and the second layers represent the potential serving decisions between the supply and demand nodes. Likewise, the arcs between the first and the third layer represent the decision of keeping the blood as inventory for the next period (“hold” decision - \(d^\phi\)). Finally, the arcs between the demand nodes and the sink node determine the maximum amount of blood that could be served for each demand time using the demand value (e.g. \(\hat{D}_{t,\text{AB+}}\)) as the arc upper bound.

Figure. Policy’s network model without piecewise linear value approximation

In addition, the next figure shows the same network but including piecewise linear value function approximation in a new fourth layer of bold nodes (This new layer is a representation of the rightest super-sink node). The piecewise linear value function approximation is modelled as a set of parallel arcs between the Inventory nodes (3) and the sink node, and the costs of these nodes are defined by the slopes/marginal values (\(\bar{v}_{tb}(r)\)) of the piecewise linear function of each blood type (see the previous section). A simple way to create this modelling trick is to create one arc per each potential inventory unit to be held for future periods, each of these arcs will have its corresponding contribution (\(\bar{v}_{tb}(r)\)) and an upper bound of 1. Finally, given the problem structure, the piecewise linear function is concave; therefore; the slopes of the function are monotonically decreasing, i.e. \(\bar{v}_{tb}(r) \ge \bar{v}_{tb}(r+1)\).

Figure. Policy’s network model with including piecewise linear value function approximation

This network model can be solved easily using a linear programming solver (e.g. CBC, Glop, Glpk, Xpress, Cplex, Gurobi, etc.).

Estimate the value of (non-)visited states.

The previous section described how to use the slopes or marginal values \(\bar{v}_{tb}(r)\) to obtain an approximation of the value function; however, it didn’t define how they are estimated. This section describes how can be leverage sample paths, “exploration” states and the monotonic property of the piecewise linear function’s slopes to estimate the value functions for both visited and non-visited states.

Slopes’ monotonical property

Using the exploration states, we were able to update two of the slopes of the piecewise linear function; however, it is possible that after the update, our function doesn’t hold the monotonic property anymore (i.e. \(\bar{v}_{tb}(r) \ge \bar{v}_{tb}(r+1)\)). This seems like an issue; however, it provides us with the opportunity to update the whole set of slopes with more accurate estimates without exploring all the possible states!!!

In the literature exists multiple approaches to restore the monotonicity of a function. Powell (2022) in Chapter 20 shows three alternatives that he has used. The following figures illustrate one of the approaches using The leveling algorithm.

Figure. Steps of The leveling algorithm. (a) The initial monotone function, with the observed \(R\) and the observed value of the function \(\tilde{v}\); (b) The function after updating the single-segment, producing a non-monotone function; (c) the function after the monotonicity is restored by leveling the function.

The whole VFA algorithm

As the reader can notice, the VFA algorithm requires multiple concepts and merge them together including value function approximation, separable piecewise-linear function, scalar piecewise linear function (based on slopes), pre and post-decision states, sample paths, exploration states and even monotonicity property. Let’s see how to put all of them in a single algorithm.

% This a VFA used to solve the Blood Management Problem
\begin{algorithm}
\caption{VFA algorithm using separable piecewise linear approximation}
\begin{algorithmic}
\STATE  \textbf{Step 0.} Initialization
\STATE $\qquad$ \textbf{0a.} Initialize $\bar{V}_t(S_t^x)$ for all post-decision states $S_t^x$, $t={0,1,...,T}$.
\STATE $\qquad$ \textbf{0b.} Set $n = 1$.
\STATE \textbf{Step 1.} Chose a sample path $\omega^n$.
\STATE $\qquad$ \textbf{Step 2.} Do for $t=0,1,...,T$:
\STATE $\qquad\qquad$ \textbf{2a.} Let the state variable be
\STATE $\qquad\qquad\qquad\qquad$ $S_t^n = (R_t^n, \hat{D}_t(\omega^n))$
\STATE $\qquad\qquad\qquad$ And let the exploration states be
\STATE $\qquad\qquad\qquad\qquad$ 
        $S_{tb'}^{n+} = ((R_{tb}^n + 1^{b=b'})_{b \in B}, \hat{D}_t(\omega^n)) \quad 
        \text{for all } b' \in B $
\STATE $\qquad\qquad\qquad\qquad$ 
        $S_{tb'}^{n-} = ((R_{tb}^n - 1^{b=b'})_{b \in B}, \hat{D}_t(\omega^n)) \quad 
        \text{for all } b' \in B \quad (\text{if } R_{tb}^n > 0)$ 
\STATE $\qquad\qquad$ \textbf{2b.} Solve
\STATE $\qquad\qquad\qquad\qquad$ 
        $\tilde{V}_t^n(S_t^n) = 
        \max_{x_t \in \chi_t}(\sum_{b \in B}\sum_{d \in D}c_{bd}x_{tbd} +
        \gamma\sum_{b \in B}\bar{V}^{x, n-1}_{t}(R^x_{tb}))$
\STATE $\qquad\qquad\qquad$ Let $x_t^n$ be the decision that solves the maximization problem.
\STATE $\qquad\qquad$ \textbf{2c.} 
        Find $\tilde{V}_t^{n+}(S_t^n)$ and $\tilde{V}_t^{n-}(S_t^n)$ using the same policy.
\STATE $\qquad\qquad$ \textbf{2d.} Compute the slopes
\STATE $\qquad\qquad\qquad\qquad$ 
        $\tilde{v}_{tb}^{n+} = 
        \tilde{V}_t^n(S_{tb}^{n+}) - \tilde{V}_t^n(S_t^n) 
        \quad \text{for all } b \in B$
\STATE $\qquad\qquad\qquad\qquad$
        $\tilde{v}_{tb}^{n-} = 
        \tilde{V}_t^n(S_t^n) - \tilde{V}_t^n(S_{tb}^{n-}) 
        \quad \text{for all } b \in B$
\STATE $\qquad\qquad$ \textbf{2e.} If $t>0$ update the value function:
\STATE $\qquad\qquad\qquad\qquad$ 
        $\bar{V}_{t-1}^n=
        U^V(\bar{V}_{t-1}^{n-1}, S_{t-1}^{x,n}, \tilde{v}_{tb}^{n+}, \tilde{v}_{tb}^{n-})$
\STATE $\qquad\qquad$ \textbf{2f.} Update the state variable 
\STATE $\qquad\qquad\qquad\qquad$ $S_{t+1}^n=S^M(S_t^n,x_t^n,W_{t+1}(\omega^n))$
\STATE \textbf{Step 3.} Let $n=n+1$. If $n<N$, go to step 1.
\end{algorithmic}
\end{algorithm}