Reinforcement Learning Foundations

Introduction and Context

Reinforcement learning (RL) is a framework for learning how to make decisions through interaction with an environment. An artificial agent observes the current situation, selects an action, receives feedback, and then uses the experience to improve future decisions. Unlike supervised learning, where correct examples are supplied, reinforcement learning usually provides evaluative feedback rather than explicit instructions for every decision.

RL is especially useful when actions have consequences that unfold over time. Examples include robot navigation, game playing, recommendation, traffic-signal control, inventory management, industrial process control, and adaptive resource allocation. In each case, a decision may produce an immediate benefit but also affect later opportunities. The central challenge is therefore not merely to choose a good action now, but to learn a strategy that produces desirable long-term outcomes.

This chapter introduces the formal vocabulary and mathematical foundations required for later study of Markov decision processes, dynamic programming, temporal-difference learning, and deep reinforcement learning.

Learning Objectives

By the end of this chapter, you should be able to:

1. Explain the roles of an agent and an environment.

2. Distinguish states from observations and actions from rewards.

3. Describe policies, trajectories, episodes, and returns.

4. Calculate discounted returns correctly.

5. Explain state-value and action-value functions.

6. Analyze delayed consequences and the credit-assignment problem.

7. Distinguish supervised, unsupervised, and reinforcement learning.

8. Apply the RL framework to a practical decision-making problem.

9. Identify important limitations, safety concerns, and design considerations.

1. The Reinforcement Learning Interaction

A reinforcement-learning system consists of an agent interacting repeatedly with an environment. At a decision time t:

• the agent receives information about the current situation;
• the agent selects an action according to a policy;
• the environment responds by producing a reward and a subsequent situation.

A common notation is:

\[

S_t \rightarrow A_t \rightarrow R_{t+1}, S_{t+1}.

\]

Here, \(S_t\) is the state at time \(t\), \(A_t\) is the action selected at time \(t\), \(R_{t+1}\) is the reward associated with the transition, and \(S_{t+1}\) is the next state. The indexing convention reflects that the action at time \(t\) causes the outcome observed after that action. Some texts use a slightly different reward index; consistency is more important than the particular convention.

The agent's objective is to maximize expected cumulative reward, not necessarily immediate reward. This distinction separates RL from simple reactive control.

Agent

The agent is the decision-making entity. It may be a software program, robot, autonomous vehicle, trading system, or controller. The agent contains or implements a policy and may also maintain estimates of values, transition behavior, or uncertainty.

The phrase “the agent selects actions according to a policy” is precise: the policy specifies how actions are selected from available information. In a deterministic policy, one action is selected for each relevant state; in a stochastic policy, the policy assigns probabilities to possible actions.

Environment

The environment is everything outside the agent that responds to its actions. It includes physical surroundings, users, other agents, data-generating processes, and operational constraints. The environment may be deterministic or stochastic, fully or partially observable, and stationary or changing over time.

A useful boundary must be defined. For example, in an autonomous driving system, the vehicle controller may be the agent, while roads, traffic, weather, pedestrians, and other vehicles form part of the environment. Sensors and actuators sit at the interface between them.

State

A state is a representation of the relevant situation at a particular time. In a Markov model, the state contains sufficient information about the past for predicting future outcomes, given the current action. Formally, the Markov property can be expressed as:

\[

P(S_{t+1},R_{t+1}\mid S_t,A_t,S_{t-1},A_{t-1},\ldots)

= P(S_{t+1},R_{t+1}\mid S_t,A_t).

\]

This equation is a modeling assumption or property of the chosen state representation. Real systems may not naturally satisfy it, but a history summary, recurrent model, or engineered state can sometimes approximate it.

A state should include information relevant to decision-making while avoiding unnecessary complexity. For a warehouse robot, a state might include its position, battery level, carrying status, nearby obstacles, and outstanding delivery requests.

Observation

An observation is the information actually available to the agent. In a fully observable environment, the observation may equal the true state. In a partially observable environment, the agent receives only an incomplete or noisy view.

For example, a robot may observe camera pixels and lidar readings but not the exact intentions of pedestrians. The agent may maintain a belief about possible states or use a memory-based policy. Confusing observation with state can lead to unrealistic algorithms that assume access to information unavailable at deployment.

Action

An action is a choice available to the agent. Actions can be discrete, such as “move left,” “move right,” or “wait,” or continuous, such as setting a motor torque or steering angle. The action set may depend on the state because some actions may be unsafe or infeasible.

Action design is an engineering decision. A very coarse action space may prevent effective control, while an excessively large action space may make learning inefficient. Safety constraints should be represented explicitly rather than left entirely to trial and error.

Reward

A reward is a numerical signal supplied by the environment after an interaction. It evaluates the immediate consequence of an action from the perspective of the learning objective. Rewards can be positive, negative, or zero.

A reward is not necessarily the same as a raw measurement. For instance, an energy-management system may convert energy cost, comfort deviation, and equipment stress into a scalar reward. Reward design therefore expresses priorities and can create unintended incentives if poorly specified.

The objective is generally written as maximizing expected return. A reward of 10 followed by a reward of -20 may be preferable or inferior to another sequence depending on timing, discounting, and the decision horizon.

2. Policies, Trajectories, and Episodes

Policy

A policy, denoted by \(\pi\), specifies action selection. For a stochastic policy,

\[

\pi(a\mid s)=P(A_t=a\mid S_t=s).

\]

Thus, \(\pi(a\mid s)\) is the probability of selecting action \(a\) when the agent is in state \(s\). A deterministic policy can be written as \(a=\pi(s)\). Policies may instead condition on observations or histories when the true state is unavailable.

A policy is not the same as a value function. The policy determines what the agent does; a value function estimates how desirable a state or action is under a specified policy.

Trajectory

A trajectory, also called a rollout, is a sequence such as

\[

S_0,A_0,R_1,S_1,A_1,R_2,S_2,\ldots.

\]

It records the agent's experience. Data collected from trajectories may be used to estimate rewards, values, transition dynamics, or policy performance.

Episode and continuing tasks

An episodic task has a terminal condition. An episode begins at an initial state and ends when the agent reaches a goal, fails, or reaches a time limit. Examples include completing a game or delivering a package.

A continuing task has no natural terminal state, such as regulating temperature in a building. Continuing tasks require a discount factor, an average-reward objective, or another method for defining long-term performance. A time limit imposed for computational convenience should not automatically be interpreted as a true terminal state.

3. Returns and Discounting

The return is the cumulative reward used to evaluate an outcome. For an episodic task with a finite horizon, the undiscounted return from time \(t\) is

\[

G_t=R_{t+1}+R_{t+2}+\cdots+R_T,

\]

where \(T\) is the final reward index. For continuing or long-horizon tasks, the discounted return is

\[

G_t=\sum_{k=0}^{\infty}\gamma^kR_{t+k+1},

\]

where \(0\leq\gamma<1\) is the discount factor. In a finite episode, the sum terminates at the end of the episode.

The discount factor determines how strongly future rewards influence present decisions. A value near zero emphasizes immediate rewards; a value near one gives greater weight to delayed rewards. Discounting can also ensure that an infinite sum is finite when rewards are bounded. It does not mean that future rewards are unimportant; it represents a modeling choice about time preference, uncertainty, or planning horizon.

Worked example: discounted return

Suppose the rewards following time \(t\) are:

\[

R_{t+1}=2,\qquad R_{t+2}=0,\qquad R_{t+3}=5,

\]

and \(\gamma=0.9\). The return is

\[

G_t=2+0.9(0)+0.9^2(5).

\]

Because \(0.9^2=0.81\),

\[

G_t=2+0+0.81(5)=2+4.05=6.05.

\]

The third reward contributes 4.05 after discounting. This example illustrates why delayed rewards must be weighted according to their temporal distance from the current decision.

4. Value Functions

Value functions predict expected returns. They are expectations because future rewards may depend on stochastic transitions and stochastic action selection.

State-value function

The state-value function for policy \(\pi\) is

\[

V^\pi(s)=\mathbb{E}_\pi[G_t\mid S_t=s].

\]

It measures the expected return when the agent starts in state \(s\) and subsequently follows policy \(\pi\).

Action-value function

The action-value function is

\[

Q^\pi(s,a)=\mathbb{E}_\pi[G_t\mid S_t=s,A_t=a].

\]

It measures the expected return when the agent first takes action \(a\) in state \(s\), then follows policy \(\pi\).

For a policy that chooses actions according to \(\pi\), the two functions are related by

\[

V^\pi(s)=\sum_a\pi(a\mid s)Q^\pi(s,a)

\]

for discrete actions. For continuous actions, the sum is replaced by an integral when the distribution has a suitable density.

Bellman expectation equations

The return can be decomposed into the immediate reward plus the discounted return from the next state:

\[

G_t=R_{t+1}+\gamma G_{t+1}.

\]

Taking conditional expectations gives the Bellman expectation equation:

\[

V^\pi(s)=\mathbb{E}_\pi[R_{t+1}+\gamma V^\pi(S_{t+1})\mid S_t=s].

\]

For a known transition and reward model, this equation supports dynamic programming. It is not a claim that the next state is deterministic; the expectation accounts for uncertainty.

The optimal value functions are defined by the best achievable expected return:

\[

V^*(s)=\max_\pi V^\pi(s),

\qquad

Q^*(s,a)=\max_\pi Q^\pi(s,a).

\]

Under standard finite Markov decision process assumptions, an optimal deterministic policy can be selected by choosing an action with maximal optimal action value. Ties may permit multiple optimal policies.

5. Delayed Consequences and Credit Assignment

A central difficulty in RL is delayed consequence. An action may not receive informative feedback until many steps later. The algorithm must determine which earlier actions contributed to a later outcome. This is called the credit-assignment problem.

Consider a robot that makes ten navigation decisions before reaching a destination. If the final reward is positive, the learning system must estimate how the entire sequence contributed to success. Immediate rewards can make learning easier, but designing them may be difficult. Sparse rewards provide less frequent feedback and may cause slow exploration.

Delayed consequences also create temporal trade-offs. An action that reduces current reward may enable a larger future reward. For example, a battery-powered robot may spend energy detouring around an obstacle in order to reach a high-value destination. A purely greedy strategy that maximizes immediate reward can fail because it ignores future states.

Exploration and exploitation are closely related. Exploitation chooses actions currently believed to be good; exploration gathers information about uncertain actions. A deployed system must balance learning with safety, cost, and reliability. Random exploration that is acceptable in a simulation may be unacceptable for a medical device or physical robot.

6. Comparing Learning Paradigms

Supervised learning

Supervised learning uses labeled examples, typically pairs \((x,y)\), to learn a mapping from inputs to target outputs. A classification model may learn from images labeled “cat” or “dog.” The training objective directly compares predictions with supplied labels.

In RL, the correct action is generally not supplied for every state. Instead, the agent receives rewards resulting from its decisions. The learning problem includes both action selection and evaluation of consequences.

Unsupervised learning

Unsupervised learning seeks structure in data without externally supplied target labels. Clustering, dimensionality reduction, and density estimation are examples. The learner may discover regularities, but it is not necessarily making sequential decisions to maximize reward.

Unsupervised representation learning can support RL by producing compact features from high-dimensional observations. It does not replace the policy-learning objective.

Reinforcement learning

RL uses interaction, feedback, and an objective defined over cumulative consequences. The data distribution is often affected by the current policy, making RL data-dependent and non-stationary from the learner's perspective. Exploration is necessary when the agent does not know which actions are valuable.

The paradigms can be combined. Demonstrations can provide supervised pretraining, unsupervised methods can learn representations, and RL can optimize sequential behavior after deployment or simulation training.

7. Formal Framework: The Markov Decision Process

A finite Markov decision process (MDP) is commonly represented by

\[

(\mathcal{S},\mathcal{A},P,R,\gamma),

\]

where:

• \(\mathcal{S}\) is the state space;
• \(\mathcal{A}\) is the action space;
• \(P(s'\mid s,a)\) is the transition probability;
• \(R(s,a,s')\) or an equivalent reward specification defines reward behavior;
• \(\gamma\) is the discount factor.

The MDP assumes that the chosen state satisfies the Markov property. It also assumes that the relevant dynamics can be represented through the specified transition and reward mechanisms. Real applications may violate these assumptions because of hidden variables, changing users, unmodeled disturbances, or strategic competitors.

An MDP provides a useful abstraction, not a guarantee that the world is simple. Model selection determines what information is treated as state and what uncertainty is left to the learning algorithm.

8. Illustrative Case: Learning to Manage a Warehouse Robot

Background

A logistics company operates mobile robots that carry containers between storage locations and packing stations. Each robot has limited battery capacity and shares narrow aisles with other robots.

Problem

The company wants to reduce delivery time while avoiding collisions, congestion, and excessive battery depletion. A shortest-path policy may be fast in isolation but can create congestion when many robots choose the same route.

RL formulation

The agent is the route-planning controller for one robot. Observations include the robot's location, battery estimate, container status, nearby occupancy, and current task. A carefully engineered state representation may include predicted congestion and a limited history of observations. Actions might be selecting the next aisle, waiting, recharging, or requesting an alternative task.

Rewards could combine delivery progress, time cost, energy cost, and severe penalties for unsafe behavior. For example, a transition reward might be conceptually structured as

\[

R=r_{progress}-c_{time}-c_{energy}-c_{risk},

\]

where each term must be calibrated in consistent utility units. This expression is a design template rather than a universal formula. A large safety penalty should not be assumed to compensate automatically for every possible unsafe sequence.

Analysis and approach

The problem is episodic if an episode ends when a delivery is completed, the robot fails, or a planning horizon expires. It is continuing if the controller operates indefinitely across tasks. Simulation can provide safer exploration than direct experimentation in the warehouse. Demonstration data from experienced dispatchers may initialize the policy, while RL can improve performance under simulated congestion.

The design team should compare the learned policy with shortest-path and rule-based baselines. Evaluation should include average delivery time, energy use, collision rate, near-miss rate, task completion, and performance under previously unseen demand patterns.

Outcome

An effective policy may accept a small immediate delay to avoid a congested aisle, producing better long-term throughput. However, a high average reward alone is insufficient if rare unsafe events are unacceptable. Deployment should therefore use action constraints, monitoring, fallback control, and staged rollout.

Learning points

1. The state must include information relevant to future congestion and safety.

2. Reward design determines which operational priorities the agent learns.

3. Simulation can reduce the cost and risk of exploration but may produce a reality gap.

4. Evaluation requires safety and robustness metrics, not only cumulative reward.

5. Human oversight and fallback behavior remain important in physical systems.

9. Challenges, Limitations, and Responsible Practice

Reward misspecification

An agent optimizes the reward that is implemented, not the intention behind it. If delivery speed is rewarded without adequate safety terms, the system may take dangerous shortcuts. Rewards should be tested against adversarial and edge-case behavior.

Sample inefficiency

Many RL algorithms require large amounts of interaction data. Data collection may be expensive, slow, or dangerous. Model-based planning, demonstrations, offline datasets, simulation, and representation learning can reduce this burden, but each introduces assumptions and possible biases.

Distribution shift

A policy trained under one traffic pattern, customer population, or weather condition may fail under another. Evaluation should include stress tests and conditions outside the training distribution.

Partial observability and non-stationarity

Hidden state and changing environments can make a fixed policy unreliable. Memory, belief-state modeling, online adaptation, or periodic retraining may be needed. Retraining must be governed carefully so that updates do not silently reduce safety.

Ethical and governance issues

RL systems can affect access to services, prices, healthcare decisions, employment, and physical safety. Designers should document objectives, data sources, constraints, monitoring procedures, and known failure modes. Sensitive applications require accountability, privacy protection, fairness analysis, auditability, and human override mechanisms. Reward signals should not encode discriminatory or legally prohibited outcomes.

Best practices

A professional RL development process should:

• define the agent-environment boundary explicitly;
• distinguish observable information from hidden state;
• establish safety constraints before training;
• use interpretable baselines and offline evaluation;
• test reward functions for unintended strategies;
• monitor rare events and tail risks;
• use simulation with validation against real data;
• deploy incrementally with rollback and fallback procedures;
• report uncertainty and limitations rather than only mean reward.

10. Contemporary Directions

Modern RL increasingly combines deep neural networks with value estimation or policy optimization, enabling learning from images, language, and complex sensor streams. Offline RL learns from previously collected interaction data and is valuable when online exploration is unsafe or expensive. Model-based RL learns or uses an environment model for planning. Multi-agent RL studies settings in which several decision-makers interact, often creating non-stationary learning problems.

Large foundation models can provide representations, planning proposals, or interfaces to tools, but their inclusion does not eliminate the need for explicit reward design, evaluation, and safety constraints. A sophisticated model remains an RL system only when its behavior is optimized or adapted through an appropriate sequential decision objective.

Chapter Summary

Reinforcement learning studies how an agent learns sequential decisions through interaction with an environment. The agent selects actions according to a policy, receives rewards, and experiences new states or observations. States represent decision-relevant situations; observations are the information actually available. A trajectory records interaction, while an episode is a bounded task sequence.

The return aggregates immediate and future rewards. Discounted returns use a factor \(\gamma\) to weight delayed outcomes, and value functions estimate expected returns under a policy. The state-value function evaluates states, while the action-value function evaluates state-action choices. Bellman equations express the recursive relationship between immediate reward and future value.

RL differs from supervised learning because correct actions are not supplied for every situation, and from unsupervised learning because its objective concerns sequential reward. MDPs provide a formal framework under the Markov assumption. Practical RL must address delayed consequences, exploration, reward misspecification, partial observability, data efficiency, safety, fairness, and distribution shift.

Key Terms

Agent: The entity that selects actions and learns from interaction.

Environment: The external system that responds to the agent's actions.

State: A representation of the situation relevant to predicting future outcomes.

Observation: Information actually available to the agent.

Action: A decision or control input selected by the agent.

Reward: Numerical feedback associated with an interaction.

Policy: A rule or probability distribution specifying action selection.

Trajectory: A sequence of states, actions, and rewards.

Episode: A task interaction with an identifiable beginning and termination.

Return: Cumulative reward from a specified time onward.

Discount factor: A parameter controlling the weight of future rewards.

State-value function: Expected return from a state under a policy.

Action-value function: Expected return after taking an action in a state and following a policy thereafter.

Markov property: The condition that the current state contains sufficient predictive information about the future.

Markov decision process: A formal model consisting of states, actions, transitions, rewards, and discounting.

Exploration: Selecting actions to gain information.

Exploitation: Selecting actions believed to produce high return.

Credit-assignment problem: The challenge of linking delayed outcomes to earlier decisions.

Reward misspecification: A mismatch between the implemented reward and the intended objective.

Partial observability: A condition in which the agent cannot directly access the complete underlying state.

Review Questions

Short Answer Questions

1. What roles do the agent and environment play in an RL interaction?

2. Distinguish a state from an observation.

3. Define a policy and explain how a stochastic policy differs from a deterministic policy.

4. What is the purpose of the discount factor?

5. Distinguish the state-value function from the action-value function.

Long Answer Questions

1. Explain the RL interaction cycle using the notation \(S_t,A_t,R_{t+1},S_{t+1}\), and discuss why the timing convention matters.

2. Compare supervised, unsupervised, and reinforcement learning in terms of data, feedback, objectives, and typical applications.

3. Explain the Markov property and discuss why it may be difficult to satisfy in a real-world application.

4. Derive the Bellman expectation equation from the definition of discounted return.

5. Discuss reward misspecification, exploration, and safety in the design of an RL system.

Analytical / Application Questions

1. Design an MDP formulation for elevator control. Specify the agent, environment, state or observation, actions, rewards, and a possible terminal condition.

2. An online recommendation agent receives immediate clicks but may reduce long-term user satisfaction. Analyze how reward design and discounting could produce undesirable behavior, and propose evaluation measures.

3. A robot receives a final positive reward only when it reaches a destination. Analyze the credit-assignment and exploration difficulties, then recommend at least three methods for improving learning safely.

Multiple Choice Questions with Answers

Question 1

Which statement most precisely describes a policy in reinforcement learning?

A. It specifies how actions are selected given available information.

B. It records only the rewards produced by the environment.

C. It is the complete physical environment surrounding the agent.

D. It guarantees the highest possible return in every stochastic task.

Correct Answer: A. It specifies how actions are selected given available information.

Question 2

What is the main distinction between a state and an observation?

A. A state is always numerical, whereas an observation is always visual.

B. A state is the underlying decision-relevant situation, whereas an observation is information available to the agent.

C. A state is selected by the agent, whereas an observation is selected by the reward function.

D. A state occurs after an action, whereas an observation can occur only before an action.

Correct Answer: B. A state is the underlying decision-relevant situation, whereas an observation is information available to the agent.

Question 3

If rewards after time t are 2, 0, and 5, and the discount factor is 0.9, what is the discounted return?

A. 6.05

B. 7.00

C. 6.50

D. 5.45

Correct Answer: A. 6.05

Question 4

Which expression defines the state-value function for policy π?

A. The probability of selecting action a in state s

B. The immediate reward received after every action in state s

C. The expected return given that the agent is in state s and follows π

D. The maximum possible reward in the entire environment

Correct Answer: C. The expected return given that the agent is in state s and follows π

Question 5

What is the credit-assignment problem?

A. Choosing a numerical data type for rewards

B. Determining which earlier actions contributed to a delayed outcome

C. Converting observations into pixels

D. Ensuring that all actions have identical probabilities

Correct Answer: B. Determining which earlier actions contributed to a delayed outcome

Question 6

Which characteristic is most associated with supervised learning rather than reinforcement learning?

A. Learning from explicit target labels for training examples

B. Receiving feedback after actions in a sequential environment

C. Balancing exploration and exploitation

D. Optimizing cumulative consequences over time

Correct Answer: A. Learning from explicit target labels for training examples

Question 7

For a stochastic policy, what does π(a|s) represent?

A. The reward received in state s

B. The probability of selecting action a given state s

C. The probability that state s is terminal

D. The discounted value of state s under every policy

Correct Answer: B. The probability of selecting action a given state s

Question 8

Which condition is required for the standard Markov property?

A. The environment must provide only positive rewards.

B. The agent must use a deterministic policy.

C. The current state must contain sufficient information for predicting the future given the current action.

D. Every episode must have exactly the same length.

Correct Answer: C. The current state must contain sufficient information for predicting the future given the current action.

Question 9

Which statement best describes exploitation?

A. Selecting actions currently believed to yield high return

B. Selecting random actions solely to discover unknown outcomes

C. Removing the reward signal from the environment

D. Replacing the policy with an unsupervised clustering algorithm

Correct Answer: A. Selecting actions currently believed to yield high return

Question 10

A warehouse robot is rewarded only for delivery speed and not for collision avoidance. What is the most likely design risk?

A. The policy may learn unsafe shortcuts that increase speed.

B. The environment automatically becomes fully observable.

C. The discount factor becomes equal to one.

D. The state-value function becomes identical to the policy.

Correct Answer: A. The policy may learn unsafe shortcuts that increase speed.