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​

• 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$.

• 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.

• 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$.

• 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.

• 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.

• 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}$

• 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$

REINFORCE: Sutton and Barto​

• 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.

• 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$.

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

Actor-Critic: Sutton and Barto​

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​

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)=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:

• $\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​

• $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.

• $\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​

• State Value Function Approximation

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

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

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​

• 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$)

• $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$

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

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.

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

• 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)$ 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)$.

• If we use the mean squared error instead:

• 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:

• 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​

Environment
    │
    │ experience
    ▼
(s, a, r, s')
    │
    ▼
Replay Buffer D
┌──────────────────────┐
│ old experience       │
│ old experience       │
│ old experience       │
│ old experience       │
└──────────────────────┘
    │
    │ random sample
    ▼
Mini-batch
    │
    ├──────────────► Current Q Network
    │                   │
    │                   ▼
    │                 Q(s,a)
    │
    └──────────────► Target calculation
                        │
                        ▼
              r + γ max Q(s',a')
                        │
                        ▼
             Target − Prediction
                        │
                        ▼
                       SGD
                        │
                        ▼
                  Update weights

• 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​

        [Same structure of network 2]

Current state s                    Next state s'
     │                                  │
     ▼                                  ▼
Online Q Network                  Target Network
weights = w                       weights = w⁻
     │                                  │
     ▼                                  ▼
Q(s,a;w)                      max Q(s',a';w⁻)
     │                                  │
     └────────── compare ────────────────┘
                      │
                      ▼
                    Loss
                      │
                      ▼
                update only w

• 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.

RL Taxonomy​

Drawbacks of previous methods​

• Large state space:
  • Go: $10^{170}$
  • Backgammon: $10^{20}$
  • Atari games: $10^9 \text{ to } 10^{11}$
• Scale-up model-free based techniques for prediction and control is challenging.
• Value function used look-up table representation
  • All states has an entry in $V(s)$
  • All state-action pair $(s,a)$ has an entry in $Q(s,a)$
• Too many state, and stat-action pair to store in memory
• Slow learning process for each states, due to large space.
• Each states needs to be explored sufficiently.
• For large MDPs
  • Function approximation: Almost near optimal value.
  • Estimate value function with function approximation.
    • $\hat{v}(s,w) \approx v_\pi(s)$
    • $\hat{q}(s,a,w) \approx q_\pi(s,a)$
  • Generalize from seen states to unseen states.
  • Using MC or TD learning techniques: Update parameter $w$.

Function Approximation​

• A technique for estimating unknown underlying function using historical or available observations.
• Assumption: an underlying mapping function exists
  • $f(x) \approx \hat{f}(x)$
• Function: $x \xrightarrow{f} y$

Types of Value Function Approximation​

State-value: state $s$ → scalar $\hat{v}(s,w)$

Action-value (s, a input): state $s$ and action $a$ → scalar $\hat{q}(s,a,w)$

Action-value (s input, all actions out): state $s$ → $\hat{q}(s,a_1,w),\ldots,\hat{q}(s,a_m,w)$

• $w$ is the parameter vector of the function approximator.
  • e.g. Neural Network weights

Types of Function Approximator​

• Tabular
  • V-Table: $s \rightarrow v(s)$
  • Q-Table: $(s,a) \rightarrow q(s,a)$
• Decision Trees, Nearest Neighbors
  • $s = [\text{speed} = 49, \text{distance} = 10]$
  • $s \rightarrow \text{Decision Tree / KNN} \rightarrow \hat{v}(s)$
• Linear Function approximation
  • Linear Combination of Features
  • Values are linear function for features $\hat{v}(s,w) = w^Tx(s)$
  • $x(s) = \begin{bmatrix} \text{speed} \\ \text{distance} \\ \text{fuel} \end{bmatrix}$
  • $\hat{v}(s,w) = w^Tx(s)$
  • $\hat{v}(s,w) = w_1x_1(s) + \cdots + w_n x_n(s)$
• Differentiable function approximation
  • $\hat{v}(s,w)$ is a differentiable function of $w$, can be non-linear in $s$
  • e.g. Neural Network, or CNN
    • $\frac{\partial \hat{v}(s,w)}{\partial w}$
    • $w \leftarrow w - \alpha \nabla_wL$
    • $\text{Pixels} \xrightarrow{CNN} \hat{v}(s)$

Which FA to use?​

In principle, any FA that fits the RL framework can be used.

• Need training methods that are suitable for non-stationary data.

ANN​

Logistic Regression​

$\mathcal{L}(a, y) = -y \log(a) - (1-y) \log(1-a)$

• Loss function for Logistic Regression

Gradient Descent​

Goal: Find $w$ tht minimize $J(w)$ or find a local minimum of $J(w)$.

• An iterative approach for error correction.
• For one sample, $\mathcal{L}(a, y) = -y \log(a) - (1-y) \log(1-a)$
• For $m$ samples,

$J(w, b) = \frac{1}{m} \sum_{i=1}^m \mathcal{L}(a^{(i)}, y^{(i)})$

• Find $w$ and $b$ that will minimize $J(w, b)$
  • $\min_{w, b} J(w, b)$
  • $J(w)$ is loss function.

$w \leftarrow w - \alpha \frac{\partial J(w, b)}{\partial w}, \quad b \leftarrow b - \alpha \frac{\partial J(w, b)}{\partial b}$

$\Delta w J(w) = \big(\frac{\partial J(w)}{\partial w_1}, \ldots, \frac{\partial J(w)}{\partial w_n}\big)$

• Adjust the $w$ in the direction of the -ve gradient.
  • $w = w - \alpha \Delta w, \quad b = b - \alpha \Delta b$
  • where $\alpha$ is the learning rate.
  • and, $\Delta w = \frac{\partial J(w, b)}{\partial w}, \quad \Delta b = \frac{\partial J(w, b)}{\partial b}$

ANN as a Function Approximator​

• Need a method to estimate: $\Delta w$
• Method to incrementally adjust and update: $w$
• Representation of some aspects of RL environments as feature vector $x(s)$
• Aspects can be approximated: $V(s) \text{ or } Q(s, a)$
  • Estimate value functions with function approximation.
  • $\hat{V}(s, \color{red}{w}\color{black}) \approx V(s)$
  • $\hat{Q}(s, a, \color{red}{w}\color{black}) \approx Q(s, a)$
• A mechanism to plugin MC and TD for function approximation.

Value Function Approximation for policy evaluation​

VFA: Value Function Approximation

• $v_\pi(s)$ is given, so making it supervised.
• $\hat{v}(s, w)$ is estimated value if it follows the policy $\pi$ by using ANN.
• $x \rightarrow \hat{y} \quad \text{vs} \quad y$ (supervised learning)
• $s \rightarrow \hat{v}(s, w) \quad \text{vs} \quad v_\pi(s)$ (Reinforcement learning)

$J(w) = \mathbb{E}_\pi[\big(v_\pi(s) - \hat{v}(s, w)\big)^2]$

• Find $w$ that minimizes $J(w)$
  • $J(w)$: Loss function.
  • $\hat{v}(s, w)$: Guess from the value function approximation.
  • $v_\pi(s) - \hat{v}(s, w)$: Error between the true value and the estimated value.
  • $\mathbb{E}_\pi[\cdot]$: Expected average over all states $s$ according to the policy $\pi$.

• $\Delta w =$ Step size X Error X Gradient

VFA with SGD​

$\Delta w = \alpha (v_\pi(s) - \hat{v}(s, w)) \nabla_w \hat{v}(s, w)$

• Stochastic Gradient Descent sample the gradient
• Sample a state randomly, find what $v_\pi(s)$ is, and find the estimate
  • $\Delta w = \alpha [\text{Error at } s \times \text{Gradient at } s]$
  • Sample $s_t$ from $\pi$, and update $w$
• Expected value update using SGD update is same as full gradient update
  • Random sampling will be eventually the same as full gradient update