RL @ ECE-UofT - Lecture 08: Deep SARSA and DQL
Overview
Ali Bereyhi develops deep control methods by replacing tabular action values with neural networks, first extending SARSA and Q-learning, then addressing DQN’s instability with experience replay and a separate target network. He also explains how the maximum operator can overestimate action values, introduces Double Q-learning’s split between action selection and value evaluation, and motivates policy-gradient and actor-critic methods for continuous actions.
Key takeaways
- Deep SARSA uses the Q value of the next action actually selected by the epsilon-greedy policy, whereas deep Q-learning targets the maximum next-state action value.
- Experience replay stores state-action-reward-next-state transitions and samples them randomly in mini-batches, reducing temporal correlation and allowing the same experience to support repeated updates.
- DQN stabilizes bootstrapped learning by holding a separate target network fixed for H training rounds, then periodically copying the online network’s weights into it.
- The maximum over noisy Q estimates can be systematically optimistic; Double Q-learning reduces this effect by using one estimator to choose an action and another to evaluate it.
- A biased estimate of every action value does not necessarily produce a poor policy, but action-dependent bias can change the ranking of actions and lead to suboptimal choices.
- Standard DQN requires a finite set of actions because it outputs one Q value per action; continuous-control problems motivate policy networks and actor-critic methods.
Chapters
- Monte Carlo and temporal-difference methods work naturally when the state and action tables are manageable.
- When state spaces grow too large to enumerate, a neural network can approximate the value function from state features.
- The previous lecture focused on prediction, evaluating a fixed policy; this lecture moves to control, improving the policy through interaction.
- A control loop alternates between sampling experience, updating value estimates, and improving the policy.
- A greedy policy chooses the action with the highest estimated value, while epsilon-greedy exploration sometimes selects an action at random.
- Exploration reduces the chance that early, inaccurate estimates lock the agent into a poor policy.
- The tabular Q update is replaced by a gradient update to the weights of a function approximator.
- Stochastic gradient descent uses sampled environment experience to adjust the model toward better action-value estimates.
- The input is a feature representation of the state, rather than necessarily the raw state itself.
- A Q network maps state features to a vector containing one estimated action value for each available action.
- A robot with four movement choices can use four output values, and the greedy action is the output with the largest estimate.
- A network taking a state-action pair and returning one scalar is possible, but a vector output makes discrete-action maximization convenient.
- For a computer game, the state can be represented by a screen image or a stack of recent frames that captures motion.
- A convolutional neural network can process the image-like input and produce one output per legal game action.
- If a game has 10 individual key actions and 45 two-key combinations, the output head would need to represent 55 actions.
- SARSA is the representative on-policy control algorithm, while Q-learning is the representative off-policy algorithm.
- Both can replace the Q table with a neural network, but Q-learning is more commonly used in deep value-based control.
- Off-policy learning supports experience replay because stored transitions can be reused even when collected under older behavior policies.
- A value network may estimate a state value V or a vector of action values Q; DQN is a value-based approach.
- A policy network instead maps state features to action probabilities or an action choice.
- Policy-gradient methods, including PPO, optimize the policy network directly and become the focus of later lectures.
- For a fixed policy, a sampled TD target combines the immediate reward with a discounted estimate of the next state’s value.
- The TD error compares that target with the network’s current estimate for the state-action pair.
- With function approximation, the update scales the TD error by the gradient of the Q network with respect to its weights.
- SARSA’s next-state target uses the value of the next action selected by the current behavior policy, rather than the maximum over actions.
- With epsilon-greedy behavior, the agent selects the next action after observing the next state and uses that action’s Q estimate.
- This on-policy target evaluates the actions the agent actually takes, including exploratory actions.
- A sampled transition contains the current state and action, the reward, the next state, and the next action selected by epsilon-greedy behavior.
- The target is the immediate reward plus the discounted Q estimate for that sampled next action.
- Each transition produces a TD error that updates the network weights through the action-value gradient.
- Eligibility traces accumulate gradients across recent state-action visits instead of using only the current gradient.
- The trace decays using the product of lambda and gamma, then scales the TD-error update to the network weights.
- Bereyhi relates this accumulated gradient to momentum in gradient descent, while emphasizing that it is an eligibility-based update.
- Q-learning samples actions using an epsilon-greedy behavior policy but updates toward the greedy target policy.
- Its one-step target is the immediate reward plus the discounted maximum action value at the next state.
- This off-policy distinction is what allows Q-learning to reuse transitions gathered under different behavior policies.
- The Q-learning update changes network weights by multiplying the TD error by the gradient of the selected state-action output.
- Computing the next-state maximum requires a forward pass; computing the weight update requires backpropagation.
- The lecture describes a one-forward, one-backward update, with cached forward results potentially reused on the following step.
- Consecutive states in a trajectory are often strongly correlated, such as nearby positions of the Mountain Car agent.
- Updating from adjacent samples can overfit the network to a narrow region of the state space.
- A single-sample gradient also has high variance, motivating updates from batches of more diverse experience.
- An off-policy replay buffer stores transitions as state, action, reward, and next state.
- Randomly drawing stored transitions for training mixes samples from different times and trajectories instead of using only adjacent states.
- Replay improves sample efficiency by letting the agent reuse previously collected experience for multiple gradient updates.
- A mini-batch contains multiple independently sampled transitions, each with its own next-state estimate and TD error.
- The gradients from the batch are averaged to form a less noisy update than a single transition provides.
- The next state is used to construct the bootstrapped target, while the network being fitted is evaluated at the transition’s current state and action.
- The agent first interacts with the environment using epsilon-greedy behavior and adds each transition to buffer D.
- Once enough experience has accumulated, the algorithm samples a mini-batch, computes target values and gradients, and updates the Q-network.
- A practical replay buffer has a fixed capacity; new transitions replace older ones when it fills.
- The basic bootstrapped label is the reward plus a discounted maximum Q value at the next state.
- If the same network generates the label and is updated to match it, changing its weights also changes the target.
- The result is a moving target: the network is trying to catch a reference that shifts during training.
- DQN copies the online network weights into a target network, written as a separate set of parameters.
- The target network stays fixed for H rounds while the online network learns from replay-buffer mini-batches.
- After H rounds, the updated online weights are copied into the target network, refreshing the bootstrapped labels periodically.
- The DQN training loop combines epsilon-greedy environment sampling, replay-buffer storage, mini-batch updates, and periodic target-network copies.
- The target network supplies next-state estimates, while gradients update the online network.
- The interval H controls how often the target is refreshed and must be chosen to balance stability and responsiveness.
- The DeepMind team’s 2015 work showed that a deep Q-network could learn Atari games from visual input and reach or exceed human-level scores on some games.
- The result combined neural function approximation with replay and a target network, techniques that made deep Q-learning practical.
- Bereyhi identifies the paper as a major turning point that helped convince researchers deep reinforcement learning could work.
- Experiments on games such as Alien, Space Invaders, and Time Pilot found learned Q values could remain systematically above estimated true values.
- A constant shift in all action values does not necessarily change the greedy policy, but unequal errors across actions can select the wrong action.
- The maximum operator is a possible source of overestimation because it tends to select estimates with positive noise.
- Bereyhi compares two computers whose true runtimes are 8 seconds and 5 seconds, with measurement noise added to each observation.
- Selecting the largest noisy measurement among repeated samples tends to produce an estimate above the true maximum.
- Using one independent set of measurements to select the candidate and another to evaluate it reduces the selection bias.
- Double Q-learning uses one estimator to select the maximizing action and a separate estimator to evaluate that chosen action.
- In the neural-network version, the online network supplies the argmax action and the other network supplies its Q value for the target.
- This avoids using the same noisy maximum estimate for both selection and evaluation, reducing overestimation bias.
- The reported comparisons show Double DQN estimates closer to the reference action values than standard DQN in examples such as Space Invaders.
- Lower value-estimation bias does not automatically mean a better policy; policy improvement depends on whether errors change the ranking of actions.
- The lecture notes that reported performance gains varied by game, including improvements in Alien and Time Pilot.
- Prioritized replay samples transitions according to assigned priorities rather than uniformly, emphasizing selected experiences.
- Distributed DQN uses multiple actors or agents to gather experience from different parts of an environment and share updates.
- The Gorilla architecture is presented as an example of distributed deep Q-learning, with parallel experience collection and centralized learning.
- A standard Q-network outputs one value for every possible action, which is practical only when the action set is discrete and limited.
- A robot arm or autonomous vehicle has continuously varying controls such as joint angles, steering, and acceleration.
- Discretizing many continuous controls can produce an impractically large output layer, potentially with an enormous number of action combinations.
- A state-action Q network can evaluate one continuous action at a time, but Q-learning still needs to maximize over actions, which is difficult in a continuous space.
- A policy network can instead map the state directly to an action or an action distribution, using a Gaussian for continuous actions or softmax for discrete actions.
- Policy gradients train the policy using gradients of its likelihood; actor-critic methods pair an acting policy network with a critic that evaluates actions.
- Bereyhi previews policy-gradient methods and actor-critic learning, then recommends implementing examples to make the algorithms’ components concrete.
- DQN is most suitable when the action space is finite and small enough for the network to output all action values.
- Continuous-control applications such as robotics and autonomous driving motivate policy-based methods instead.
- The next topic is policy networks that sample actions from a learned distribution and use value estimates to improve the policy.
Transcript excerpt
0:00 estimate, right? Monte Carlo, temporal difference, these were the approaches and then we use them basically these two ideas along with the fact that the optimal policy is the one which has maximum action value and we tried to come up with different ideas. Basically the ideas which are more sample efficient, have less bias, and can work fine. And we ended up with a couple of techniques, but then we said this is going to help us up to a level. And that level is when you have the number of estates limited, but if the number of estates now grows significantly large, you cannot do it anymore because you cannot go over every single one, every single state, every single action, do that. Now, the idea was to go for function
0:47 approximation. And we talked last time before the reading week about the function approximation. The idea was there that you model your value function as a neural network. So, you have this neural network which is taking, for example, the state and then giving you the value of the state as the output. Now, you try to look at the environment, you sample from the environment, and you use those samples to train this model, right? That was the idea. We did not talk about the control yet. We just talked about talk about prediction. Evaluation of the policy. So, last time when we talked, we basically wanted to get the idea how we can use function approximation and we thought of a simple example. We have the policy, we want to know how it works. And then we start to
1:34 model the value of that policy using a neural network. Then we sample from the environment, we use those samples to update. All right, cool? You remember what we did last time,
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Ali Bereyhi.