"rl" 태그로 연결된 8개 게시물개의 게시물이 있습니다.

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

Temporal-Difference Learning​

Updates a guess towards a guess.

• Model-free: No MDP Dynamics or Rewards
• Learns directly from episodes of experience.
• Bootstrapping: Estimate value function using estimated value from incomplete episodes.
  • Update estimate using another estimate.
• Updates the estimate of $V$ immediately after each step.
• Combines Monte Carlo and Dynamic Programming (Bootstrapping idea).

MC​

$V(S_t) = V(S_t) + \alpha [\underbrace{G_t}_{\text{Goal}} - \underbrace{V(S_t)}_{\text{Previous estimate}} ]$

• Update $V(S_t)$ towards the actual return.
• $\alpha = \frac{1}{n}$: Every-visit MC.
  • gives equal weight to all past samples in the arithmetic mean.
• Fixed $\alpha > \frac{1}{n}$: gives more weight to recent experience and reduces the influence of older episodes faster.
  • $\alpha = 0.1, \quad V(S) = 10$
  • $V(S) \leftarrow 10 + 0.1 (20 - 10) = 11$
  • $V(S) \leftarrow 11 + 0.1 (30 - 11) = 12.9$
  • Move 10% of the way towards the new value.

One-Step Bootstrapping​

$\text{TD}(0) \rightarrow \text{TD}(\lambda) \rightarrow \text{TD}(1) \approx \text{MC}$

• $\lambda$ controls how much longer-term return information is used in the TD update.
  • It controls how far into the future TD learns from.
• $\lambda = 0$: uses one-step bootstrapping, corresponding to TD(0).
• As $\lambda$ increases, rewards further into the future have more influence on the update.
• $\lambda = 1$: approaches the Monte Carlo return in episodic tasks.

$V(S_t) = V(S_t) + \alpha [\underbrace{\underbrace{R_{t+1} + \gamma V(S_{t+1})}_{\text{TD target}} - V(S_t)}_{\text{TD Error}} ]$

• Only one immediate reward is used $R_{t+1}$.
• Everything after that is replaced by the current guess $V(S_{t+1})$ instead of actual future rewards.
• It uses actual reward for the first step and the estimated value/guess for the rest.

MC
Sₜ ──Rₜ₊₁──> Sₜ₊₁ ──Rₜ₊₂──> ... ──> Terminal
│                                        │
└────────── episode 끝까지 기다림 ────────┘
                   ↓
               actual Gₜ
                   ↓
              V(Sₜ) update


TD(0)
Sₜ ──Rₜ₊₁──> Sₜ₊₁ ── ? ──> ...
│              │
│              └─ current V(Sₜ₊₁)
│
└── Rₜ₊₁ + γV(Sₜ₊₁)로 즉시 V(Sₜ) update

TD(0) Algorithm​

• No need to wait until the end of the episode to update the value function.

MC vs. TD​

• In practice, TD is faster than MC because it can learn from incomplete episodes.

• MC: Full sampled path to the end.
• TD: Just one real step.
• DP: Every branch, weighted by probability, no sampling.

SARSA​

$S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1}$

• Follows generalized Policy Iteration.
  • Policy Evaluation: TD Policy Evaluation $Q \approx q_\pi$
  • Policy Improvement: $\epsilon$-greedy policy improvement, allowing exploration.
  • Update happens after every time step.
• Use TD methods for evaluation. $Q(S, A)$
• TD Evaluation + $\epsilon$-greedy Policy Improvement = SARSA

$Q(S_t, A_t) = Q(S_t, A_t) + \alpha [\underbrace{R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})}_{\text{TD target}} - Q(S_t, A_t)]$

• $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$: transition from one state-action pair to the next.
• The process repeatedly alternates between improving $Q$ and improving the policy.
• The estimates gradually move toward the optimal action-value function $q_*$ and the optimal policy $\pi_*$.
• Unlike classical policy iteration, SARSA does not need to complete policy evaluation before improving the policy.

SARSA Example​

• $Q(S_t,A_t)=10$
• $R_{t+1}=2$
• $\gamma=0.9$
• $\alpha=0.5$
• $Q(S_{t+1},A_{t+1})=8$
• TD Target $=2+0.9(8)=9.2$
• TD Error $=9.2-10=-0.8$
• Updated $Q(S_t,A_t)=10+0.5(-0.8)=9.6$

SARSA Algorithm​

• As SARSA learns, each episode is completed faster.
• As the Q-values improve, the agent learns better actions for each state and reaches the goal using fewer steps.

Q-Learning​

• On-policy: SARSA, behavior policy is the same as the target policy.
• Off-policy: Q-Learning, behavior policy is different from the target policy. $Q(S, A)$
• Update $Q(S_t, A_t)$ toward the value of the alternative, best action.

$Q(S_t, A_t) = Q(S_t, A_t) + \alpha [\underbrace{R_{t+1} + \gamma \max_{a} Q(S_{t+1}, a)}_{\text{TD target}} - Q(S_t, A_t)]$

• The Actual next action is replaced by the Best possible action.

• $Q(S_t, A_t)=10$
• $R_{t+1}=2$
• $\gamma=0.9$
• $\alpha=0.5$
• $Q(S_{t+1}, a_1)=8$
• $Q(S_{t+1}, a_2)=11$
• $Q(S_{t+1}, a_3)=5$
• TD Target $=2+0.9(11)=11.9$
• TD Error $=11.9-10=1.9$
• Updated $Q(S_t, A_t)=10+0.5(1.9)=10.95$

Q-Learning Algorithm​

Cliff Walking​

• SARSA (on-policy) accounts for ε-greedy exploration near the cliff and learns the safer route.
• Q-Learning (off-policy) learns the optimal route.
  • but occasionally falls off the cliff during exploration, hurting its online performance

Known MDP vs Unknown MDP​

Model-based vs Model-free​

Monte Carlo Methods​

• A Computational technique that uses random sampling and statistical methods to solve complex problems and estimate numerical results.
  • Named after the Monte Carlo Casino in Monaco.
  • It means Estimate an unknown quantity by sampling, and averaging what you observe.
• Used fo any estimation method whose operation involves a significant random component.
• Used in mathematics, physics, engineering, finance, computer science, etc.
• It is particularly valuable when an analytical solution is difficult or impossible to obtain.

Estimating $\pi$ by Sampling (Monte Carlo Simulation)​

• Mechanism:
  • Generate uniform random points $(x, y) \in [-1, 1] \times [-1, 1]$.
  • Count points falling inside the unit circle ($x^2 + y^2 \le 1$).
  • Estimate $\pi$ via area proportions:

• Empirical Validation:
  • Total samples ($n$): $3000$ points
  • Estimated value: $\pi = 3.1386666666666665$
  • Relative error: $-0.0931\%$ from true value ($\approx 3.14159265$)

Monte Carlo Prediction​

$v_\pi(s) = \mathbb{E}_{\pi}[G_t | S_t = s] \approx \frac{1}{N} \sum_{i=1}^{N(s)} G^{(i)}$

• $\frac{1}{N} \sum_{i=1}^{N(s)} G^{(i)}$: Mean of the returns/rewards
• Model-Free Learning: Operates without prior knowledge of transition dynamics $P$ or reward function $R$.
• Learning from Complete Episodes: Learns state-value functions $v_\pi$ exclusively from full trajectories under policy $\pi$. Only works for episodic tasks where termination at step $T$ is guaranteed.
• No Bootstrapping: Does not update estimates using other value estimates $v(s')$; instead, updates rely solely on actual empirical returns observed at the end of the episode.
• Empirical Mean Returns: The value of state $s$ is estimated by the sample average of all observed returns starting from $s$:

An Episode of Experience & Return Formulation​

• Trajectory Structure: $S_0 \xrightarrow{A_0, R_1} S_1 \xrightarrow{A_1, R_2} S_2 \dots \xrightarrow{A_{T-1}, R_T} S_T$
• Discounted Return ($G_t$): $G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots + \gamma^{T-t-1} R_T$
• Discount Factor ($\gamma = 1$): For episodic tasks with terminal-only rewards (such as Blackjack), setting $\gamma = 1$ is standard practice because the episode length is finite.

First-Visit Monte Carlo​

• First-Visit MC estimates the value function $V(s)$ by averaging returns following only the first occurrence of state $s$ within each sampled episode.
• Algorithmic Flow:
  • Initialize counters $N(s) \leftarrow 0$ and accumulate returns: $G(s) \leftarrow 0 \quad \forall s \in S$
  • Sample a complete episode $i = \{S_{i,0}, A_{i,1}, R_{i,2}, \dots, S_{i,T_i}\}$ generated under policy $\pi$
  • Compute return $G_{i,t} = \sum_{k=t+1}^{T_i} \gamma^{k-t-1} R_{i,k}$ from step $t$ to termination.
  • Only for the first time step $t$ where state $s$ appears in episode $i$:
    • $N(s) \leftarrow N(s) + 1$ (Increment counter for total first visits)
    • $G(s) \leftarrow G(s) + G_{i,t}$ (Increment total return)
    • $V(s) \leftarrow \frac{G(s)}{N(s)}$ (Update the value by mean return)

$A \xrightarrow{R_1=1} B \xrightarrow{R_2=2} A \xrightarrow{R_3 = 1} C \xrightarrow{R_4 = 1} \text{terminal}$

Every-Visit Monte Carlo​

• Every-Visit MC treats every single occurrence of state $s$ within an episode as a valid data sample, accumulating its corresponding return into the empirical mean.
• Algorithmic Flow:
  • Initialize counters $N(s) \leftarrow 0$ and accumulate returns: $G(s) \leftarrow 0 \quad \forall s \in S$
  • Sample a complete episode $i = \{S_{i,0}, A_{i,1}, R_{i,2}, \dots, S_{i,T_i}\}$ generated under policy $\pi$
  • Compute return $G_{i,t} = \sum_{k=t+1}^{T_i} \gamma^{k-t-1} R_{i,k}$ from step $t$ to termination.
  • For each time step $t$ where state $s$ appears in episode $i$:
    • $N(s) \leftarrow N(s) + 1$ (Increment counter for total visits)
    • $G(s) \leftarrow G(s) + G_{i,t}$ (Increment total return)
    • $V(s) \leftarrow \frac{G(s)}{N(s)}$ (Update the value by mean return)

$A \xrightarrow{R_1=1} B \xrightarrow{R_2=2} A \xrightarrow{R_3 = 1} C \xrightarrow{R_4 = 1} \text{terminal}$

Incremental Mean​

$\mu_k = \frac{1}{k} \sum_{j=1}^{k} x_j$

• New estimate = Old estimate + step-size * (new sample - old estimate).
• Memory efficient: Only need to store the old estimate ($\mu_k$) and the number of visits ($k$).

Incremental Monte Carlo​

• Updates the value function $V(s)$ incrementally after each trajectory without requiring memory to store individual past returns.
• Algorithmic Flow:
  • Initialize $N(s) \leftarrow 0$ and $V(s) \leftarrow 0$ for all $s \in S$.
  • Episode sampling: Execute episode $i$ under policy $\pi$ and compute returns $G_{i,t} = \sum_{k=t+1}^{T_i} \gamma^{k-t-1} R_{k}$.
  • Incremental update: For each visited state $s$ at time step $t$:
    • $N(s) \leftarrow N(s) + 1$ (Increment counter for total visits)
    • $V(s) \leftarrow V(s) + \alpha (G_{i,t} - V(s))$ (Update the value by mean return)
    • Where $G_{i,t} - V(s)$ represents the temporal difference (TD) error between the sampled return target and the current estimate.
• Choice step size $\alpha$
  • $\alpha = \frac{1}{N(s)}$: Replicates the exact empirical sample-average of Every-Visit MC where all observed samples receive equal weight.
  • $\alpha = \text{constant}$: Implements an exponential recency-weighted running average that decays outdated experience, making it suited for non-stationary environments where MDP dynamics change over time.
• Cons:
  • Requires a significant number of episodes to converge to the true value function.
  • Requires to terminate the episode.

Model-free Control​

• The MDP model is unknown, or too large/complex to use directly.
• But experience can be sampled.
• Applications:
  • Robo soccer
  • Autonomous vehicles
  • Robotics
  • Game playing
  • Recommender systems
  • Finance & portfolio management

On-Policy vs Off-Policy​

General Policy Iteration​

• Alternates between Policy Evaluation ($V \approx v_\pi$ or $Q \approx q_\pi$) and Policy Improvement ($\pi \leftarrow \text{greedy}$).
• This interplay drives the system asymptotically toward the optimal pair $(v_*, \pi_*)$ or $(q_*, \pi_*)$.

$\pi'(s) = \text{argmax}_{a \in A} \big( \mathcal{R}(s, a) + \gamma \sum_{s' \in S} \mathcal{P}(s' | s, a) V(s') \big)$

• Why $V(s)$ Fails in Model-Free Settings:
  • Finding the maximizing action over $V(s)$ strictly requires the transition model $P(s' \mid s, a)$ and reward function $R(s, a)$.
  • In Model-Free RL, these dynamics are unavailable; hence, $V(s)$ alone cannot guide policy updates without an explicit environment model.

$\pi'(s) = \text{argmax}_{a \in A}Q(s,a)$

• Model-Free Advantage:
  • By estimating $Q(s, a)$ directly through sample episodes, policy improvement requires no knowledge of $P$ or $R$.
  • This fundamental shift makes $Q(s, a)$ estimation the standard paradigm for Model-Free Control (Monte Carlo Control, SARSA, Q-Learning).

• This is why MC Control estimates $q_\pi(s,a)$, not $v_\pi(s)$.

Exploration Problem​

• A greedy agent always chooses the action with the highest current estimated value.
• But what if the current $Q(s,a)$ estimates are inaccurate?

Mystery Box Example​

Initially,

1. Open the red box:
   $R = 0 \rightarrow Q(\text{red}) = 0$

2. Open the blue box:
   $R = +1 \rightarrow Q(\text{blue}) = 1$

3. Keep opening the blue box:
   $R = +1, +3, +2, \ldots \rightarrow Q(\text{blue}) \approx 2$

4. A purely greedy agent now keeps choosing the blue box because
   $Q(\text{blue}) > Q(\text{red})$.

5. However, the red box may actually be better. For example,
   $\mathbb{E}[R \mid \text{red}] = 5$.

   The agent does not know this because it sampled the red box only once.

Exploitation vs. Exploration​

• Exploitation: Choose the action that currently has the highest estimated value.
• Exploration: Try less-sampled or unfamiliar actions to discover whether they may actually be better.
• In this example, the agent should occasionally explore the red box because it has not been sampled enough to confidently conclude that it is worse.

$\epsilon$-Greedy Exploration​

• if $\epsilon = 0.1$, then the agent will choose the greedy action with probability $0.9$ (Exploitation)
• And the random action with probability $0.1$ (Exploration).
• Policy Improvement Theorem:
  • for any $\epsilon$-greedy policy $\pi$
  • The $\epsilon$-greedy policy $\pi'$ is as good or better than the original policy $\pi$: $v_{\pi'}(s) \geq v_{\pi}(s)$

Monte Carlo Control​

• Traditional Policy Iteration:
  • Fix the policy $\pi$.
  • Evaluate the current policy until $Q$ is sufficiently close to $q_\pi(s,a)$.
  • Improve the policy using the estimated action values.
  • Repeat policy evaluation and policy improvement.
• Monte Carlo Control:
  • Perform MC Policy Evaluation after every episode.
  • Improve the policy using $\epsilon$-greedy after every episode.
  • $Q_1 \rightarrow \pi_1 = \epsilon\text{-greedy}(Q_1)$
  • $Q_2 \rightarrow \pi_2 = \epsilon\text{-greedy}(Q_2)$
  • $\cdots$
  • Eventually approaches $(q_*, \pi_*)$ under appropriate convergence conditions.

GLIE​

Greedy in the Limit with Infinite Exploration

1. $\lim_{k \to \infty} N_k(s,a) = \infty$
2. $\lim_{k \to \infty} \pi_k(a|s) = 1(a = \argmax_{a' \in A} Q_k(s,a'))$

• Explore enough early -> Explore less over time -> Eventually greedy.
  • $N_k(s,a)$: How many times the state-action pair $(s,a)$ has been visited in the $k$-th episode.
  • $\pi_k \rightarrow \text{greedy}(Q_k)$
• Infinite exploration first, greedy behavior in the limit.

GILE Monte Carlo Control​

• Algorithm flow:
  • Run episode $k = \{S_0, A_0, R_1, \dots, S_{T}\}$ with policy $\pi_k$.
  • For each state-action pair $(s,a)$ in the episode:
    • $N_k(s,a) \leftarrow N_k(s,a) + 1$
    • $Q_k(s,a) \leftarrow Q_k(s,a) + \frac{1}{N_k(s,a)} (G_k - Q_k(s,a))$
  • Improve the policy based on the new $Q$ value.
    • $\epsilon \leftarrow \frac{1}{k}$
    • $\pi \leftarrow \epsilon\text{-greedy}(Q)$
  • Repeat until convergence.
• old estimate + step-size * (new sample - old estimate).
  • old estimate = $Q(S_t, A_t)$
  • new sample = $G_t$
  • step-size = $\frac{1}{N_k(s,a)}$
• Run Episode → Update Q → Reduce $\epsilon$ → Improve Policy

DP vs MC​

• Dynamic Programming:
  • Model-based
  • Bootstrapping: Updating a value estimate using another estimated value instead of waiting for the final outcome.
  • Lower variance
• Monte Carlo:
  • Model-free
  • No bootstrapping: It uses rewards that actually occurred, not an estimated value of the next state.
  • Uses complete sampled returns
  • Requires episodic tasks
  • Higher variance

MDP​

$(\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma)$

• At each time step $t$, the agent observes state $S_t \in \mathcal{S}$ and chooses action $A_t \in \mathcal{A}$
• Receives reward $R_{t+1} \in \mathcal{R}$
• Transitions to a new state $S_{t+1}$