BAI701- Deep Learning and Reinforcement Learning

Module – 5 Notes (Deep Reinforcement Learning)

Stateless algorithms in Reinforcement Learning - Focusing on the Multi-

Armed Bandit problem and its significance:

Stateless Algorithms in Reinforcement Learning

• Stateless algorithms are a simplified form of reinforcement learning where the

environment does not change as a result of the agent’s actions, and every trial
yields rewards drawn from the same probabilistic distribution.

• There is no notion of state—the outcome of an action is independent of past actions.

These algorithms are foundational because they introduce key RL concepts like
exploration vs. exploitation in a simplified setting.

The Multi-Armed Bandit Problem:

The multi-armed bandit (MAB) is a classical example of a stateless RL problem:

• Imagine a gambler in a casino with several slot machines (“arms”).
• Each machine has an unknown probability distribution of rewards.
• The gambler’s goal is to maximize total reward over multiple plays by balancing:
1. Exploration: Trying different slot machines to learn their reward probabilities.
2. Exploitation: Playing the slot machine that seems to give the highest reward
based on past trials.
Key idea:
Unlike general RL problems, each trial is independent. There’s no state dependency,
meaning the reward from an arm does not depend on previous plays or sequences of
actions.

Strategies for Solving the Multi-Armed Bandit

1. Naïve Algorithm
• Method: Play each machine a fixed number of times to estimate rewards, then
always pick the machine with the highest average payoff.
• Drawbacks:
o Hard to determine the optimal number of exploratory trials.
o Wastes effort on suboptimal machines if too many exploratory trials are used.
o May select the wrong machine permanently if the initial estimate is wrong.
o

1
2. ǫ-Greedy Algorithm
• Method:
o With probability 1 − 𝜖, pick the best-performing machine so far
(exploitation).
o With probability 𝜖, pick a random machine (exploration).

• Advantages:
o Avoids being stuck forever on the wrong machine.
o Exploitation starts early, increasing expected reward over time.
• Tuning:
o 𝜖is usually small (e.g., 0.1).
o Annealing can be used: start with a large 𝜖for more exploration, gradually
reduce it over time.

3. Upper Confidence Bound (UCB) Methods

• Method: Select the machine with the highest upper confidence bound on its reward
rather than just the mean reward:
𝑈𝑖 = 𝑄𝑖 + 𝐶𝑖
Where:
• 𝑄𝑖 = mean reward of machine 𝑖
• 𝐶𝑖 = confidence bonus based on uncertainty
• Rarely tried machines have higher 𝐶𝑖 , encouraging exploration.
• Advantages:
o Combines exploration and exploitation naturally in a single step.
o Adjustable confidence level (via parameter 𝐾) regulates the exploration-
exploitation trade-off.
Significance of Stateless Algorithms
1. Fundamental RL Concepts: Introduce exploration vs. exploitation, reward
estimation, and decision-making under uncertainty.
2. Building Blocks: Many advanced RL algorithms (including stateful RL) use these
stateless strategies as subroutines for action selection.
3. Simplicity: They are computationally simpler because there’s no need to maintain or
reason about states.
4. Insight into Learning Dynamics: Understanding how an agent balances exploration
and exploitation in stateless problems helps in designing algorithms for complex,
state-dependent RL tasks.

So,
• Stateless RL algorithms like multi-armed bandits are the simplest RL problems.
• They focus on optimizing actions with no state dependency, primarily illustrating
how to explore and exploit effectively.
• Methods like ǫ-greedy and UCB provide systematic strategies to learn optimal
actions over time, laying the foundation for more complex RL algorithms.

2
The Basic Framework of Reinforcement Learning:
Basic Framework of Reinforcement Learning

Reinforcement Learning (RL) is a framework in which an agent interacts with an

environment through actions, observes the resulting state transitions, and receives rewards
based on its behavior. Unlike stateless bandit problems, RL explicitly models states, because
rewards depend not only on the current action but also on the entire sequence of past
actions.

Key Components
• Agent → chooses an action 𝑎𝑡
• Environment → receives the action, gives reward 𝑟𝑡 , and transitions from state 𝑠𝑡 to
𝑠𝑡+1
• Reward → depends on how well the agent’s goals are met
• State → full description of the environment at a specific time

State–Action Interaction
• The same action may produce different rewards depending on the state.
Example: A sudden swerve in a car is bad in normal driving but good when avoiding a
collision.

Markov Decision Process (MDP)

• RL systems are modeled as MDPs, where the current state contains all required
information for future transitions.
• Finite MDPs have episodes (e.g., tic-tac-toe).
• Non-episodic MDPs (e.g., robots) run indefinitely.
• A full episode of length 𝑛 + 1is written as:
𝑠0 𝑎0 𝑟0 𝑠1 𝑎1 𝑟1 … 𝑠𝑛 𝑎𝑛 𝑟𝑛

Examples of RL Settings
1. Tic-tac-toe / Chess / Go:
State = board position; reward given at the end.
2. Robot locomotion:
State = joint positions; reward based on movement and balance.
3. Self-driving cars:
State = sensor inputs; reward based on safety and progress.

Challenges of Reinforcement Learning

The text outlines four major challenges:
1. Credit-Assignment Problem
• Rewards often occur long after the valuable action was performed.
• Contribution of each action to final reward is unclear.
• Rewards can also be stochastic (e.g., slot machines).

3
2. Huge State Spaces

• Many RL tasks (like chess) have enormously large state spaces.

• The system must generalize to unseen states, requiring strong models.

3. Exploration vs Exploitation
• Exploring new actions may be costly.
• Exploitation (using known actions) may miss better long-term strategies.
• RL must balance both.

4. Data Collection is Difficult

• Real-world RL (robots, cars) requires physical interactions.
• Failures are dangerous and early training may produce few successes.
• Lack of real-world data limits learning.

Role of Deep Learning in Reinforcement Learning:

Traditional RL stores values of all state–action pairs in tables (e.g., tic-tac-toe).

This fails in large state spaces (e.g., chess, video games).

Why Deep Learning is Needed

• State spaces are too large to tabulate.
• Deep networks act as function approximators.
• They map state → value or state → action.
• They generalize knowledge to new, unseen states, just like humans.

Example from the Text:

• Alpha Zero evaluates board positions using a neural network instead of a table.
• It learns complex patterns like:
o long-term strategic traps,
o sacrifice-based positional advantages,
o subtle spatial patterns in chess.
• Deep learning extracts meaningful features even from raw sensory inputs (pixels)

4
How reinforcement learning is useful in at least one of the following domains:

Go, robotics, conversational systems, self-driving cars, or hyperparameter

learning.

1. Go (Board Games)
• Problem: Go has a 19×19 board, a huge number of possible moves (~250 per turn),
and long game sequences (~150 moves). Traditional brute-force methods (like chess
engines) are infeasible.

• RL Solution:
o AlphaGo and AlphaZero use policy networks to predict the best moves and
value networks to estimate the probability of winning from a given board
state.
o Self-play enables the system to improve without human knowledge.
o Monte Carlo Tree Search (MCTS) explores promising moves guided by the
networks.
• Benefit: RL allows the system to learn strategies and innovate moves, often
surpassing human expertise, without explicitly programming Go rules for all
situations.

5
2. Robotics
• Problem: Robots must learn complex physical tasks like walking, grasping, or
screwing a cap. Defining exact rules for all actions and situations is almost
impossible.
• RL Solution:
o The robot performs actions and receives rewards for achieving goals (e.g.,
moving forward, completing a manipulation task).
o Convolutional neural networks process visual input for tasks involving objects.
o Actor-critic methods, policy gradients, and guided policy search are used to
optimize actions.
• Benefit: RL enables robots to learn precise sequences of movements autonomously,
adapt to new terrains, and handle high-dimensional inputs like camera images and
joint sensors.

3. Conversational Systems (Chatbots):

• Problem: Building agents that negotiate, answer questions, or converse naturally.
Human language is unpredictable, and hard-coded rules are insufficient.
• RL Solution:
o Dialogue agents use policy networks (GRUs or LSTMs) to choose utterances
that maximize expected rewards (e.g., successful negotiation or task
completion).
o Self-play or simulated dialogues allow the agent to explore strategies and
optimize communication.
o Combined with supervised learning to prevent language from diverging from
human norms.
• Benefit: RL allows chatbots to adapt strategies, learn persistent negotiation tactics,
and improve decision-making in interactive tasks.

4. Self-Driving Cars
• Problem: Driving involves complex, dynamic environments. Defining exact rules for
every situation is impossible.
• RL Solution:
o Cars receive rewards for safe and efficient driving, and penalties for collisions
or unsafe behavior.
o Neural networks process sensor data (e.g., camera images) to predict steering
or acceleration.
o Imitation learning (supervised learning from human drivers) is often
combined with RL to improve initial performance.
• Benefit: RL enables vehicles to learn safe driving policies in diverse conditions,
including unseen environments, without explicitly coding every possible driving
scenario.

6
 4. Hyperparameter / Neural Architecture Learning

• Problem: Designing neural network architectures manually is complex due to

interdependent hyperparameters (layers, filters, strides).
• RL Solution:
o A controller network (policy network) proposes architectures.
o The child network is trained with the proposed architecture, and its
performance (accuracy) generates a reward signal.
o The controller network is updated via policy gradients (REINFORCE) to
improve the architectures it proposes.
• Benefit: RL automates the design of neural networks, finding architectures that
maximize performance, which is otherwise expensive and time-consuming for
humans to optimize manually.
So,
• Reinforcement learning is useful in these domains because it allows systems to learn
optimal actions from feedback (rewards) in environments that are too complex for
explicit programming.

• RL is especially powerful where trial-and-error, self-play, or simulation can generate

experiences to improve performance over time.