# Outsmarting Human Design in Airline Revenue Management
## 2 Heuristic Methods for Earning While Learning  
The EWL problem has its roots into the research fields of price optimization and optimal control (earning), and statistical learning and economics (learning about the demand behavior). Even though these research fields are each more than a century old, they were studied independently for a long time. The first attempts to combine these two fields [18; 19] did not receive much attention, perhaps due to the technical difficulties of the time, such as implementing pricing variation (e.g., updating catalogs), obtaining reliable estimates of the demand behavior, and tracking competition pricing. It was not until the digital and information era, when changing prices and accurately keeping track of how demand responds to them became much more effective, that academia and industry started to pay attention to the EWL problem. The literature of EWL is often organized based on how learning about the demand behavior happens. Many papers that investigate the EWL problem assume that the unknown demand behavior parameters are learned by the decision maker through the Bayesian framework [20; 21; 22], while others concentrate on the parametric framework [23; 24], and yet some others are oriented towards non-parametric models [25; 26]. Even though we have a special interest in the parametric model framework, many important discoveries generalize across frameworks, and thus we present them below. One of the most influential early works addressing the EWL problem proposes to learn the demand model parameters in a Bayesian fashion [27]. In theory, the optimal Bayesian policy could be computed via dynamic programming, but, in many situations of interest, no closed-form analytical expression exists. Thus, the proposed workaround, today known as certainty equivalent pricing (CEP), consists of selecting at each time step the price that would be optimal if the current demand model parameter estimates were correct. CEP is shown to be optimal under certain conditions, such as when only the intersect of a linear demand function is being estimated, but it is sub-optimal when estimating both the slope and the intersect of a linear demand model [28]. However, further analytical studies [29; 30] pointed to a more fundamental problem: the sequence of prices may converge to a sub-optimal price even with infinite data. This phenomenon has been named _incomplete learning_, and it has been demonstrated theoretically that, to  
Figure 1: Inside revenue management systems. avoid incomplete learning while maximizing revenue, the system must follow a policy that accumulates information about the demand behavior at an adequate rate without deviating too much from the greedy policy [24]. Several heuristic methods combining this principle with a classical parametric demand model [4; 8; 20; 31; 32] have been studied, in which controlled variance pricing (CVP) [2] has arguably been the most influential method. The CVP algorithm imposes a constraint on the greedy pricing policy that requires the selected prices not be too close to the average of previously selected prices. This constraint seeks to guarantee sufficient price dispersion by imposing a \"taboo interval\" over prices which the system is not allowed to select. Recently, a novel heuristic method [3] was found to outperform CVP in simulated studies and real-world benchmarks. This heuristic combines the revenue maximization and the accumulation of information into a single objective function in the form of  
\[U(f)=R(f)-\eta\bigg{(}\frac{\sigma_{\Psi}(f)}{\psi}\bigg{)}, \tag{1}\]  
where \(\eta\) is the trade-off parameter, \(R(f)\) represents the expected revenue for fare \(f\), and \(\sigma_{\Psi}(f)\) represents uncertainty of the demand behavior after selecting fare \(f\). At each time step, the system selects the fare that maximizes the objective function \(U(f)\). The main idea of this heuristic is to include the uncertainty of the demand model parameters in the optimization objective as a penalty term.