Value Function Based Methods

Main ideas / lessons

• Value-function-based methods (as framed in the textbook) aim to estimate action values rather than compute the true optimal value directly.
• The method conceptually builds:
  • (Q^*): the true (optimal) expected payoff for each action.
  • (Q_T(a)): the agent’s estimate of (Q^*(a)) at time (T).
  • (V(\cdot)) / (v): when estimating values associated with states, the speaker uses (v) to denote the value function (with a note about notation conventions).

Notation / symbols the speaker uses (and why)

• (Q) = action-value estimate (expected payoff).
• (v) (value function) = value attached to a state.
• Notation confusion in the RL literature:
  • Some literature uses (J) for value, (Q) for cost, etc.
  • The lecture tries to follow “Edition two” notation, but admits occasional slips into “Edition one” style.
• Indicator function notation:
  • Uses (I(\cdot)) instead of (I/\Delta) to denote an indicator:
    • (I(a=\text{something}) = 1) if true, else (0).

Action selection policies

1) Greedy (pure exploitation)

• At time (T), choose the action maximizing the current estimate: [ A_T = \arg\max_a Q_T(a) ]

• Limitation (key concept):

  • If early samples make one action look good, greedy may never sample other actions, even if they are actually better.

2) ε-greedy (exploration + exploitation)

• Goal: ensure exploration so all actions can be sampled eventually.

• Probability rule:

  • With probability (1-\varepsilon): choose the greedy action: [ \arg\max_a Q_T(a) ]

  • With probability (\varepsilon): explore by choosing uniformly from all actions.

  • Nuance about the probability of selecting the greedy action during uniform exploration:
  • If there are (n) actions: [ P(\text{greedy action}) = (1-\varepsilon) + \varepsilon/n ] [ P(\text{choosing a non-greedy action}) = \varepsilon (n-1)/n ]

• Clarification of “ε”:

  • The lecture distinguishes this ε from other uses of ε (e.g., conceptually different “ε-optimality / PAC-style” meanings).

3) Softmax (Boltzmann) exploration

• Idea: instead of giving equal probability to all non-greedy actions, give probability proportional to the estimated values.
• Problem with raw proportionality:
  • If some (Q_T(a)) are negative, raw proportional probabilities could be negative.
• Fix: exponentiate using softmax
  • Action probabilities depend on (e^{Q_T(a)}) to avoid negative probabilities.
• Temperature parameter (β):
  • Introduce a temperature (denoted β) to tune randomness:
    • Very large β → exponentials become similar → policy approaches uniform random.
    • β → 0 → distribution becomes peaked → policy approaches greedy.
• Intuition (example framing):
  • If one action’s value is much higher than others, softmax picks it most of the time, but not always.

Relationship to correctness / convergence

• With ε-greedy and persistent exploration:
  • If ε is fixed, the agent can learn the correct values but will keep acting randomly a fraction of the time.
  • Example: ε = 0.1 means ~10% random forever.
• Therefore, for stronger “eventually behave optimally” claims, ε should decrease (“cool”) over time.

Cooling schedules

• A typical sufficient decay rate mentioned:
  • ε decreases on the order of (1/T).
• Practical issue:
  • This can make convergence very slow.

Practical workaround

• Cool ε in stages:
  • use high ε for a while,
  • reduce ε,
  • repeat.
• Duration per ε level depends on factors and may be set via empirical estimates.

Efficient updating of (Q_T(a)) (incremental averaging)

Naive approach vs incremental update

• Naively, to compute (Q_T(a)), you would:
  • store all past rewards for action (a),
  • average them at time (T).
• The lecture provides an incremental update so you do not need full history.

Definitions

• Let (N_a) = number of times action (a) has been taken so far.
• When action (a) is taken at time (T), the estimate updates by combining:
  • the previous estimate, and
  • the newly observed reward (r_t).

Update logic (stochastic averaging form)

• The update is framed as:
  • current estimate + step_size × (error term),
• where the error term reflects how the observed reward (r_t) differs from the previous estimate (Q_{T-1}(a)) (when (a) was chosen).

Why it’s called “stochastic averaging”

• The target would ideally involve expected reward.
• The algorithm uses the sample reward instead, so the update uses a sample-based estimate of the expected error.

Step-size choice

• The specific step-size corresponds to exact averaging:
  • equivalent to computing the sample mean without storing all samples.

Stationarity vs non-stationarity (and handling via constant α)

Stationary assumption

• “Stationary” means:
  • the reward distribution does not change over time (even though outcomes can still vary).

Non-stationary problem

• If the environment changes over time (e.g., a coin wears so head/tail frequencies drift):
  • old samples become less relevant,
  • recent samples should matter more.

Why decaying step size can fail under non-stationarity

• Sample-mean updates shrink weight like (1/N).
• After many samples, new observations have tiny impact, so the estimate doesn’t adapt.

Practical solution: use constant learning rate α (< 1)

• Replace (1/N)-style decaying weights with a constant α.
• Effect:
  • older rewards get exponentially decayed weight,
  • the method tracks changing distributions better.

Trade-off

• If the environment is stationary:
  • constant α prevents full convergence; estimates keep oscillating.

• If non-stationary:

  • constant α enables better tracking (imperfect but preferable).

• Lecture practice note:

  • theory often uses decaying α for convergence guarantees,
  • practice often uses constant α.

Speakers / sources featured

• Speaker: the course instructor/lecturer (no name provided in the subtitles).
• Source referenced: a textbook (specifically “SAT and B book”), with explicit mention of Edition one vs Edition two notation differences.
• Other named sources/speakers: none explicitly identified beyond these references.