## 3 Preliminaries
### The Markov Decision Process and Reinforcement Learning  
Reinforcement learning is a general framework for sequential decision making under uncertainty. The reinforcement learning problem is often represented by a Markov Decision Process (MDP). A standard MDP is defined as follows:  
* State space \(\mathcal{\delta}\);
* Action space \(\mathcal{A}\);
* Initial observation distribution \(\rho:\mathcal{S}\rightarrow\mathbb{R}\);
* Transition distribution \(p:\rho:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow\mathbb{R}\);
* Reward function \(\tau:\mathcal{\delta}\times\mathcal{A}\rightarrow\mathbb{R}\). The agent makes decisions and takes actions according to the policy \(\pi\) and the current observation. The goal of the agent is to find the optimal policy \(\pi^{*}\) maximizing expected \(\gamma\)-discounted cumulative reward, called the value function \(V^{\pi}\). Thus, we have:  
\[V^{\pi}(s)\stackrel{{\mathrm{def}}}{{=}}\mathbb{E}[\sum_{t=0}^{ \infty}\gamma^{t}R(s_{t},a_{t})|s_{0}=s,a_{t}\sim\pi(a_{t}|s_{t}),s_{t+1}\sim P (s_{t+1},a_{t})] \tag{1}\]  
\[Q^{\pi}(s,a)\stackrel{{\mathrm{def}}}{{=}}R(s,a)+\gamma E_{s^{ \prime}\sim P(s^{\prime}|s,a)}V^{\pi}(s^{\prime}) \tag{2}\]  
The optimal action-value function \(Q^{*}=\max_{\pi}Q^{\pi}(s)\) satisfies the Bellman Optimality Equation:  
\[Q^{*}(s,a)\stackrel{{\mathrm{def}}}{{=}}E_{s^{\prime}\sim P(s^{ \prime}|s,a)}\max_{a^{\prime}\in A}[R(s,a)+\gamma Q^{*}(s^{\prime},a^{\prime})] \tag{3}\]  
In our experimental investigations, we adopt Proximal Policy Optimization (PPO) [9], a policy gradient method for reinforcement learning. PPO demonstrates superior efficiency and reliability compared to Trust Region Policy Optimization (TRPO) due to its utilization of first-order optimization techniques exclusively. Within the PPO framework, two primary variants exist: PPO-Penalty and PPO-Clip. PPO-Penalty approximates a KL-constrained update, akin to TRPO, but introduces a penalty term in the objective function to address the KL-divergence without imposing a hard constraint. Additionally, the penalty coefficient is automatically adjusted during training to ensure proper scaling. In contrast, PPO-Clip takes a different approach by omitting the KL-divergence term from the objective function and dispensing with explicit constraints. Instead, it relies on specialized clipping methods within the objective function to discourage substantial deviations between the new and old policies. For the current project, we employ PPO-Clip, as it offers convenience and ease of implementation, making it a more feasible choice compared to PPO-Penalty. The central concept behind PPO-Clip is the clipping surrogate objective, defined as follows:  
\[L^{\text{PPO}}(\theta)=E_{t}[min(r_{t}(\theta)A_{t},clip(r_{t}(\theta),1- \epsilon,1+\epsilon)A_{t})] \tag{4}\]  
where \(\epsilon\) is a hyperparameter. The first term inside the min is \(L^{\text{PPO}}\). The second term, \(clip(r_{t}(\theta),1-\epsilon,1+\epsilon)A_{t}\), modifies the surrogate objective by clipping the probability ratio, which removes the incentive for moving it outside of the interval \([1-\epsilon,1+\epsilon]\). The PPO-Clip is described in Algorithm 1. ```
Input: Initial policy parameters \(\theta_{0}\), initial value function parameters \(\phi_{i}\)
1 fork=0,1,2,\(\cdots\)do
2 Collect set of trajectories \(\mathcal{D}_{k}=\{\tau_{i}\}\) by running policy \(\pi_{k}=\pi(\theta_{k})\) in the environment. Compute rewards-to-go \(\hat{R}_{t}\)
3 Compute advantage estimates, \(\hat{A}_{t}\) (using any method of advantage estimation) based on the current value function \(V_{\phi_{k}}\)
4 Update the policy by maximizing the PPO-Clip objective: \(\theta_{k+1}=\arg\max_{\theta}\frac{1}{|\mathcal{D}_{k}|^{T}}\sum_{\tau\in \mathcal{D}_{k}}\sum_{t=0}^{T}\min\Big{(}\frac{\pi_{\theta}(a_{t}|s_{t})}{\pi_ {\theta_{k}}(a_{t}|s_{t})}A^{\pi\theta_{k}}(a_{t},s_{t}),g\Big{(}e,A^{\pi\theta _{k}}(a_{t},s_{t})\Big{)}\Big{)}\), typically via stochastic gradient ascent with Adam.