# Outsmarting Human Design in Airline Revenue Management
## 3 Background
### Reinforcement Learning  
RL also uses the same underlying concepts behind DP to optimize MDPs. The RL agent's goal is to find the policy \(\pi\) that maps the observed state \(s\) to actions that maximize the expected return, and the procedure very often involves the computation of value functions. In contrast to DP, RL methods have strong emphasis on learning through the interaction with an environment. RL methods have mainly two important advantages over DP methods that we will exploit [7]. The first one is that they do not require an explicit _distribution model_, such as the one defined by \(p(s^{\prime}|s,a)\), that describes every possible outcome weighted by their probabilities when transitioning from one state to another. Instead, RL methods use a _sample model_, that produces just one example from all possible outcomes. In many applications, sample models are often much easier to obtain, particularly when the number of possible outcomes is very large, and/or the computation of the probability of each outcome is complex. Secondly, RL does not suffer from the _curse of dimensionality_ that occurs when the state-action space of a problem is so large that computing \(q(s,a)\) for all the state-action pairs becomes intractable. Alternatively, RL generates trajectories in the state-action space, and it performs updates at the pairs encountered along the way, directing the learning towards the pairs that occur more frequently, thus focusing computational resources where they are most currently needed to succeed in the task. There are many classes of RL algorithms, but we focus on the important class of actor-critic methods. Generally, these methods seek to compute the stochastic policy function \(\pi(a|s)\), also known as the actor, which returns the probability of selecting action \(a\) given state \(s\), and the value function \(v_{\pi}(s)\), also called the critic, which outputs the expected return from state \(s\) while following policy \(\pi\). In practice, the actor-critic methods usually model these two functions by the parameterized policy \(\pi(a|s;\theta)\approx\pi(a|s)\) and parameterized value function \(v(s;w)\approx v_{\pi}(s)\). The main idea behind actor-critic is to perform updates for parameters \((\theta,w)\) to maximize the performance metric \(J(\theta)\doteq v_{\pi}(S_{0})\) while following the policy gradient in a stochastic gradient ascent manner:  
\[\theta_{j+1}=\theta_{j}+\alpha\
abla_{\theta}J(\theta_{j}). \tag{3}\]  
The most used policy gradient estimator \(\
abla_{\theta}J(\theta_{j})\) has the following form (see policy gradient theorem [7] for details)  
\[\
abla_{\theta}J(\theta_{j})\approx\hat{\mathbb{E}}_{\pi}\big{[}\big{(}R_{t+ 1}+\gamma v(S_{t+1};w_{j})-v(S_{t};w_{j})\big{)}\
abla_{\theta}\ln\pi(A_{t}|S_ {t};\theta_{j})\big{]},\]  
where \(\hat{\mathbb{E}}_{\pi}\) indicates the empirical average over a finite batch of samples while following policy \(\pi\). The parameters for the value function \(v(s;w)\) can be updated according to  
\[w_{j+1}=\arg\min_{w}\ \hat{\mathbb{E}}_{\pi}\Big{[}\big{(}R_{t+1}+\gamma\hat{v} (S_{t+1};w_{j})-\hat{v}(S_{t};w)\big{)}^{2}\Big{]}, \tag{4}\]  
which can be computed through stochastic gradient descent. The actor-critic framework provides a wide range of RL algorithms (e.g., deep deterministic policy gradient [45], asynchronous advantage actor-critic [46], trust region policy optimization [47], proximal policy optimization [48], etc. ), each having their respective pros and cons. In principle, for our work, any of these algorithms could be used. Later, we present the EWL problem in its continuing nature, that is, the task of balancing between earning and learning never finishes, because, for every day, new booking data are added to the historical database and old data are deleted. For tasks with such a continuing nature (when the episode length \(\mathrm{T}\rightarrow\infty\)), we cannot choose the discount rate to be one (\(\gamma=1\)), because the agent's goal, which is maximizing the expected return, would diverge [7].