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)$.
• $\nabla_\theta \log \pi_\theta(s,a)$ is called the Score Function.

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

Linear Value Function Approximation​

• Represent Value function (state or action) by a linear combination of features
  • $\hat{v}(s, w) = x(s)^Tw = \sum_{j=0}^n x_j(s) w_j$
• Loss function: $J(w) = \mathbb{E}_\pi[\big(v_\pi(s) - \hat{v}(s, w)\big)^2]$

$\Delta w = \alpha \underbrace{\big(v_\pi(s) - \hat{v}(s, w)\big)}_{Error} \underbrace{x(s)}_{Feature}$

• Weight update: step size X Error X Feature value
• SGD converges to global mininum

Incremental methods for prediction​

• Real-world RL is not supervised, instead, it is guided by rewards.
• No $v_\pi(s)$ is given.
• Instead, substitute a target for $v_\pi(s)$

$\Delta w = \alpha(G_t - \hat{v}(s_t, w)) \nabla_w \hat{v}(s_t, w)$

• Monte Carlo updates: target is the return $G_t$

$\Delta w = \alpha(\underbrace{R_{t+1} + \gamma \hat{v}(s_{t+1}, w)}_{\text{TD Target}} - \hat{v}(s_t, w)) \nabla_w \hat{v}(s_t, w)$

• TD updates: use TD Target

VFA for Monte Carlo​

• MC return $G_t$ is an unbiased, noisy sample of true value $v_\pi(s_t)$
  • if $G_t = 3, 7, 4, 6, 5, \cdots$
  • but in average, $\frac{1}{N} \sum_{i=1}^N G_t^{(i)} \approx v_\pi(s)$
• $\langle S_1, G_1 \rangle, \langle S_2, G_2 \rangle, \cdots, \langle S_N, G_N \rangle$ is an estimate of $v_\pi(s)$
  • $x \rightarrow y$ (supervised learning)
  • $s_t \rightarrow G_t$ (Reinforcement learning)
• so it learns to $\hat{v}(s, w) \approx G_t$

• In Linear VFA, $\hat{v}(s,w) = w^Tx(s)$
  • $x(s)$ is the feature vector of state $s$
  • $w$ is the weight vector
  • so $\nabla_w \hat{v}(s, w) = \nabla_w (w^Tx(s)) = x(s)$
• Update = Learning rate X Error X state features

• $G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots + \gamma^{L_k-t} R_{L_k}$

VFA for TD Learning​

• Use bootstrapping and sampling to approximate the target $v_\pi$
  • Sampling: Use a sampled transition $S_t, A_t, R_{t+1}, S_{t+1}$ instead of computing the full expectation over possible transitions.
  • Bootstrapping: Construct the TD target using the current estimate $\hat{v}(S_{t+1}, w)$, instead of waiting for the complete episodic return.

$R_{t+1} + \gamma \hat{v}(S_{t+1}, w)$

• TD Target is a biased sample of true value $v_\pi(S_t)$
• Can use supervised learning on a training set of $\langle S, R \rangle$ paris
  • $\langle S_1, R_2 + \gamma \hat{v}(S_2, w) \rangle, \langle S_2, R_3 + \gamma \hat{v}(S_3, w) \rangle, \cdots, \langle S_{T-1}, R_T \rangle$

$\Delta w = \alpha(R + \gamma \hat{v}(s', w) - \hat{v}(s, w)) \nabla_w \hat{v}(s, w)$

• Linear VFA + TD(0) for prediction and policy evaluation
• TD Error: $\delta_t = R_{t+1} + \gamma \hat{v}(S_{t+1}, w) - \hat{v}(S_t, w)$
• $\Delta w = \alpha \delta_t \nabla_w \hat{v}(S_t, w)$
  • $\nabla_w \hat{v}(s, w) = x(s)$
  • $\Delta w = \alpha \delta_t x(s)$
  • $w \leftarrow w - \alpha \delta_t x(s)$

Overall​

• Linear VFA: $\hat{v}(s, w) = w^Tx(s)$
• MC Target = $G_t$
• TD Target = $R_{t+1} + \gamma \hat{v}(s', w)$
• MC: $w \leftarrow w + \alpha(G_t - \hat{v}(s, w)) x(s)$
• TD: $w \leftarrow w + \alpha(R_{t+1} + \gamma \hat{v}(s', w) - \hat{v}(s, w))x(s)$

Feature Detection​

1. Detect invariant features of the image.
2. Describe the local area around each feature.
3. Match patterns of the feature descriptions.

Moravec conner detector​

$E(u, v) = \sum_{x, y} [I(x, y) - I(x + u, y + v)]^2$

• One of the earliest corner detectors (1980)
• Moravec detects a corner by shifting a small window in different directions and checking whether the image changes significantly in every direction.
  • Shifting a window in any direction should give a large change in intensity, measured in terms of Sum of Squared Differences (SSD).
• $(u, v)$ is how much the window is shifted.
• Larger $E$ indicates the image changes more after the shift.

• Flat: $E \approx 0$, No change in any direction
• Edge: $E \approx 1$, Change in some direction
• Corner: $E \approx 40$, Large change in every direction

Harris corner detector​

$E(x, y) = \sum_{u}\sum_{v} \underbrace{W(u, v)}_{\text{Window function}} [\underbrace{I(u + x, v + y)}_{\text{Shifted Intensity}} - \underbrace{I(u, v)}_{\text{Intensity}}]^2$

• Improvement over Moravec change of intensify for a shifted windoe centered at $(u, v)$

• $(x, y) = (1, 0) \rightarrow$ move 1px to the right.
• $(x, y) = (0, 1) \rightarrow$ move down 1px.
• $(x, y) = (2, 1) \rightarrow$ move 2px to the right and 1px down.
• $I(u, v)$: Pixel intensity of the original point.
• $I(u + x, v + y)$: Pixel intensity of the shifted point.
• SSD: if $I(u,v) = 65$, and $I(u + x, v+ y) = 124$, then the SSD is $(124 - 65)^2 = 3481$.
• $w(u, v)$: window function, usually apply gaussian weighting to the pixels around the center.
  • if we calculate all the $(x, y)$ step by step, it will be computationally expensive.
  • so we use Taylor Expansion to approximate the intensity change.

Taylor Expansion​

$I(u + x, v + y) \approx I(u, v) + I_x(u, v)x + I_y(u, v)y$

• Let $I_x$ and $I_y$ be the partial derivatives of $I$
• Approximates the intensity of the slightly shifted point, using the current intensity and gradient information.
• $I_x = \frac{\partial I}{\partial x}$: How much the intensity changes when moving to the right or left a little bit.
• $I_y = \frac{\partial I}{\partial y}$: How much the intensity changes when moving up or down a little bit.

$E(x, y) \approx \sum_{u}\sum_{v} w(u, v) [I_x(u, v)x + I_y(u, v)y]^2$

• because $I(u + x, v + y) \approx I(u, v) + I_x(u, v)x + I_y(u, v)y$.
• we can calculate intensity change by x/y gradient and the window shift.
• $(ax + by)^2 = a^2x^2 + 2abxy + b^2y^2 = [x, y] \begin{bmatrix} a^2 & ab \\ ab & b^2 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix}$

$E(x,y) = [x, y] \underbrace{\begin{bmatrix} \sum_{u}\sum_{v} w(u, v) I_x^2 & \sum_{u}\sum_{v} w(u, v) I_xI_y \\ \sum_{u}\sum_{v} w(u, v) I_xI_y & \sum_{u}\sum_{v} w(u, v) I_y^2 \end{bmatrix}}_{A} \begin{bmatrix} x \\ y \end{bmatrix}$

• Eigenvector = direction of the change
• Eigenvalue = magnitude of the change
• if both $\lambda_1 \text{ and } \lambda_2 \approx 0$, the point is flat.
• if either $\lambda_1 \text{ or } \lambda_2 \gg 0$ the point is an edge.
• if both $\lambda_1 \text{ and } \lambda_2 \ll 0$ the point is a corner.

$R = \det(A) - k(\text{trace}(A))^2$

• $\det(A) = \lambda_1 \lambda_2$
  • it can check if the point is a corner by checking if $\lambda_1 \text{ and } \lambda_2$ are both large.
• $\text{trace}(A) = \lambda_1 + \lambda_2$
  • it can penalizes edge-like responses where one eigenvalue is large but the other is small.
• $R = \lambda_1 \lambda_2 - k(\lambda_1 + \lambda_2)^2$
  • $k$ is an empirical constant, typically set $0.04 \leq k \leq 0.06$.
  • A threshold is applied an corners detected, non-maxima are suppressed.
  • $R$ can be derived from eigenvalues of the matrix $A$.
  • $R \approx 0$ the point is flat.
  • $R < 0$ the point is an edge.
  • $R \gg 0$ the point is a corner.

Harris corner detection pipeline​

• Compute the Harris response $R$ for every pixel.
• Large positive $R$ indicates a strong corner response.
• Apply a threshold to remove weak responses.
• Apply non-maximum suppression to keep only local maxima.
• Overlay the remaining points on the original image as detected corners.

Detector vs descriptor​

• Detector: detect the location of the features in an image or video (WHERE).
• Descriptor: descriptors summarize the appearance of the neighborhood (WHAT IT LOOKS LIKE).
• A good feature detector should be:
  • make similar descriptors for similar features of the same object.
  • Invariance: the descriptor should be invariant to translation, rotation, scale, and illumination.

SIFT​

Scale-Invariant Feature Transform

• It was proposed by Lowe in 1999, includes both a detector and a descriptor.
• A method to detect and match local features despite changes in scale and rotation.
• Core idea: build multiple blurred versions of the image, compute their differences, and find points that stand out across scales.

1. Build a scale-space pyramid of Differences of Gaussians (DoG) and detect minima/maxima.
2. Localize keypoints.
3. Assign them an orientation.
4. Compute the SIFT descriptor.

• $L(x, y, \sigma) = G(x, y, \sigma) * I(x, y)$: Blurred image at scale $\sigma$.
• $D(x, y, \sigma) = L(x, y, k\sigma) - L(x, y, \sigma)$: Difference of Gaussians at scale $\sigma$.
• Octave: a group of scale-space images at the same resolution.
• After each octave, the image is typically downsampled by a factor of 2.

Key point localization​

$\text{Image} \rightarrow \text{Gaussian scale space} \rightarrow \text{DoG} \rightarrow \text{DoG extrema} \rightarrow \text{Filter low-contrast and edge responses} \rightarrow \text{Keypoints}$