Model Based RL​

• Model: Transition Probability, Reward Function, State, Action, Discount Factor
• Planning: use the learned models to evaluate possible actions, construct or iprove a value function or policy using Value/Policy Iteration.
• Underlying MDP: The env's actual state transitions and reward structure.
  • Transition Model $P(s'|s,a)$
  • Reward Model $R(s,a)$
  • Goal: Approximate the env's MDP and use if for planning.

Aspect	Model-Free RL	Model-Based RL
Environment Model	No model available (transition dynamics)	Learn a model from experience
Learning	Directly learn a value function and/or policy from experience	Use the learned model to plan a value function and/or policy
Methods	Learn directly from experience	Use a simulator with DP, Model-Free RL, or Policy Search

Advantages of Model-Based RL​

• Efficient Model Learning: Supervised learning can efficiently learn transition and reward models from experience.
• Model Uncertainty: The learned model can estimate uncertainty in its prediction

Disadvantages of Model-Based RL​

• Two-Step Process: First learn the environment model, then use it to construct a value function or policy.
• Two Sources of Approximation Error:
  • Approximated Model Error: The learned model may inaccurately predict transitions or rewards.
  • Approximated Planning Error: Planning with the learned model may produce approximate or suboptimal results.
  • Compounding Error: Model and planning errors can accumulate, reducing the accuracy of the final policy.

MDP Model​

$\text{MDP} = \langle S, A, P, R \rangle_{\eta}$

• Assumption: State space $S$ and Action space $A$ are known and the env satisfies the Markov property.
• Model $\mu = \langle P_{\eta}, R_{\eta} \rangle$ is parameterized by $\eta$ and represents state-transitions and rewards.
  • $P_{\eta} \approx P$
  • $R_{\eta} \approx R$

$S_{t+1} \sim P_{\eta}(s_{t+1} | s_t, a_t)$ $R_{t+1} \sim R_{\eta}(r_{t+1} | s_t, a_t)$

$P(s_{t+1}, R_{t+1} | s_t, a_t) = P(s_{t+1} | s_t, a_t) P(R_{t+1} | s_t, a_t)$

• Assume that the next state and reward are conditionally independent given the current state and action (not a consequence of the Markov property).
• This allows transition and reward distributions to be modeled separately.

Model Learning​

• Goal: Approximate a model $\mu_\eta$ from experience $\{S_1, A_1, R_2, \ldots, S_T\}$.
• Supervised Learning: Use $(S_t, A_t)$ as input and $(R_{t+1}, S_{t+1})$ as targets.
• Loss Function: Measure prediction errors using a loss function (e.g., MSE).
• Empirical Loss: Average prediction error over observed training data.
• Use supervised learning framework, find parameters $\eta$ that minimize empirical loss (MSE).

$$\eta^* = \arg \min_\eta L(\eta)$$

Lookup Table Model​

• Underlying Model is presented as a lookup table.
• A model is an explicit $\text{MDP}, \hat{P}, \hat{R}$

$\hat{P}_{ss'}^a = \frac{1}{N(s,a)} \sum_{t=1}^T 1((S_t, A_t, S_{t+1}) = (s,a,s'))$

• $N(s,a)$ is the number of times State-Action pair has been visited.
• $1$: Indicator function that is 1 if the condition is true, 0 otherwise.
• $\hat{P}_{ss'}^a$ is the estimated probability of transitioning from state $s$ to state $s'$ under action $a$.

$\hat{P}(s'|s,a) = \frac{N(s,a,s')}{N(s,a)}$

• Estimated Transition Probability by counting the number of times the State-Action-Next State tuple has been observed.

$$\hat{R}_s^a = \frac{1}{N(s,a)} \sum_{t=1}^T 1((S_t, A_t) = (s,a)) R_{t+1}$$

• Calculate the average reward for the State-Action pair.

Single Action MRP Example​

Two States $\{A, B\}$ and no discount, 8 episodes of learning.

• A → B: 100% transition probability, reward = 0.
• B → Terminal: 75% chance of reward 1, 25% chance of reward 0.

Episode	Experience
1	A, 0, B, 0
2	B, 1
3	B, 1
4	B, 1
5	B, 1
6	B, 1
7	B, 1
8	B, 0

• MC: Estimates values using observed complete returns.
  • $V(B) = 6/8 = 0.75$
  • $V(A) = 0$
• TD: Uses bootstrapping, updates a state's value using the estimated value of the next state.
  • $V(B) = 0.75$
  • $V(A) \leftarrow \gamma + \gamma V(B) = 0 + 0.75 = 0.75$
  • Requires a backup of $A$ after $V(B)$ has been learned.

Planning with a model​

• Given Model $\mu_\eta = \langle P_{\eta}, R_{\eta} \rangle$
• Solve $\text{MDP} \langle S, A, P_{\eta}, R_{\eta} \rangle$ by $\eta$.
• With Planning algorithm:
  • Value Iteration
  • Policy Iteration
  • Tree searching
  • etc.

Sample-based Planning​

• Generate a lot of samples or data then, use model free methods such as MC, SARSA, Q-learning, etc. to plan.
• $S_{t+1} \sim P_{\eta}(S_{t+1} | S_t, A_t)$
• $R_{t+1} \sim R_{\eta}(R_{t+1} | S_t, A_t)$
• Data Efficiency: Reduce real environment interactions by learning from simulated experiences.

Monte Carlo Search​

• Given a model $\mu_v$ and simulated policy $\pi$
• For each $a \in A$:

$$Q(S_t, a) = \frac{1}{K} \sum_{k=1}^K G_t$$

• Simulate $k$ episodes from current state $s_t: \{ s_t, a, R_{t+1}^k, \ldots, S_T^k \} \sim \mu_v, \pi$
• Evaluate actions by mean returns (MC evaluation)
• $G_t^{(k)}$: Return from the $k$-th simulation.
• Select current action with max value

$a_t = \arg\max_{a \in A} Q(s_t, a)$

e.g.

Action	Episode 1	Episode 2	Episode 3
Left	3	5	4
Right	2	1	3

• $Q(s_t, \text{Left}) = \frac{3 + 5 + 4}{3} = 4$
• $Q(s_t, \text{Right}) = \frac{2 + 1 + 3}{3} = 2$
• Select action with max value: $\text{Left}$

Expectimax Tree​

• White Node: Choose action with max value.
• Black Node: Average state values of all possible actions.
• Compute Optimal $Q(s,a)$ values for the current state by construction an expectimax tree.

$$Q(s,a)=\sum_{s'}P_\nu(s'|s,a) \left[R_\nu(s,a,s')+\gamma V(s')\right]$$ $$V(s)=\max_a Q(s,a)$$

• $P_\nu(s'|s,a)$: Transition probability.
• $R_\nu(s,a,s')$: Expected Reward
• $V(s')$: Value of the next state.

Limitations of Expectimax Tree​

$$O((|\mathcal S|\times|\mathcal A|)^H)$$

• Scaling Exponentially with Depth: Tree size grows exponentially with depth $H$.
• $|\mathcal S|$: Number of possible states.
• $|\mathcal A|$: Number of possible actions.
• $H$: Depth of the tree.

Monte Carlo Search Tree, MCTS​

• Given a model $\mu_v$
• Build a search tree rooted at the current state $s_t$, sample actions and next states.
• Iteratively Construct and update the tree by performing $K$ simulation episodes starting from the root node.
• Once search is finished, select the current action with maximum value in the search tree.

$a_t = \arg\max_{a \in A} Q(s_t, a)$

Aspect	MCTS	Expectimax Tree
Expansion	Construct partial search tree	Construct full search tree up to a given depth
Exploration	Select branches using UCB	Explore all possible branches
Evaluation	Estimate values using sampled returns	Calculate expected values using transition probabilities
Action Selection	Select actions based on estimated values	Select actions with maximum expected values
Computational Cost	Controlled by simulation budget	Exponential in search depth
Trade-off	More efficient, but approximate	More exhaustive, but computationally expensive

Tree Traversal​

$$Q(s,a,i) = \underbrace{V_i}_{\text{Exploitation}} + \underbrace{c\sqrt{\frac{\ln n(s)}{n(s,a)}}}_{\text{Exploration}}$$

• Use Upper Confidence Bound (UCB) to select which branches to explore.
• $c$: Exploration coefficient.
• $n(s)$: Number of visits to state $s$.
• $n(s,a)$: Number of visits to state-action pair $(s,a)$.
• Exploration Bonus: Encourages selecting less-visited actions.
• UCB: Balances exploitation of high-value actions and exploration of less-visited actions.
  • In bandit problems, $c$ is a constant to balance exploration and exploitation.

Node expansion​

• Add a new child node to the search tree for an unexplored action.

Rollout​

• Perform a random simulation from the expanded node until termination or a depth limit.
• Calculate the total return from the simulation.

$$\begin{aligned} & \text{ROLLOUT}(S_i) \\ & \quad \text{Loop: } \\ & \quad \quad \text{if } S_i \text{ is a terminal } \\ & \quad \quad \quad \text{return } S_i \\ & \quad \quad \quad \text{else } \\ & \quad \quad \quad \quad A_i = \text{random available action } S_i \\ & \quad \quad \quad \quad S_i = \text{Simulate } (A_i, S_i) \\ \end{aligned}$$

Backpropagation​

• Propagate the simulation return back through the selected path to the root.
• Update visit counts and estimated values of the visited nodes.

Advantages of MCTS​

• Highly Selective Best-First Search
• Evaluates states dynamically, unlike DP.
• Use Samples to break curse of dimensionality.
• Works for "black box" model.
• Computationally efficient.

Reinforce Learning with Human Feedback, RLHF​

Why Human Feedback?​

• Some tasks do not have clear or automatically measurable rewards.
• Humans can provide:
  • Preferences: Choose between two outputs (A > B).
  • Rankings: Rank multiple outputs (1st, 2nd, 3rd).
  • Evaluations: Judge whether an answer is better or worse.
• Example: Evaluating which chatbot response is more polite.

Alignment Problem​

• LLMs are pretrained to predict text, not necessarily to generate useful responses.
• Generated text may be harmful, biased, or factually incorrect.
• Traditional evaluation metrics (e.g., BLEU) do not directly capture human preferences.
• Human feedback helps align model behavior with human preferences for helpfulness, truthfulness, and safety.
• Example: A model may generate plausible but impractical coding advice.

Core Idea of RLHF​

• Human Feedback: Use human evaluations and preferences to guide model training.
• Alignment: Align model behavior with human expectations and preferences.
• Optimization: Train models to maximize rewards reflecting human preferences rather than only next-token likelihood.
  • Goal of LLM's pretraining: $\max_\theta \sum_{t}\log P_\theta(x_t | x_{<t})$
    • Maximize the likelihood of the next token.
  • Goal of RLHF: $\max_\theta \mathbb{E}_{y \sim \pi_\theta(\cdot|x)} R(x, y)$
    • Maximize the expected reward of human-preferred responses.
• Application: Widely used in NLP and LLM alignment.

RLHF Training Pipeline​

Pre-training → SFT → Reward Model Training → RL Optimization

1. Pre-training: Train a base model on a large text corpus using next-token prediction.
2. Supervised Fine-Tuning (SFT): Fine-tune the base model on high-quality instruction-response examples.
3. Reward Model Training: Train a reward model using human-labelled preferences to predict response quality.
4. Reinforcement Learning: Optimize the model's policy to maximize rewards predicted by the reward model.

Step 1. Pre-training​

• Select a base model pretrained on a massive text corpus.
• Learns general knowledge and language patterns.
• Limitation: May produce biased, unsafe, or irrelevant responses.

Step 2. Supervised Fine-Tuning (SFT)​

• Goal: Train the base model to follow instructions and generate reasonable responses.
• Collect high-quality demonstration data (instruction, input, output).
• Fine-tune the base model on the curated dataset.
• Limitation: Instruction-following does not guarantee alignment with human preferences.

Step 3. Reward Model Training​

• Goal: Learn a reward function that reflects human preferences.
• Generate multiple responses for the same prompt.
• Humans compare or rank the responses.
• Train a reward model to assign scores based on human preferences.
• Example: A professional, polite response (B) is preferred over a blunt response (A): B > A.
• Outcome: Convert human judgments into numerical reward scores.

Step 4. RL with Human Feedback​

• Goal: Optimize the LLM policy using the trained reward model.
• Algorithm: PPO (example).
• Generate responses using the current policy.
• Score responses using the reward model from Step 3.
• Update the policy to maximize reward.
• Use a KL penalty to limit deviation from the reference policy and reduce over-optimization.
  • KL Penalty: Penalizes large deviations between the updated policy and the reference policy.
  • Higher KL Penalty → More conservative policy updates.

$$D_{KL}(P\|Q)=\sum_x P(x)\log\frac{P(x)}{Q(x)}$$ $$\max_\theta\left[ \mathbb E[R(x,y)] -\beta D_{KL}(\pi_\theta\|\pi_{\mathrm{ref}}) \right]$$

Strategy	CNN	LLM
Feature Extraction	Freeze backbone, train classifier head	Freeze base model, train task-specific head
Partial Fine-Tuning	Freeze early layers, update selected layers	PEFT (e.g., LoRA): Freeze base weights, train small additional parameters
Full Fine-Tuning	Update all pretrained weights	Update all pretrained weights (not PEFT)

Chatgpt​

Benefits of RLHF​

• Alignment: Aligns model behavior with human values and preferences.
• Safety & Usefulness: Encourages safer, more useful responses with higher human acceptance.
• Ambiguous Goals: Handles tasks where rewards are difficult to define explicitly.

Challenges of RLHF​

• Cost: Requires extensive human annotations, making training expensive.
• Human Bias: Biases in human feedback can be transferred to the reward model and policy.
• Over-optimization: Models may exploit the reward function rather than produce genuinely better responses (Reward Hacking).
• Scalability: Collecting and applying human feedback becomes difficult as models and tasks scale.

Applications of RLHF​

• ChatGPT: Improvement in safety and helpfulness
• Claude: Constitutional AI for more nuanced alignment
• Gemini: Large-scale RLHF for multimodal capabilities
• Robotics: Learning task from human demonstrations
• Teaching robots via human feedback to cook
• Medical AI systems trained with doctor's feedback to align with human expert medical standards.

Policy Search Methods​

Instead of $V$ and $Q$ functions, we directly estimate the optimal policy.

$\pi^{\theta}(a|s) \approx P(a|s, \theta)$

• Policy was generated directly from the value function (e.g. $\epsilon$-greedy)
• Parameterize the policy directly.
  • Instead of $v(s,w)$ or $\hat{q}(s,a,w)$, we have $\pi^{\theta}(a|s)$
  • Given a particular state $s$, what actions should we take? (What is probability of that particular action?)
  • $\theta$ is a learnable parameter which could be a neural network.

Value-based and Policy-based Methods​

• Value-based: Learnt value function, Implicit policy (e.g. $\epsilon$-greedy)
• Policy-based: No value function, Learnt policy.
  • Good convergence properties
  • Effective in high-dimensional or continuous action spaces
    • if it is really continuous and large, it is not efficient as well.
  • Can learn stochastic policies.
  • Sometimes policies are relatively simple, values and models are complex.
  • Typically reaches local optima.
  • Obtained knowledge is specific and does not generalize well.
• Actor-Critic: Learnt value function, Learnt policy.

Policy Gradient Techniques​

• Trust-Region Based: Optimize the policy in a trust zone (closer circle).

Stochastic policies​

Rock-Paper-Scissors​

• A deterministic policy is easily exploited
  • Deterministic policy: If we follow a set of action or sequence of actions, we will definitely reach the goal and will always reach teh same location.
• A uniform random policy is optimal policy.

Grid World​

$$\phi(s,a) = \big(\underbrace{1 0 1 0}_{walls}, \underbrace{0 1 0 0}_{actions}\big)$$

• Agent cannot differentiate between the grey states.
• $\phi(s,a)$ features describing state $s$ and action $a$.
• $\phi(s,E) = (\underbrace{1, 0, 1, 0}_{\text{NESW}}, \underbrace{0, 1, 0, 0}_{\text{NESW}})$ is the North and the South are walls and the agent will move to the East.
• If $\pi(\text{grey}) = W$, then when the agent is in the left grey state, it will move west, get stuck in a loop, and never reach the goal.

• Therefore, an optimal stochastic policy moves randomly $E$ or $W$ in grey states.
  • $\pi_{\theta}(\text{wall to N and S, move E}) = 0.5$
  • $\pi_{\theta}(\text{wall to N and S, move W}) = 0.5$
• The agent will reach the goal with high probability.
• Policy-based methods can learn Stochastic policies. 4563

Objective Function in Policy-based Methods​

Given a policy $\pi_{\theta}(a|s)$ with parameters $\theta$, the goal is to find the best $\theta$.

$$J_1(\theta) = v_{\pi_{\theta}}(S_1)$$

• In an episodic task (with an end state), $J_1(\theta)$ is for that particular start state and measures how much expected return we can get.
• $S_1$ is the start state.
• $J(\theta)$ is the measure of the quality of the policy or the objective function to optimize.

$$J_{avV}(\theta) = \sum_{s}\mu_{\pi\theta}(s)v_{\pi\theta}(s)$$

• In continuing environments (doesn't have an end state), consider the states and take the average value weighted by how often the agent visits each state.
• $\mu_{\pi\theta}(s)$ is how often the agent is visiting that particular state $s$.

$$J_{avR}(\theta) = \sum_{s}\mu_{\pi\theta}(s)\sum_{a}\pi_{\theta}(a|s)\sum_{r}p(r|s,a)r$$

• Use the average reward per time step.
• Small batches can be used to estimate this average reward during training.

Policy-based Methods​

• Policy-based RL is an optimization problem, find $\theta$ that maximize $J(\theta)$.
  • $J(\theta)$ is the policy objective function.
• Gradient-free methods: Hill Climbing, Genetic Algorithms, ...
• Gradient-based

$\Delta{\theta} = \alpha \nabla_{\theta} J(\theta)$

• Policy gradient method will search for a local minimum in $J(\theta)$ by ascending the gradient of the Policy.
  • why ascending? because we want to maximize the objective function's value/rewards.
  • $\nabla_{\theta} J(\theta) = \begin{pmatrix} \frac{\partial J(\theta)}{\theta_1} \\ \vdots \\ \frac{\partial J(\theta)}{\theta_n} \end{pmatrix}$
  • $\alpha$ is the step size.

$$\Delta{\theta} J(\theta) = \nabla_{\theta} \mathbb{E}_d[v_{\pi\theta}(s)]$$

• Assume the policy $\pi_{\theta}$ is differentiable.
• Compute an estimate of the policy gradient.
• Compute $\Delta{\theta} J(\theta)$ using Monte Carlo samples since we need to explore the environment, gather information, and then learn the policy.

Score Function​

• Assume the policy $\pi_{\theta}$ is differentiable.
• $\nabla_{\theta} \pi_{\theta}(s, a)$ is the gradient.

$$\begin{aligned} \nabla_\theta \pi_\theta(s,a) &= \pi_\theta(s,a) \frac{\nabla_\theta \pi_\theta(s,a)} {\pi_\theta(s,a)} \\ &= \pi_\theta(s,a) \nabla_\theta \log \pi_\theta(s,a) \quad \big( \because \ \nabla_\theta \log f(\theta) = \frac{1}{f(\theta)} \nabla_\theta f(\theta) \big) \end{aligned}$$

• Multiplying and dividing by $\pi_\theta(s,a)$ is called the Likelihood Ratio Trick.
  • Since $\frac{\pi_\theta(s,a)}{\pi_\theta(s,a)} = 1$, this does not change the original value.
    • $\nabla_\theta \pi_\theta(s,a)$ is Gradient of the policy
    • $\pi_\theta(s,a)$ is the policy.
    • $\frac{\nabla_\theta \pi_\theta(s,a)}{\pi_\theta(s,a)}$ measures how sensitive the policy is to changes in $\theta$, relative to the policy value itself.
  • From the derivative rule of the logarithm, $\frac{\nabla_\theta \pi_\theta(s,a)}{\pi_\theta(s,a)} = \nabla_\theta \log \pi_\theta(s,a)$.
• Score Function: $\nabla_\theta \log \pi_\theta(s,a)$.

Policy Gradient Theorem​

Policy Gradient = How policy changes $\times$ How good the action is.

• It generalizes the likelihood ratio approach to multi-step MDPs.
• Replaces the instantaneous reward $r(s,a)$ with the action value function $Q^{\pi\theta}(s,a)$.
  • $s_1 \xrightarrow{a_1} s_2 \xrightarrow{a_2} s_3 \xrightarrow{a_3} \text{Goal}$

$$\ \nabla_\theta J(\theta) = \mathbb{E}_{\pi\theta}[ \underbrace{\nabla_\theta \log \pi_\theta(s,a)}_{\text{Score Function}} \underbrace{Q^{\pi\theta}(s,a)}_{\text{Action Value Function}} ]$$

• The theorem applies to start state objective, average reward, and average value objectives.
• $Q^{\pi_\theta}(s,a)$: the expected long-term reward starting from state $s$, taking action $a$ and following policy $\pi_\theta$
• $\nabla_\theta \log \pi_\theta(s,a)$: How sensitive the policy is to changes in $\theta$.
• $\mathbb{E}{\pi\theta}[\cdot]$: Average over all possible states and actions according to the policy $\pi_\theta$.
• $\nabla_\theta J(\theta)$: The direction in which $\theta$ should be changed to increase the objective $J(\theta)$.

Simplified Policy Gradient steps​

1. Loop
2. Collect trajectories for Policy $\pi_\theta$
3. Estimate advantage function $A$
4. Compute Policy Gradient $\hat{g}$
5. Update Policy Parameter $\theta_{\text{new}} = \theta_{\text{old}} + \alpha \hat{g}$

• $\hat{g}$ is the estimated policy gradient.
  • Can be MC policy gradient, or Actor-Critic Policy Gradient.
• if $\alpha$ is too big, data collected under bad policy and it cannot be recovered.
• if $\alpha$ is too small, it is not efficient use of experience.

REINFORCE Algorithm​

• Monte Carlo Policy Gradient: explore and learn from the environment and learn the optimal policy.
• Update Parameters by Stochastic Gradient Ascent.
• Using policy gradient theorem: find the partial derivatives to find the direction of the gradient.
• Using return $v_t$ as an unbiased sample of $Q^{\pi\theta}(s,a)$.
  • $Q^{\pi\theta}(s_t,a_t) = \mathbb{E}_{\pi\theta}[v_t | s_t, a_t]$

$\Delta{\theta} = \alpha \nabla_\theta \log \pi_\theta(s_t,a_t) v_t$

$$\begin{array}{l} \textbf{Function REINFORCE} \\ \qquad \text{Initialize } \theta \text{ arbitrarily} \\ \qquad \textbf{for each episode } \{s_1,a_1,r_1,\ldots,s_{T-1},a_{T-1},r_T\} \sim \pi_\theta \textbf{ do} \\ \qquad\qquad \textbf{for } t=1 \textbf{ to } T-1 \textbf{ do} \\ \qquad\qquad\qquad \theta \leftarrow \theta + \alpha \nabla_\theta \log \pi_\theta(s_t,a_t) v_t \\ \qquad \textbf{return } \theta \\ \end{array}$$

REINFORCE: Sutton and Barto​

$$\begin{array}{l} \textbf{Input: } \text{a differentiable policy parameterization } \pi(a \mid s,\theta) \\ \textbf{Algorithm parameter: } \text{step size } \alpha > 0 \\ \textbf{Initialize } \text{policy parameter } \theta \in \mathbb{R}^{d'} \text{ (e.g., to 0)} \\ \\ \textbf{Loop forever (for each episode):} \\ \qquad \text{Generate an episode } S_0,A_0,R_1,\ldots,S_{T-1},A_{T-1},R_T, \text{ following } \pi(\cdot \mid \cdot,\theta) \\ \qquad \textbf{Loop for each step of the episode } t=0,1,\ldots,T-1: \\ \qquad\qquad G \leftarrow \sum_{k=t+1}^{T} \gamma^{k-t-1}R_k \qquad (G_t) \\ \qquad\qquad \theta \leftarrow \theta + \alpha \gamma^t G \nabla \ln \pi(A_t \mid S_t,\theta) \end{array}$$

• Slow to converge.
• Going to have low bias but high variance.

Actor-Critic​

• Actor has a supervisor (Critic) that tells it how good or bad the action actor took is.
• Actor: Controls agent's behavior using Policy-based methods.
• Critic: Measures how good the action taken by the agent is using Value-based methods.

Reducing Variance using a Critic​

$Q_w(s,a) \approx Q^{\pi\theta}(s,a)$

• Monte Carlo policy gradient has high variance.
• Use a Critic to estimate the action-value function.
• Actor-Critic algorithms maintains two sets of parameters:
• Critic: Updates action-value function parameters $w$.
  • It is solving the problem of policy evaluation.
  • How good is the policy $\pi_\theta$ for current parameters $\theta$?
  • MC or TD methods to estimate the value function.
• Actor: Updates policy parameters $\theta$ in the direction advised by the Critic.

$$\Delta_{\theta} J(\theta) = \mathbb{E}_{\pi\theta}[ \nabla_\theta \log \pi_\theta(s,a) Q_w(s,a) ] \\ \Delta_{\theta} = \alpha \nabla_\theta \log \pi_\theta(s,a) Q_w(s,a)$$

• It follows an approximate policy gradient.

Action-Value Actor-Critic​

• Using Linear value function approximation: $Q_w(s,a) = \phi(s,a)^T w$
• Critic: Use Linear TD(0) to update $w$.
• Actor: Use policy gradient to update $\theta$.

$$\begin{array}{l} \textbf{Function Actor-Critic} \\ \qquad \text{Initialize } \theta, s \\ \qquad \text{Sample } a \sim \pi_\theta \\ \\ \qquad \textbf{for each step do} \\ \qquad\qquad \text{Sample reward } r = R_s^a \\ \qquad\qquad\text{Sample transition } s' \sim P_s^a \\ \qquad\qquad \text{Sample action } a' \sim \pi_\theta(s',a') \\ \\ \qquad\qquad \delta = r + \gamma Q_w(s',a') - Q_w(s,a) \\ \qquad\qquad \theta = \theta + \alpha \nabla_\theta \log \pi_\theta(s,a) Q_w(s,a) \\ \\ \qquad\qquad \mathbf{w} \leftarrow \mathbf{w} + \beta \delta \phi(s,a) \\ \qquad\qquad a \leftarrow a',\; s \leftarrow s' \end{array}$$

• $\delta$ is Critic.
• $\theta$ is Actor.
• Update $w$: Critic can provide a better advice.

Actor-Critic: Sutton and Barto​

$$\begin{array}{l} \textbf{Input: } \text{a differentiable policy parameterization } \pi(a \mid s,\theta) \\ \textbf{Input: } \text{a differentiable state-value function parameterization } \hat{v}(s,\mathbf{w}) \\ \textbf{Parameters: } \text{step sizes } \alpha^\theta > 0,\; \alpha^{\mathbf{w}} > 0 \\ \textbf{Initialize } \text{policy parameter } \theta \in \mathbb{R}^{d'} \text{ and state-value weights } \mathbf{w} \in \mathbb{R}^{d} \text{ (e.g., to 0)} \\ \textbf{Loop forever (for each episode):} \\ \qquad \text{Initialize } S \text{ (first state of episode)} \\ \qquad I \leftarrow 1 \\ \qquad \textbf{Loop while } S \textbf{ is not terminal (for each time step):} \\ \qquad\qquad A \sim \pi(\cdot \mid S,\theta) \\ \qquad\qquad \text{Take action } A,\; \text{observe } S',R \\ \qquad\qquad \delta \leftarrow R + \gamma \hat{v}(S',\mathbf{w}) - \hat{v}(S,\mathbf{w}) \qquad \left( \text{if } S' \text{ is terminal, then } \hat{v}(S',\mathbf{w}) \doteq 0 \right) \\ \qquad\qquad \mathbf{w} \leftarrow \mathbf{w} + \alpha^{\mathbf{w}} \delta \nabla \hat{v}(S,\mathbf{w}) \\ \qquad\qquad \theta \leftarrow \theta + \alpha^\theta I \delta \nabla \ln \pi(A \mid S,\theta) \\ \qquad\qquad I \leftarrow \gamma I \\ \qquad\qquad S \leftarrow S' \end{array}$$

TRPO, Trust Region Policy Optimization​

$A(s,a) = Q(s,a) - V(s)$

• Advantage: the difference between the Q and the V values.
  • How good is an action compared to the average action for a specific state.
• $Q(s,a)$ = the expected long-term return when taking action $a$ in state $s$
• $V(s)$ = the expected average long-term return when following the policy from state $s$
• Used in many Deep RL algorithms such as TRPO, PPO, GRP and etc.
• Stationary Target: Fixed target during training.

Update the old policy to a new policy such that they are with in a "Trusted" distance apart.

• Conservative policy update allows improvement instead of degradation of policy.
• Improve training stability by avoiding parameter updates that changes the policy too much at one step.
• By enforcing KL divergence constraint on size of the policy update at each iteration.

Kullback-Leibler Divergence​

KL divergence score

$KL(P || Q)$

• It quantifies how much one probability distribution differs from another probability distribution.
• $||$ indicates divergence or $P$'s divergence from $Q$.

$D_{KL}(P || Q) = \sum_{x \in X} P(x) \log \frac{P(x)}{Q(x)}$

• Given two probability distributions $P$ and $Q$ over a discrete random variable $X$, the KL divergence is the expected value under $P$ of the log ratio between $P$ and $Q$.
  • Multiplying by $P(x)$ gives more weight to events that occur frequently under $P$.
  • $P$ large, $Q$ small → large divergence
  • $P$ small, $Q$ large → effect is smaller
• e.g. $\pi_{\text{old}}(a_1|s) = 0.8$ and $\pi_{\text{old}}(a_2|s) = 0.2$, while $\pi_{\text{new}}(a_1|s) = 0.1$ and $\pi_{\text{new}}(a_2|s) = 0.9$
  • The policy changed drastically in one update step.
• TRPO prevents this by enforcing $D_{KL}(\pi_{\text{old}} \| \pi_{\text{new}}) \leq \delta$.

TRPO vs Gradient Descent​

Comparison	Gradient Descent	Trust Region
Optimization approach	Picks the steepest direction.	Defines a region in which to search for the next point.
Step	Moves forward by a step size.	Determines the maximum step size to explore.
Next point	Moves directly in the selected direction.	Locates the optimal point within the trust region.
Search process	Repeats the directional step.	Resumes the search from the selected point.
Main characteristic	Fast and simple for optimizing an objective function.	Controls how far the optimization explores at each step.
In Reinforcement Learning	May not work well in reinforcement learning.	Provides a restricted region for finding the next optimal point.

PPO, Proximal Policy Optimization​

• TRPO is relatively complicated, every time we need to find trust region and solve the optimization problem, leading to high computational cost.
• PPO simplifies it by using a Clipped Surrogate function
• Based on a ratio of two policies
  • Current Policy $\pi_{\theta}$
  • Baseline Policy (Old Policy) $\pi_{\theta_{\text{old}}}$

Policy Ratio​

$$r_t(\theta) = \frac{\pi_\theta(a_t|s_t)} {\pi_{\theta_{\text{old}}}(a_t|s_t)}$$

• $r_t(\theta)=1$: no policy change
• $r_t(\theta)>1$: the action becomes more likely
• $r_t(\theta)<1$: the action becomes less likely

The surrogate objective is:

$$J(\theta) = \mathbb{E}_t \left[ r_t(\theta)\hat A_t \right]$$

• $\hat A_t>0$: the action was better than expected → increase its probability.
• $\hat A_t<0$: the action was worse than expected → decrease its probability.
• Without a restriction, the policy may change too much in a single update.

Clipped Surrogate Objective​

$$J^{CLIP}(\theta) = \hat{\mathbb E}_t \left[ \min ( \underbrace{r_t(\theta)\hat A_t}_{\text{Normal Policy Gradient objective}}, \underbrace{\operatorname{clip} (r_t(\theta),1-\epsilon,1+\epsilon)}_{\text{Clipped Policy Gradient Objective}}\hat A_t ) \right]$$

• $r_t(\theta) = \frac{\pi_\theta(a_t|s_t)}{\pi_{\theta_{\text{old}}}(a_t|s_t)}$ is the ratio of the new policy to the old policy.
• $\hat A_t = Q(s_t,a_t) - V(s_t)$ is the advantage function.
• $\epsilon$ is a hyperparameter, usually $0.1$ or $0.2$.
• If $\epsilon=0.2$, the clipping range is $[0.8,1.2]$.
• For $\hat A_t>0$, PPO removes the benefit of increasing $r_t$ above $1+\epsilon$.
• For $\hat A_t<0$, PPO removes the benefit of decreasing $r_t$ below $1-\epsilon$.
• The policy ratio itself is not strictly forced to remain inside the clipping range.
• Instead, clipping removes the incentive for excessively large beneficial policy updates.

$$\begin{array}{l} \textbf{Algorithm: PPO with Clipped Objective} \\ \textbf{Input: } \theta_0,\ \epsilon \\ \textbf{for } k=0,1,2,\ldots \textbf{ do} \\ \qquad \text{Collect set of partial trajectories } \mathcal{D}_k \text{ on policy } \pi_k=\pi(\theta_k) \\ \qquad \text{Estimate advantages } \hat{A}_t^{\pi_k} \text{ using any advantage estimation algorithm} \\ \\ \qquad \text{Compute policy update} \\ \qquad \theta_{k+1} = \arg\max_{\theta} \mathcal{L}_{\theta_k}^{CLIP}(\theta) \\ \\ \qquad \text{by taking } K \text{ steps of minibatch SGD (via Adam), where} \\ \qquad \mathcal{L}_{\theta_k}^{CLIP}(\theta) = \mathbb{E}_{\tau\sim\pi_k} \left[ \sum_{t=0}^{T} \min \left( r_t(\theta)\hat{A}_t^{\pi_k}, \operatorname{clip} \left( r_t(\theta),1-\epsilon,1+\epsilon \right) \hat{A}_t^{\pi_k} \right) \right] \\ \end{array}$$

• $\theta_0$: Initial policy parameters.
• $\epsilon$: Clipping threshold.
• $\hat{A}_t^{\pi_k}$: $A_\pi(s,a)=Q_\pi(s,a)-V_\pi(s)$, where $a_t\sim\pi(a_t\mid s_t),\quad s_{t+1}\sim P(s_{t+1}\mid s_t,a_t)$, for $t\ge0$.

Function Approximation​

$\hat{v}(s, \mathbf{w}) \approx v_\pi(s)$

$\hat{q}(s, a, \mathbf{w}) \approx q_\pi(s, a)$

• Incremental methods for prediction
• Model-free VFA: MC and TD targets

GPI, Generalized Policy Iteration​

• Iterate between policy evaluation and policy improvement
• Policy Evaluation: Approximate policy evaluation. $\hat{q}(\cdot, \cdot, \mathbf{w}) \approx q_\pi$
• Policy Improvement: $\epsilon$-greedy policy improvement.

Types of Action-Value FA​

$$s \to \text{FA}(\mathbf{w}) \to \hat{q}(s, \mathbf{w})$$

• State Value Function Approximation

$$(s, a) \to \text{FA}(\mathbf{w}) \to \hat{q}(s, a, \mathbf{w})$$

• Action Value Function Approximation
  • $\hat{q}(s, \text{Left}, \mathbf{w}) = 3.2$
  • $\hat{q}(s, \text{Right}, \mathbf{w}) = 8.7$

$$s \to \text{FA}(\mathbf{w}) \to \hat{q}(s,a_1, \mathbf{w}) \cdots \hat{q}(s,a_n, \mathbf{w})$$

• The network output is a vector of Q-values for each action.
• More convenient to use discrete action spaces.

Action	Q-value
Left	3.2
Right	8.7
Jump	5.3

Action VFA​

$\hat{q}(s, a, \mathbf{w}) \approx q_\pi(s, a)$

• Approximate the Action-value function.
• Doing action $a$ at state $s$, Approximate the Q-value of that action.

$\mathcal{J} = \mathbb{E}_{\pi} \left[ (q_\pi(s, a) - \hat{q}(s, a, \mathbf{w}))^2 \right]$

• Minimize mean-squared error (MSE) between the approximate Q-value $\hat{q}(s, a, \mathbf{w})$ and the true Q-value $q_\pi(s, a)$.

$\Delta \mathbf{w} = \alpha (q_{\pi}(s,a) - \hat{q}(s,a,\mathbf{w})) \nabla_{\mathbf{w}} \hat{q}(s,a,\mathbf{w})$

• Use SGD to find the local minimum.
• $q_{\pi} - \hat{q}$ tells us how much the prediction is off from the target.
• $\nabla_{\mathbf{w}} \hat{q}(s,a,\mathbf{w})$ tells us how each weight affects the predicted $Q$-value.

Linear Action VFA​

$$x(s, a) = \begin{bmatrix} x_1(s, a) \\ x_2(s, a) \\ \vdots \\ x_n(s, a) \end{bmatrix}$$

• Feature vector is used to represent the state and action pair.

$\hat{q}(s, a, w) \approx x(s, a)^T w = \sum_j x_j (s, a) w_j$

• Predicted Q-value is a linear combination of the feature values. (sum of each feature value $x_j$ multiplied by the weight $w_j$)

$$\begin{aligned} \hat{q}(s, a, w) = x(s, a)^T w \\ \hat{q} = x_1w_1 + x_2w_2 + \cdots + x_n w_n \end{aligned}$$

• $x_1, x_2, \cdots$: features of the state and action pair.
• $w_1, w_2, \cdots$: weights that need to be learned.
• derivative $\hat{q}$ with respect to $w$.
  • $\frac{\partial \hat{q}}{\partial w_1} = x_1$
  • $\frac{\partial \hat{q}}{\partial w_2} = x_2$

$$\nabla_w\hat{q} = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix} = x(s, a)$$

• e.g. $\hat{q} = 2w_1 + 5w_2$, then $\nabla_w\hat{q} = \begin{bmatrix} 2 \\ 5 \end{bmatrix}$

$$\begin{aligned} \Delta w \\ &= \alpha (q_{\pi} - \hat{q}) \nabla_w\hat{q} \\ &= \alpha (q_{\pi} - \hat{q}) x(s, a) \\ &= \alpha (q_{\pi}(s, a) - \hat{q}(s, a, w)) x(s, a) \end{aligned}$$

Incremental Prediction Algorithm​

• Assumption so far: $q_{\pi}(s,a)$ is given.
• But an actual RL agent does not know the true $q_{\pi}(s,a)$.
• Therefore, we need to estimate a target.
• Monte Carlo (MC): the target is the return $G_t$.
  • $G_t = R_{t+1} + \gamma R_{t+2} + \cdots$
  • Update: $\Delta w = \alpha \bigl(G_t - \hat q(s_t,a_t,w)\bigr)\nabla_w\hat q(s_t,a_t,w)$
  • It compares the predicted Q-value with the actual return observed after the episode.
  • MC does not use another prediction inside the target.
• Temporal Difference (TD): the target is $R_{t+1} + \gamma \hat q(s_{t+1},a_{t+1},w)$.
  • Update: $\Delta w = \alpha \bigl(R_{t+1} + \gamma\hat q(s_{t+1},a_{t+1},w) - \hat q(s_t,a_t,w)\bigr)\nabla_w\hat q(s_t,a_t,w)$
  • It compares the current Q prediction with the current reward plus the discounted next Q prediction.
  • Bootstrapping: update the current prediction using another prediction.
  • Because the next prediction can also be wrong, we ask: can repeated updates converge to a stable value?
• On-policy: behavior policy = target policy.
• Off-policy: behavior policy $\ne$ target policy.
  • The policy that generates the experience is different from the policy that we want to evaluate or improve.

Policy	Algorithm	Lookup Table	Linear	Non-linear
On-policy	MC	✓	✓	✓
On-policy	TD(0)	✓	✓	✗
Off-policy	MC	✓	✓	✓
Off-policy	TD(0)	✓	✗	✗

• Deadly Triad: Function Approximation + Bootstrapping + Off-policy.

Algorithm	Lookup Table	Linear	Non-linear
MC Control	✓	(✓)	✕
SARSA	✓	(✓)	✕
Q-Learning	✓	✕	✕

• SARSA learns the policy that it actually follows.
  • Target: $R_{t+1} + \gamma Q(s_{t+1},a_{t+1})$, On-policy TD
• Q-Learning learns the optimal policy.
  • Target: $\max_{a'} Q(s_{t+1},a')$, Off-policy TD
• (✓): Moved around the near-optimal value function.
  • Linear FA may not represent the exact $Q^*$ because all state-action values share the same weight vector and must fit the same linear function.
• x: Divergence

Batch Methods​

• Incremental learning: an experience -> update the weights.
• Batch methods: collect experiences -> store in $\mathcal{D}$ -> reuse $\mathcal{D}$ for training.
• It seeks to find the best fitting value functions.

$\mathcal{D} = \{(s_1, v^{\pi}_1), (s_2, v^{\pi}_2), \cdots, (s_N, v^{\pi}_N)\}$

• Which $w$ makes $\hat{v}(s, w)$ fit all stored data best?
  • Using the agents' experience or training data.
  • Training data: a fixed batch of previously collected data.

Least Squares Prediction​

• Given a value function approximation: $\hat{v}(s,w) \approx v^\pi(s)$
• Given experience data: $\mathcal{D} = \{(s_1,v_1^\pi),(s_2,v_2^\pi),\ldots,(s_N,v_N^\pi)\}$ consisting of state-value pairs.

$$LS(w)=\sum_{t=1}^{N}\left(v_t^\pi-\hat{v}(s_t,w)\right)^2$$

• $LS(w)$ is the sum of all squared prediction errors.
• The Least Squares method finds the parameter vector $w$ that minimizes the squared error between $\hat v(s,w)$ and $v^\pi(s)$.

$$w^\pi=\arg\min_w LS(w)$$

• If we use the mean squared error instead:

$$\mathbb{E}_{\mathcal D} \left[ \left(v_t^\pi-\hat v(s_t,w)\right)^2 \right] = \frac{1}{N} \sum_{t=1}^{N} \left(v_t^\pi-\hat v(s_t,w)\right)^2$$

• The factor $1/N$ does not change the minimizing $w$.

SGD Procedure​

1. Sample a $\{\text{state},\text{value}\}$ pair from $\mathcal D$.
2. Apply the SGD update:

$$\Delta w = \alpha \left(v^\pi-\hat v(s,w)\right) \nabla_w\hat v(s,w)$$

• Sample from $\mathcal D$ -> calculate the error -> update $w$ -> repeat.

3. Under appropriate conditions, SGD converges toward the Least Squares solution.

• Then, what model should represent $\hat v(s,w)$?
  • Linear function approximator
  • ANN
  • CNN

DNN, Deep neural network​

• Universal function approximator
  • Linear FA limited to linear combinations of features $\hat{v}(s, w) = x(s)^T w$
  • DNN can represent non-linear mappings of features. $s \rightarrow \text{DNN}(\mathbf{w}) \rightarrow \hat{v}(s, \mathbf{w})$
• Combination of both Linear and Non-Linear transformations
  • $z = Wx + b$
  • $h = \text{ReLU}(z)$
• It may require exponentially less nodes or parameters to represent the sample Linear function.
• SGD can be used to learn parameters
  • prediction -> loss -> gradient -> SGD -> $w$ update.
• It can generalize from observed states to unseen states.
• It can handle continuous state spaces, which are common in real world problems.
  • $s = (x, y, \text{velocity}, \text{angle})$
  • $s = (2.371, 5.826, 0.43, \cdots) \rightarrow \text{DNN} \rightarrow \hat{v}(s, \mathbf{w})$
• E2E learning (learn feature representation and policy together) can be more effective.
• Function approximation using images, environments with visual observations.
• DNNs can directly process pixel data and learn from raw images.
• DNNs can be used in environments with continuous action spaces for approximating policies (Robotics)
• It can achieve SOTA performance in several complex tasks.

CNN, Convolutional neural network​

• CONV is the first layer to extract features from an input image.
  • Core building block of a CNN
  • A number of filters such as Edge Detectors are applied to the input image.
• Padding: add extra pixels around the image to handle edge cases.
  • Valid Padding: no padding, output size is smaller than input size.
    • $p = 0$.
    • Output size: $(n - f + 1) \times (n - f + 1)$
    • $f$: filter size.
  • Same Padding: add padding so that output size is the same as input size.
    • $p = \frac{f-1}{2}$
• Stride: the number of pixels the filter moves across the input image.
  • $S = 1$: Move the filter by one pixel horizontally and vertically.
  • $S = 2$: Move the filter by two pixels horizontally and vertically.
• POOL: down sampling operation which reduces the dimensionality of a matrix.
  • It reduces the number of parameters for large image but retain the valuable information.
  • Max pooling: Max(7, 8, 9, 10) = 10
  • Average pooling: Avg(7, 8, 9, 10) = 8.5
  • Sum pooling: Sum(7, 8, 9, 10) = 34
• FC: The output matrix after convolution layer is flattened and feed into a fully connected layer similar to ANN.
  • It's a traditional Multi-layer Perceptron/Neural Network.
  • For multi-class classification, Softmax activation function is usually used.
  • Output of the CONV and POOL layers represent a high-level features of the Input image.
  • FC layer uses this feature to classify the input image into the desired class.

Deep Reinforcement Learning​

• Use DNNs to represent
  • Value and Q-Value function (Action-value function)
  • Policy (Policy Gradient methods)
  • Model
• Use SGD to optimize loss function.
• RL makes the target, SGD trains DNN to fit the target.
• In TD: $\Delta w = \text{learning rate} \times \text{TD error} \times \text{gradient}$
  • TD error: $\underbrace{R_{t+1} + \gamma \hat{q}(s_{t+1},a_{t+1},w)}_{\text{Target}} - \underbrace{\hat{q}(s_t,a_t,w)}_{\text{Current Prediction}}$
• In Q-Learning: $\max_{a'} Q(s_{t+1},a',w)$ is the target.

Q-Learning with VFA​

• Original Q-Learning converges to the optimal $Q^*(s, a)$ using look-up table.
• VFA Q-Learning minimizes MSD Loss by SGD using target Q estimates instead of true Q.
  • so it can diverge due to the correlation between samples or Non-stationary targets.

Experience Replay​

• DQN stores past transitions $(s,a,r,s')$ in a replay buffer and randomly samples them for training, which reduces correlation between consecutive samples and improves training stability.
  • Sample $(s, a, r, s')$ from $\mathcal{D}$
  • Compute the target value of the samples $s: (r + \gamma \max_{a'} \hat{q}(s',a',w))$
  • Use SGD to update the network weight: $\Delta w = \alpha (r + \gamma \max_{a'} \hat{q}(s',a',w) - \hat{q}(s,a,w))\nabla_w \hat{q}(s,a,w)$

Fixed Q-Targets​

• Improve stability by fixing the target weights used in the target calculation for multiple updates.
• Target network uses different set of weights that the weights being updated.
• $w^-$: set of weights used in the target.
• $w$: set of weights being updated.

$r + \gamma \max_{a'} Q(s',a',\color{red}w^-\color{black})$

• Sample $(s, a, r, s')$ from $\mathcal{D}$
• Compute the target value of the samples $s: (r + \gamma \max_{a'} Q(s',a',w^-))$
• Use SGD to update the network weight: $\Delta w = \alpha (r + \gamma \max_{a'} Q(s',a',w^-) - Q(s,a,w))\nabla_w Q(s,a,w)$

DQN​

DQN in Atari​

• E2E learning of $Q(s,a) values from pixels$s$
• Input state $s$ is a stack or raw pixels from last 4 frames.
• Output is $Q(s,a)$ for 18 joystick/button positions
• Reward is chance in score for that step.
• Network Architecture and hyper-parameters are fixed across all games.
• 4x84x84 stack of 4 previous frames -> 16 8x8 filters CONV -> 32 4x4 filters CONV -> 256 hidden units FC -> Fully connected linear output layer.