Volume 1: Mathematical Foundations

Learning objectives Identify the main components of an RL system: agent, environment, state, action, reward. Compute the discounted return for a sequence of rewards. Relate the gridworld to real tasks (e.g. navigation, games) where an agent gets delayed reward. Concept and real-world RL In reinforcement learning, an agent interacts with an environment: at each step the agent is in a state, chooses an action, and receives a reward and a new state. The return is the sum of (discounted) rewards along a trajectory; the agent’s goal is to maximize this return. A gridworld is a simple environment where states are cells and actions move the agent; it models robot navigation (e.g. a robot moving to a goal in a warehouse) and game AI (e.g. a character moving on a map). In robot navigation, the state might be (row, col); the action is up/down/left/right; the reward is +1 at the goal and often 0 or a small penalty per step. Discounting (\(\gamma < 1\)) makes future rewards worth less than immediate ones and keeps the return finite in long or infinite horizons. ...

Learning objectives Implement a multi-armed bandit environment with Gaussian rewards. Compare epsilon-greedy and greedy policies in terms of average reward and regret. Recognize the exploration–exploitation trade-off in a simple setting. Concept and real-world RL A multi-armed bandit is an RL problem with a single state: the agent repeatedly chooses an “arm” (action) and receives a reward drawn from a distribution associated with that arm. The goal is to maximize cumulative reward. Exploration (trying different arms) is needed to discover which arm has the highest mean; exploitation (choosing the best arm so far) maximizes immediate reward. In practice, bandits model A/B testing, clinical trials, and recommender systems (which ad or item to show). The 10-armed testbed is a standard benchmark: 10 arms with different unknown means; the agent learns from experience. ...

Learning objectives Understand why initializing action values optimistically can encourage exploration. Implement optimistic initial values and compare with epsilon-greedy on the 10-armed testbed. Recognize when optimistic initialization helps (stationary, deterministic-ish) and when it does not (nonstationary). Theory Optimistic initial values mean we set \(Q(a)\) to a value higher than the typical reward at the start (e.g. \(Q(a) = 5\) when rewards are usually in \([-2, 2]\)). The agent then chooses the arm with the highest \(Q(a)\). After a pull, the running mean update \(\bar{Q}_{n+1} = \bar{Q}_n + \frac{1}{n+1}(r - \bar{Q}_n)\) brings \(Q(a)\) down toward the true mean. So every arm looks “good” at first; as an arm is pulled, its \(Q\) drops toward reality. The agent is naturally encouraged to try all arms before settling, which is a form of exploration without epsilon. ...

Learning objectives Define an MDP: states, actions, transition probabilities, and rewards. Write transition probability matrices \(P(s’ | s, a)\) for a small MDP. Recognize the Markov property: the next state and reward depend only on the current state and action. Concept and real-world RL A Markov Decision Process (MDP) is the standard mathematical model for RL: a set of states, a set of actions, transition probabilities \(P(s’, r | s, a)\), and a discount factor. The Markov property says that the future (next state and reward) depends only on the current state and action, not on earlier history. That allows us to plan using the current state alone. Real-world examples include board games (state = board position), robot navigation (state = position/velocity), and queue control (state = queue lengths). Writing out \(P\) and reward tables for a tiny MDP is the first step toward value iteration and policy iteration. ...

Learning objectives Understand the UCB1 action-selection rule and why it explores uncertain arms. Implement UCB1 on the 10-armed testbed and compare with epsilon-greedy. Interpret the exploration bonus \(c \sqrt{\ln t / N(a)}\). Theory UCB1 (Upper Confidence Bound) chooses the action that maximizes an upper bound on the expected reward: [ a_t = \arg\max_a \left[ Q(a) + c \sqrt{\frac{\ln t}{N(a)}} \right] ] \(Q(a)\) is the sample mean reward for arm \(a\). \(N(a)\) is how many times arm \(a\) has been pulled. \(t\) is the total number of pulls so far. \(c\) is a constant (e.g. 2) that controls exploration. The term \(c \sqrt{\ln t / N(a)}\) is an exploration bonus: arms that have been pulled less often (small \(N(a)\)) get a higher bonus, so they are tried more. As \(N(a)\) grows, the bonus shrinks. So UCB1 explores systematically rather than randomly (unlike epsilon-greedy). ...

Learning objectives State the reward hypothesis: that goals can be captured by scalar reward signals. Design a reward function for a concrete task and anticipate unintended behavior. Identify and fix “reward hacking” (exploiting the reward design instead of the intended goal). Concept and real-world RL The reward hypothesis says that we can capture what we want the agent to do by defining a scalar reward at each step; the agent’s goal is to maximize cumulative reward. In practice, reward design is hard: the agent will optimize exactly what you reward, so oversimplified or buggy rewards lead to reward hacking (e.g. the agent finds a loophole that yields high reward without achieving the real goal). Examples: a robot rewarded for “distance to goal” might push the goal; a game agent rewarded for “score” might find a way to increment score without playing. Self-driving, robotics, and game AI all require careful reward shaping and testing for exploits. ...

Learning objectives Define a gridworld MDP: grid cells as states, actions (up/down/left/right), transitions, and terminal states. Understand how hitting the boundary keeps the agent in place (or wraps, depending on design). Use gridworld as the running example for policy evaluation and policy iteration. What is Gridworld? Gridworld is a simple MDP used throughout RL teaching and research. The environment is a grid of cells (e.g. 4×4 or 5×5). The state is the agent’s position \((i, j)\). Actions are typically up, down, left, right. Transitions: taking an action moves the agent one cell in that direction; if the move would go off the grid, the agent either stays in place (and usually receives the same step reward) or the world wraps, depending on the specification. ...

Learning objectives Understand the Bayesian view: maintain a posterior over each arm’s reward distribution. Implement Thompson Sampling for Bernoulli and Gaussian rewards. Compare Thompson Sampling with epsilon-greedy and UCB1. Theory (pt 1): Bernoulli bandits Suppose each arm gives a reward 0 or 1 (e.g. click or no click). We model arm \(a\) as Bernoulli with unknown mean \(\theta_a\). A convenient prior is Beta: \(\theta_a \sim \text{Beta}(\alpha_a, \beta_a)\). After observing \(s\) successes and \(f\) failures from arm \(a\), the posterior is \(\text{Beta}(\alpha_a + s, \beta_a + f)\). ...

Learning objectives Define the state-value function \(V^\pi(s)\) as the expected return from state \(s\) under policy \(\pi\). Write and solve the Bellman expectation equation for a small MDP. Use matrix form (linear system) when the MDP is finite. Concept and real-world RL The state-value function \(V^\pi(s)\) is the expected (discounted) return starting from state \(s\) and following policy \(\pi\). It answers: “How good is it to be in this state if I follow this policy?” In games, \(V(s)\) is like the expected outcome from a board position; in navigation, it is the expected cumulative reward from a location. The Bellman expectation equation expresses \(V^\pi\) in terms of immediate reward and the value of the next state; for finite MDPs it becomes a linear system \(V = r + \gamma P V\) that we can solve by matrix inversion or iteration. ...

Learning objectives Understand how reward choice affects optimal behavior (what the agent will try to maximize). Use step penalties and terminal rewards in gridworld to encourage short paths or goal reaching. Avoid common pitfalls: reward hacking and unintended incentives. Why rewards matter The agent’s goal in an MDP is to maximize cumulative (often discounted) reward. So the reward function defines the task. Changing rewards changes what is “optimal.” Design rewards so that the behavior you want is exactly what maximizes total reward. ...