10. Reinforcement Learning¶

10.1 Why RL Appears In A DDM Course¶

Intuition

Reinforcement learning is about learning from decisions and their consequences. DDM and RL both study sequential decisions, but the exam notation should remain DDM notation.

RL is useful when:

transition probabilities are unknown,
values must be learned from simulation or data,
exploration is needed to learn what works.

DDM translation

RL phrase	DDM meaning
agent	decision maker
action	decision \(x\)
reward	\(R(S_k,x)\)
state	\(S_k\)
policy	\(\pi\)
value	future value \(V(S_k^x)\) or related estimate

10.2 Exploration and Exploitation¶

Intuition

Exploitation means choosing what currently looks best. Exploration means trying alternatives to learn.

Example:

Always assigning the closest driver exploits current knowledge.
Occasionally preserving the closest driver explores whether that improves future service.

Formal epsilon idea

\[ \begin{aligned} \Pr(\text{choose current best}) &= 1-\epsilon,\\ \Pr(\text{explore another feasible decision}) &= \epsilon. \end{aligned} \]

Translation:

\(\epsilon\) controls how often the policy experiments.

Properties

Too little exploration can trap the system in bad habits.
Too much exploration hurts current performance.
Simulation is often a safer place to explore than live operations.

10.3 Learning Value Estimates¶

Intuition

RL-style value learning updates estimates after observing what happened.

Simple update

\[ \text{new estimate} = \text{old estimate} + \alpha\left(\text{observed target}-\text{old estimate}\right) \]

where:

\(\alpha\) is the learning rate,
the observed target is the new evidence.

DDM VFA version

\[ \hat V_{new}(S_k^x) = \hat V_{old}(S_k^x) + \alpha\left(\text{observed future value}-\hat V_{old}(S_k^x)\right) \]

Worked example

Old estimate:

\(\hat{V}=50\).

Observed future value:

Learning rate:

\(\alpha=0.25\).

Update:

\[ \begin{aligned} \hat V_{new} &= 50 + 0.25(70-50) \\ &= 50+5 \\ &= 55 \end{aligned} \]

10.4 Model-Based and Model-Free Intuition¶

Intuition

Model-based methods use a model or simulator of transitions. Model-free methods learn values or policies directly from experience.

DDM comparison

Type	Uses transition model?	DDM examples
Model-based	yes	exact DP, look-ahead, scenario simulation
Model-free	not explicitly	value learning from observed trajectories

Properties

Model-based methods can plan before acting if the model is good.
Model-free methods can learn when the transition model is hard to specify.
Many practical DDM systems mix both.

10.5 Q-Learning and SARSA, Intuitively¶

This section is only for DDM-focused intuition. Do not replace DDM notation with RL notation in exam modeling answers.

Intuition

Instead of estimating the value of a state, action-value learning estimates the value of taking a particular decision in a state.

DDM-friendly notation:

\[ \hat Q(S_k,x) = \text{estimated total value of choosing }x\text{ in }S_k \]

Decision:

Choose the feasible decision with the largest estimated action value:

\[ x=\arg\max_{x\in X(S_k)}\hat{Q}(S_k,x). \]

Q-learning idea:

learn from the best estimated next decision

SARSA idea:

learn from the next decision actually taken

Properties

Method	Intuition	Business interpretation
Q-learning	learns a greedy target policy	what would be best if we acted greedily later
SARSA	learns value of behavior policy	what happens under the policy we actually use

Exam phrase

RL methods are relevant because they learn value estimates or policies from experience. In DDM exam answers, however, the problem should still be modeled using \(S_k\), \(x\in X(S_k)\), \(R(S_k,x)\), \(S_k^x\), \(\omega_{k+1}\), and the policy \(\pi\).

10.6 RL as Learning a Better DDM Policy¶

Intuition

In this course, RL should be understood as a learning layer on top of the DDM loop. The system tries decisions, observes rewards/costs, and updates future decisions.

flowchart LR
    A["Observe state S_k"]:::state --> B["Choose decision x"]:::decision
    B --> C["Observe reward/cost R(S_k,x)"]:::reward
    C --> D["Observe next state S_{k+1}"]:::state
    D --> E["Update value or policy estimate"]:::learn
    E --> A
    classDef state fill:#e0f2fe,stroke:#0284c7,stroke-width:2px,color:#0f172a;
    classDef decision fill:#ffedd5,stroke:#ea580c,stroke-width:2px,color:#0f172a;
    classDef reward fill:#dcfce7,stroke:#16a34a,stroke-width:2px,color:#0f172a;
    classDef learn fill:#ede9fe,stroke:#7c3aed,stroke-width:2px,color:#0f172a;

Formal DDM-friendly action value

\[ \hat{Q}(S_k,x) = \text{estimated total value of choosing decision }x\text{ in state }S_k. \]

Decision rule:

\[ x=\arg\max_{x\in X(S_k)}\hat{Q}(S_k,x). \]

Translation:

Instead of valuing only the state, this values each possible decision in the state.

Worked example: learning whether to wait

A dispatcher can send a driver immediately or wait 5 minutes for possible batching.

Observed historical/simulated outcomes:

State type	Decision	Average total cost
low demand	send now	20
low demand	wait	28
high demand	send now	35
high demand	wait	24

Learned policy:

if low demand: send now
if high demand: wait

Business interpretation:

The value of waiting depends on the state.

Approach comparison

RL idea	DDM interpretation	Merit	Risk
exploration	try non-greedy decisions	discovers better policies	can hurt current service
exploitation	use best-known decision	good current performance	may stop learning
model-based RL	learn/use simulator	can plan with samples	simulator bias
model-free RL	learn values from experience	less model engineering	data hungry

10.7 DDM-Focused RL: What To Know Without Switching Notation¶

Mental model

The slides mention reinforcement learning as a computational method for solving decision models. For this course, RL is best understood as learning from repeated interaction with a dynamic system. It is relevant because the learner observes states, takes decisions, receives rewards/costs, and improves a policy.

DDM translation

RL phrase	DDM phrase
environment	stochastic dynamic system
state	\(S_k\)
action	\(x\in X(S_k)\)
reward	\(R(S_k,x)\)
transition	\(\omega_{k+1}\) and \(S_{k+1}\)
value estimate	\(\hat{V}(S_k^x)\) or action-value estimate
policy	\(\pi\)

Exploration vs exploitation

Exploitation chooses the currently best estimated decision:

\[ \arg\max_{x\in X(S_k)} \left[R(S_k,x)+\hat V(S_k^x)\right]. \]

Exploration sometimes tries a less certain decision to learn whether it is better than expected.

Worked example: learning driver repositioning

A ride-hailing platform estimates that keeping a driver downtown has value 8 and moving to the suburb has value 5. Exploitation keeps the driver downtown. But if the suburb has limited data, exploration may occasionally reposition there to learn whether hidden demand exists.

Course boundary

RL formulas such as Q-learning or SARSA are not the main notation for this exam. If mentioned, translate back to DDM: they are ways to learn decision values or policies from repeated simulated or observed transitions.

Chapter source note

Course basis: DDM lecture topic on reinforcement learning and VFA/ADP links. Textbook enrichment: Kochenderfer et al. on exploration/exploitation, model-based/model-free methods, Q-learning, and SARSA; Powell on learning and optimization in sequential decisions. In exam modeling answers, translate RL concepts back to DDM notation.