RL Foundations: MDPs & Value Functions

Suppose you own the notification system for a consumer app. Every time a user finishes a session, you decide: send a re-engagement notification now, or wait. Send too often and users mute the app or uninstall it — you have burned a scarce, decaying resource for a small short-term bump in opens. Send too rarely and you leave engagement on the table. The catch that makes this hard is not the individual decision — it is that today's send changes tomorrow's optimal decision. A user notified three times this week is closer to muting the channel than one notified once, so "should I send" depends on a history the system has to track and reason about over time, not just on right-now features.

This is the shape of almost every "should the system act now, knowing it will get to act again later" problem you will meet in an ML system design interview: notification timing, ad load per session, retry budgets, pricing over a customer lifetime, dialogue turn selection, inventory replenishment. Supervised learning has no native concept for this — it predicts a label for an input, once, with no notion that the prediction changes the next input it will see. Reinforcement learning (RL) is the framework built for exactly this: an agent takes actions, the world responds with a new situation and a reward, and the agent's job is to choose actions that maximize reward accumulated over time, not just this instant.

This subject builds the formal skeleton everything else in the track hangs on: the Markov Decision Process (MDP), returns and discounting, value functions, and the Bellman equations that make them computable. Every definition is built directly on the notification agent — not an abstract gridworld — because that is what interviewers actually ask you to model. A small gridworld appears once, briefly, purely to make the dynamic-programming algorithms easy to trace by hand. Later subjects in this track — Value-Based Methods: Q-Learning to DQN, Policy Gradients & Actor-Critic, and PPO & Modern Policy Optimization — all learn approximations to the objects defined here; if the objects are fuzzy, everything downstream is fuzzy too.

Framing the Notification Agent as Sequential Decision-Making

Before any formalism, get the mental model straight. A supervised click-through model answers "will this specific notification, sent now, be opened?" — a single prediction, evaluated in isolation. The RL framing asks a different, harder question: "given everything I know about this user's notification history, which action — send or wait — leads to the best sequence of outcomes, including notifications I haven't sent yet?"

Concretely, picture the interaction as a loop between an agent (your notification policy) and an environment (the user, plus the app's engagement dynamics):

graph LR
    AGENT["Agent<br/>(policy)"] -->|"action a_t (send / wait)"| ENV["Environment<br/>(user)"]
    ENV -->|"next state s_{t+1},<br/>reward r_{t+1}"| AGENT

At each opportunity t (say, once per idle period), the agent observes a state s_t, chooses an action a_t, and the environment returns a reward r_{t+1} and a new state s_{t+1}. The loop repeats until the episode ends (the user churns, or a fixed horizon is reached). Everything in this subject is about formalizing that loop precisely enough to compute an optimal policy from it.