Returns, Value functions and MDPs

Main ideas and concepts

• Long-term objective via “return”

  • The lecture motivates optimizing the long-term outcome, not just immediate rewards.
  • Return is introduced as a standard notation:
    • Let (T) be the timestamp when the episode ends (the end of the trajectory).
    • Return is essentially the (possibly discounted) sum of future rewards until episode termination.

• Why maximizing immediate rewards can fail

  • If you optimize reward at each near-term step independently, you can get:
    • High rewards soon (e.g., at (T+1), (T+2))
    • But end up in a bad future state where later rewards are poor.
  • The correct goal is to choose actions so that the overall future return is maximized, even if some intermediate rewards are small.

• Return is complicated by random episode length

  • (T) is random, not fixed.
  • Example intuition:
    • In chess or tic-tac-toe, the game may end at different move counts each run.
    • Therefore the return (G_T) is also a random variable because it depends on when termination occurs and on stochastic transitions.

• Discounted return ((\gamma)-return)

  • When the horizon is infinite (continuing forever), if (\gamma < 1) and individual rewards are bounded, the discounted sum converges (stays finite).
  • Discount factor (\gamma) interpretation:
    • (\gamma = 0) → optimize only the next immediate reward.
    • Larger (\gamma) → rewards further in the future matter more.
  • Concrete example (grasping robot intuition):
    • If there’s a constant cost (e.g., -1) and a big reward (e.g., +100) when a goal is achieved:
      • With (\gamma = 0.8), achieving sooner yields higher value because delayed success is multiplied by (\gamma^{\text{large exponent}}) (very small).
  • Tradeoff/policy dependence
    • Choosing (\gamma) can make the optimal policy change substantially.
    • (\gamma) is a free parameter that must be tuned, and different values can imply different “farsighted vs nearsighted” behaviors.
  • No special “solvable” choice
    • There is critique that (\gamma) can be awkward if the intended objective is “total reward” / “cumulative reward,” because discounting changes the objective itself.

• Mismatch in perspective: RL vs bandit communities

  • RL “bandit” problems may be treated as single-sample/immediate learning episodes by RL practitioners.
  • Bandit-theory researchers treat the interaction as the entire learning process (a full episode).
  • Vocabulary mismatch exists (e.g., how bandits/long-term factors are framed).

• Average reward as an alternative (no (\gamma))

  • Another return notion is average reward return:
    • It avoids the discount parameter (\gamma).
  • Issues:
    • For infinite trajectories, the average may fail to converge unless additional assumptions hold.
    • Example failure mode:
      • Periodic reward sequences → averages can oscillate and thus the limit may not exist.
    • Remedy concept:
      • Cesàro limit: average across periods, then take the number of periods to infinity.
  • Conceptual comparison:
    • Discounted return includes (\gamma), giving temporal preferences.
    • Average reward removes (\gamma), but has convergence/limit concerns.

• Example of discounted vs average objective

  • A toy “heaven vs hell” setup is used to show:
    • With discounting, the preference between paths depends on (\gamma).
    • With average reward, long-run averages can dominate so preferences can be more stable/independent of early transient effects.
  • Main takeaway:
    • Discounting changes what counts as optimal; it bakes temporal weighting into the objective.

---

Value functions and policy conditioning

• Value function definitions

  • Policy (\pi) determines not only the next action but the entire future behavior.
  • (V^\pi) is the value function for policy (\pi):
    • It represents the expected return when starting from a state (s) and then following policy (\pi).
  • The expectation is over randomness from:
    • Stochastic policy (the policy may pick different actions in the same state)
    • Stochastic environment (state transitions can vary)

• Expectation must be conditioned on (\pi)

  • Future rewards depend on actions chosen in the future, which depend on (\pi).
  • Hence (V^\pi(s)) is explicitly defined as an expectation over trajectories generated by following (\pi).

• Difference between (V) and (Q) (state vs state-action)

  • Earlier (Q)-style thinking gave a notion of “how good it is to take an action.”
  • For (V^\pi), the policy fixes actions after the initial state:
    • The first decision/action is the part tied to the current state when evaluating (V^\pi(s)).
    • (Q^\pi(s,a)) would explicitly evaluate for a specific chosen action (a) in state (s).

---

Markov assumption and Markov Decision Processes (MDPs)

• Why history matters without assumptions

  • In general, to predict the next state (s_{t+1}), you might need the full history.
  • Example analogy: riding a bicycle might depend on more than the current state—it could depend on past momentum/velocity changes.

• Markov assumption (first-order)

  • The lecture states the Markov assumption:
    • The next state depends only on the current state and current action, not on the full past.
    • Formally: [ P(s_{t+1} \mid \text{history}) = P(s_{t+1} \mid s_t, a_t). ]

• Stationarity assumption

  • The environment is assumed stationary:
    • Transition and reward dynamics do not change over time.

• MDP components needed to specify the problem

  • To define a reinforcement learning problem (under the MDP framework), you need:
    • State space: all possible states (s)
    • Action set: actions (a) available in states
    • Transition probabilities / transition function: how (s) evolves
    • Reward model (expected reward / reward function)
    • If using discounted return, also:
      • Discount factor (\gamma)

• How joint distributions are factored (high-level)

  • Instead of specifying the full joint distribution over ((s_{t+1}, r_{t+1})) directly, it can be specified via:
    • Transition (P(s_{t+1} \mid s_t, a_t))
    • Expected reward given (s_t, a_t, s_{t+1})
  • Justification given:
    • Because the objective optimizes expected return, knowing expectations (not full reward distributions) can be sufficient.

• Definition: Markov Decision Process

  • A system with:
    • Markovian state evolution
    • States, actions (decisions)
    • Markovian reward/transitions
  • is called a Markov Decision Process (MDP).

• Why value functions rely on the Markov property

  • Value functions treat state value as depending only on the state (s), not on how the agent arrived there.
  • This is only coherent if the Markov property holds (past history is irrelevant given current state).
  • If Markov property is violated:
    • value functions may still be used later, interpreted as marginalizing over histories (acknowledged as a practical workaround).

• Next steps

  • The lecture ends by stating the next class will cover optimal value functions.

---

Speaker / sources featured

• No specific external sources are named.
• The only speaker referenced is the lecturer/professor delivering the lecture (no name given in the subtitles).