# Outsmarting Human Design in Airline Revenue Management
## 3 Background
### The Single-Leg Problem
For each active flight, the pricing optimization is modeled and solved as a finite Markov decision process (MDP) [44], which is defined by a tuple \(M=\langle\mathcal{S},\mathcal{A},r,p\rangle\), where \(\mathcal{S}\) is the state space, \(\mathcal{A}\) is the action space, \(r:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}\) is the reward function, and \(p:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow\mathbb{R}\) is the transition probability function. At each time step \(t\) (e.g., day), the RMS observes the inventory state of an active flight \(S_{t}\in\mathcal{S}\), denoted by the tuple \(S_{t}=(\tau,c)\), where \(\tau=\mathrm{T}-t\) is the number of time steps to departure, and \(c\) is the flight's remaining capacity. Then, it takes an action (i.e., it selects a fare) \(A_{t}\in\mathcal{A}=\mathrm{F}\) according to its pricing policy \(\pi:\mathcal{S}\rightarrow\ \mathcal{A}\). Multiple customers can arrive and interact with the RMS by choosing whether to book or not at the selected action \(A_{t}=f\). At the time step \(t+1\), with probability \(p(S_{t+1}|S_{t},A_{t};\psi)\), the remaining capacity \(c\) decreases by the number of bookings made at the previous time step. Finally, the RMS receives a reward equal to the immediate expected revenue given by  
\[R_{t+1}=r(S_{t},A_{t})=f\sum_{i=0}^{c}i\cdot\Pr\{i\,\mathrm{bochings}\mid c\}.\]  
Interactions with customers continue until the flight departs, at which point no further action can be taken, and the flight reaches the terminal state \(S_{T}=(0,c)\). The MDP is illustrated in Figure 2.  
Once the parameters of the demand model are obtained, the system needs to search for the policy \(\pi_{\psi}\) that maximizes the expected return \(\mathbb{E}[G_{t}\mid A_{t},\ldots,A_{T-1}\sim\pi_{\psi}]\), where the _return_ is defined as \(G_{t}\doteq\sum_{i=0}^{T-1}\gamma^{i}R_{t+i}\). The parameter \(\gamma\in[0,1]\) is called the _discount rate_, and it defines how farsighted the system is with respect to the revenue maximization (in the case of the airline's RM; the discount rate is very often chosen to be \(\gamma=1\)[14; 42], because the MDP has no loops, and the episode's horizon \(\mathrm{T}\) is finite, thus guaranteeing that the return is a finite quantity). The optimal policy according to the demand model defined by \(\psi\) can be computed through finite-state dynamic programming (DP) methods, where we first solve the action value function \(q_{\psi}(s,a)\) by making use of the Bellman optimality equation after setting the boundary condition \(q_{\psi}(S_{T},a)\doteq 0\),  
\[q_{\psi}(s,a)=r(s,a)+\gamma\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime}|s,a; \psi)\max_{a^{\prime}}q_{\psi}(s^{\prime},a^{\prime}). \tag{2}\]  
Figure 2: Backup diagram for optimization of a flight. Finally, the pricing policy for the flight is obtained by computing \(\pi_{\psi}(s)=\arg\max_{a}q_{\psi}(s,a)\). In principle, this optimization procedure must be replicated for each active flight; however, given the simplicity of the assumed demand model (no seasonality nor day of week variation), the same policy function can be used across all active flights.