## 4 Optimal Exercise Time of American Option
### Reinforcement Learning  
As AO valuation can be framed as a Sequential Decision-Making problem, it can be solved using a Reinforcement Learning (RL) framework. [PERSON] et al. [15] have shown that Least Square Policy Iteration (LSPI) can be a promising Reinforcement Learning method for pricing the American Option. The AO elements in an RL framework are as follows:  
* State (\(s\)): [Time, Underlying Asset Price];
* Action (\(a\)): Exercise the option or Continue holding the option;
* Reward (\(r\)): For continuation 0, except upon Exercise (when the Reward is equal to the immediate exercise value);
* State transitions: Based on stochastic process model for the underlying asset price. Since the immediate exercise value \(max((K-x_{t}),0)\) is known in any state, we only need to create a linear function approximation for the continuation value (action = continue). The function approximation is linear with respect to weights, although the feature functions themselves are non-linear. We can write the Q-value function as \[Q(s,a;\mathbf{w})= \begin{cases}\boldsymbol{\phi}(s)^{T}\cdot\mathbf{w}&\text{if }a= continue\\ g(s)&\text{if }a=exercise\end{cases}  \tag{16}\]  
where \(\mathbf{w}\) is the weight vector, \(\boldsymbol{\phi}(s)\) is the feature function vector, \(g(s)\) is the exercise value (immediate payoff). The state \(s\) is a tuple of underlying asset price \(x\) and time \(t\), \(s=(t,x_{t})\). The feature functions are a set of Weighted Laguerre Polynomials, similar to the work of [7]. However, these feature functions are applied both to underlying price and time. In this work, the following feature functions are used:  
\[ \begin{split}\phi_{0}(s)&=1\\ \phi_{1}(s)&=\exp\biggl{(}-\frac{\hat{x}_{t}}{2} \biggr{)}\\ \phi_{2}(s)&=\exp\biggl{(}-\frac{\hat{x}_{t}}{2} \biggr{)}(1-\hat{x}_{t})\\ \phi_{3}(s)&=\exp\biggl{(}-\frac{\hat{x}_{t}}{2} \biggr{)}\biggl{(}1-2\hat{x}_{t}+\frac{\hat{x}_{t}^{2}}{2}\biggr{)}\\ \phi_{4}(s)&=\exp\biggl{(}-\frac{\hat{x}_{t}}{2} \biggr{)}\biggl{(}1-3\hat{x}_{t}+\frac{3\hat{x}_{t}^{2}}{2}-\frac{\hat{x}_{t} ^{3}}{3}\biggr{)}\\ \phi_{5}(s)&=\exp\biggl{(}-\frac{\hat{x}_{t}}{2} \biggr{)}\biggl{(}1-4\hat{x}_{t}+\frac{3\hat{x}_{t}^{2}}{2}-\frac{2\hat{x}_{t} ^{3}}{3}+\frac{\hat{x}_{t}^{4}}{24}\biggr{)}\end{split}  \tag{17}\]  
where \(\hat{x}_{t}=x_{t}/K\) and \(K\) is the option's strike price. The same feature functions are applied to time, with \(\hat{x}_{t}\) in Equation (17) replaced by \(\hat{t}=t/T\), where T is the expiry date of the option (usually in years). In total, there are 12 feature functions, and \(\mathbf{w}\) is a vector of 12 elements. In LSPI [25], the optimal weight vector \(\mathbf{w}^{*}\) is determined by minimizing the following objective function:  
\[\mathcal{L}(\mathbf{w})=\sum_{i=1}^{n}(Q(s_{i},a_{i};\mathbf{w})-(r_{i}+ \lambda\cdot Q(s^{\prime}_{i},\pi_{D}(s^{\prime}_{i});\mathbf{w})))^{2} \tag{18}\]  
where \(r_{i}\) is an immediate reward, \(\lambda\) is the discount factor, \(s^{\prime}_{i}\) is the subsequent (next) state (\(s^{\prime}_{i}=(t+1,x_{t+1})\)), and \(\pi_{D}(s^{\prime}_{i})\) is the target decision policy (i.e., the policy that RL is trying to learn). The term \(Q(s_{i},a_{i};\mathbf{w})\) is the Q-value at time step \(i\) for the state-action pair \((s_{i},a_{i})\). The term \((r_{i}+\lambda.Q(s^{\prime}_{i},\pi_{D}(s^{\prime}_{i});\mathbf{w}))\) is known as the target value. Taking the semi-gradient of the objective function (Equation (18)) gives  
\[\sum_{i}\boldsymbol{\phi}(s_{i})\cdot(\boldsymbol{\phi}(s_{i})^{T}\cdot \mathbf{w}^{*}-\lambda\cdot Q(s^{\prime}_{i},\pi_{D}(s^{\prime}_{i});\mathbf{ w}^{*}))=0 \tag{19}\]  
The term \(\pi_{D}(s^{\prime}_{i})\) is a policy operator, where we need to apply greedy policy. In the case of AO, it is the max operator between the continuation and exercise values. This max operator can also be found in the classical Bellman optimality equation [5].