Introduction to Immediate RL

Main ideas / concepts conveyed

1. Immediate Reinforcement Learning (IRL) setup

   • The video frames an “immediate” RL problem where:
     • You perform an action from a set.
     • The environment immediately returns a reward / evaluation / payoff.
     • Rewards are based on the state of the world (which may be partially unknown) and the correctness of the action, with no delayed credit assignment.

2. Rewards come from the environment; observations and system dynamics

   • The learner receives:
     • A problem description / problem state (context for the agent).
     • An action choice.
   • The environment then produces:
     • A reward/evaluation (payoff) according to the system’s configuration.
   • The speaker emphasizes that the input/state tells you “what’s going on,” but the exact mapping from action to outcome may be uncertain.

3. Uncertainty modeled via sampling from unknown distributions

   • For each action, reward is not deterministic; it is sampled from a probability distribution.
   • Example: coin toss
     • An action corresponds to a coin with different probabilities of heads vs tails.
     • Payoff depends on the coin outcome; the key point is that outcome probabilities differ by action.
   • The expected reward is the weighted average over possible outcomes.

4. Why repeated interaction is needed

   • Because outcomes are stochastic, the learner cannot determine the best action from only one trial.
   • The speaker argues you must repeat actions many times to:
     • collect enough samples
     • estimate which action yields higher expected payoff

5. Exploration vs. exploitation

   • A central methodological tension in immediate RL:
     • Exploration: try different actions (often randomly) to gather information about reward distributions.
     • Exploitation: use current knowledge to choose the action that appears best.
   • Exploration is especially necessary early because you haven’t learned enough about the action-outcome relationships yet.
   • The video suggests switching from exploration to exploitation once sufficient information is acquired, while still acknowledging ongoing uncertainty.

6. Immediate RL as groundwork for wider RL

   • The speaker contrasts:
     • what’s often shown in course/tutorial settings (more prescriptive)
     • vs. how it appears in textbooks
   • The class emphasizes additional reasoning, motivation, and research questions.
   • Many ideas transfer into full reinforcement learning settings beyond simple immediate/bandit-like cases.

7. Terminology: reward vs payoff vs evaluation vs cost

   • Multiple terms describe the same reward-like quantity:
     • Reward / payoff / evaluation (the quantity received after an action).
   • Cost is framed differently:
     • associated with control theory / information
     • payoff is associated with economics
   • The class chooses terminology based on context and literature conventions.

8. Sampling from distributions (implementation concept)

   • To generate a random outcome from a discrete distribution with probabilities (p_1, p_2, \ldots):
     • compute cumulative sums (e.g., (p_1), (p_1+p_2), (p_1+p_2+p_3), …)
     • generate a random number in ([0,1])
     • select the outcome whose cumulative interval contains the random number
   • For Gaussian distributions, sampling produces values most likely near the mean, consistent with the distribution.
   • Caution: don’t incorrectly return the most probable value; you must sample.

9. Core modeling objective

   • After sampling:
     • for each action, infer its true expected payoff (unknown in advance).
   • The learner’s task becomes:
     • identify which action has the highest expected value based on estimated reward statistics

---

Methodology / instruction-like steps (as presented)

A) Immediate RL interaction loop (conceptual)

• Given

  • A set of actions (e.g., action 1, action 2, …)
  • A reward/payoff mechanism from the environment (stochastic)
  • A problem state / context (problem description)

• Repeat

  1. Choose an action (initially may require exploration)
  2. Perform the action in the environment
  3. Receive an immediate reward/payoff (evaluation sampled from that action’s distribution)
  4. Update knowledge about which actions yield better expected payoff

• Goal

  • Choose the action with the maximum expected payoff after learning enough

B) Exploration vs exploitation strategy (conceptual)

• Exploration phase

  • Try different actions, potentially using randomness, to gather samples
  • Rationale: outcomes are stochastic; repeated trials are required

• Exploitation phase

  • Choose the action that currently appears to have the highest expected reward based on collected data

• Switching logic

  • Transition from exploration to exploitation once sufficient information is available (while still accounting for uncertainty)

C) Sampling outcomes from a discrete probability distribution (explicit procedure)

• Input

  • Discrete outcomes with probabilities (p_1, p_2, \dots, p_n) where (\sum p_i = 1)

• Procedure

  1. Compute cumulative probabilities:
     • (c_1 = p_1)
     • (c_2 = p_1 + p_2)
     • (c_3 = p_1 + p_2 + p_3)
     • …
     • (c_n = 1)
  2. Generate a random number (u \sim \text{Uniform}(0,1))
  3. Select the outcome based on where (u) falls:
     • If (u \in (0, c_1]), pick outcome 1
     • If (u \in (c_1, c_2]), pick outcome 2
     • If (u \in (c_2, c_3]), pick outcome 3
     • Continue similarly until outcome (n)

• Key caution

  • Don’t deterministically pick the most probable outcome; you must sample

---

Speakers / sources featured

• Bill (speaker; exact last name not provided in the subtitles)
• William (referenced as “Bill”)
• Other references mentioned (not named sources):
  • “textbooks” (unnamed)
  • “economic community” (general reference)
  • “control theory / information” and “psychology” (general academic fields)