Hot answers tagged

8 votes

Are Q-learning and SARSA the same when action selection is greedy?

If we write the pseudo-code for the SARSA algorithm we first initialise our hyper-parameters etc. and then initialise $S_t$, which we use to choose $A_t$ from our policy $\pi(a|s)$. Then for each $t$ ...
8 votes
Accepted

Is Q-learning only capable of learning a deterministic policy?

If we assume a tabular setting, then Q-learning converges to the optimal state-action value function, from which an optimal policy can be derived, provided a few conditions are met. In finite MDPs, ...
  • 35k
6 votes
Accepted

Can Q-learning be used in a POMDP?

The usual (as presented in Reinforcement Learning: An Introduction) $Q$-learning and SARSA algorithms use (and update) a function of a state $s$ and action $a$, $Q(s, a)$. These algorithms assume that ...
  • 35k
5 votes
Accepted

When do SARSA and Q-Learning converge to optimal Q values?

The true answers are 1 and 3. 1 is true because the required conditions for tabular Q-learning to converge is that each state action pair will be visited infinitely often, and Q-learning learns ...
5 votes

What is the difference between the $\epsilon$-greedy and softmax policies?

The $\epsilon$-greedy policy is a policy that chooses the best action (i.e. the action associated with the highest value) with probability $1-\epsilon \in [0, 1]$ and a random action with probability $...
  • 35k
5 votes
Accepted

How should I handle action selection in the terminal state when implementing SARSA?

The value $Q(s', ~\cdot~)$ should always be implemented to simply be equal to $0$ for any terminal state $s'$ (the dot instead of an action as second argument there indicates that what I just wrote ...
  • 9,519
4 votes
Accepted

Expected SARSA vs SARSA in "RL: An Introduction"

Why is the action selection random with Sarsa? A policy could be stochastic. In the case of SARSA, it is stochastic because of the use of $\epsilon$-greedy. Isn't it on-policy and therefore ϵ-...
  • 510
4 votes
Accepted

Is the optimal policy the one with the highest accumulative reward (Q-Learning vs SARSA)?

It is important to note that the graph shows reward received during training. This includes rewards due to exploratory moves, which sometimes involve the agent falling off the cliff, even if it has ...
  • 24.7k
4 votes
Accepted

How should I generate datasets for a SARSA agent when the environment is not simple?

I am wondering how to generate datasets when the environment is not as simple as a tic-tac-toe or a maze problem There is no difference in concept, which is why tic-tac-toe and maze problems are used ...
  • 24.7k
4 votes

How to determine if Q-learning has converged in practice?

A typical and practical way to measure the convergence to some solution (so not necessarily the optimal one!) of any numerical iterative algorithm (such as RL algorithms) is to check if the current ...
  • 35k
3 votes

What is meant by "two action selections" in SARSA?

In my view, the best way to understand these algorithms is to read the pseudocode (multiple times, if necessary!). Here's the pseudocode of Q-learning. Here's the pseudocode of SARSA. So, as you can ...
  • 35k
3 votes
Accepted

Is Expected SARSA an off-policy or on-policy algorithm?

Expected SARSA can be used either on-policy or off-policy. The policy that you use in the update step determines which it is. If the update step uses a different weighting for action choices than the ...
  • 24.7k
3 votes
Accepted

Do we need an explicit policy to sample $A'$ in order to compute the target in SARSA or Q-learning?

Q-learning uses an exploratory policy, derived from the current estimate of the $Q$ function, such as the $\epsilon$-greedy policy, to select the action $a$ from the current state $s$. After having ...
  • 35k
3 votes
Accepted

Understanding the n-step off-policy SARSA update

Multiplying the entire update by $\rho$ has the desirable property that experience affects $Q$ less when the behavior policy is unrelated to the target policy. In the extreme, if the trajectory taken ...
3 votes

Can we also estimate $V_{\pi}$ with SARSA?

What you suggest will work, the main restriction is needing to know $\pi$ fully in order to perform the conversion. If you know that you are going to be estimating $V_{\pi}$ from the start, and have a ...
  • 24.7k
2 votes
Accepted

Optimal RL function approximation for TicTacToe game

I think you can break this problem down into two parts to try and find the solution. 1. Can the neural network model the desired function? Take the tabular function you have learned in the exact ...
  • 24.7k
2 votes
Accepted

How to deal with the terminal state in SARSA in a multi-agent setting?

The SARSA update rule looks like: $$Q(S, A) \gets Q(S, A) + \alpha \left[ R + \gamma Q(S', A') \right].$$ Very similar, the $Q$-learning update rule looks like: $$Q(S, A) \gets Q(S, A) + \alpha \left[ ...
  • 9,519
2 votes

How should I handle action selection in the terminal state when implementing SARSA?

From the description of the algorithm you linked to, it says to 'repeat until s is terminal'. So one would end the episode at that point and your intuition holds. Practically, if one was ...
2 votes
Accepted

What is the relationship between the Q and V functions?

Can we say that $Q^\pi(s, a) = V^\pi(s)$ No. The correct relationship is this: $$V^\pi(s) = \sum_a \pi(a|s) Q^\pi(s, a)$$ or, if you have a deterministic policy $a = \pi(s)$ you can instead write: ...
  • 24.7k
2 votes
Accepted

What are the conditions for the convergence of SARSA to the optimal value function?

The paper Convergence Results for Single-Step On-Policy Reinforcement-Learning Algorithms by Satinder Singh et al. proves that SARSA(0), in the case of a tabular representation of the value functions, ...
  • 35k
2 votes
Accepted

Are we choosing the same action in every step in SARSA?

Do we only select one action at the very beginning and then we always choose the same action for each step? No. The pseudocode is clear on this, by using the word ...
  • 24.7k
2 votes
Accepted

Why are we choosing more than 1 action in SARSA?

Why are we choosing more than 1 action in SARSA? There is never a state where more than one action is chosen. The appearance of two Choose statements is an ...
  • 24.7k
2 votes

Why would SARSA diverge (but not Expected SARSA or Q-learning)?

I think a useful piece of information to answer this question is a representation of the safe and optimal policies that can be learned on the cliff grid world. SARSA learns the safe path while Q-...
2 votes

How are we calculating the average reward ($r(\pi)$) if the policy changes over time?

You are correct: to evaluate a policy, we need to fix it. We can temporarily fix it, just to evaluate it over a number of test cases. For a fair comparison, we should fix the start states and random ...
2 votes

Is the optimal policy the one with the highest accumulative reward (Q-Learning vs SARSA)?

Adding to Neil's reply, though the path shown is optimal, following the so-called 'optimal path' will often result in sub-optimal returns because the action selection in this problem is stochastic due ...
2 votes
Accepted

How to perform the back propagation step in Semi-gradient SARSA using a deep neural network?

If so, then would it be correct to take the gradient of this expression of $\hat{q}(S,A,w)$ with respect to the weights of the network Yes, your expression for $\hat{q}(S,A,w)$ looks correct for your ...
  • 24.7k
1 vote
Accepted

How is $Q(s', a')$ calculated in SARSA and Q-Learning?

It seems that your problem is that you think that we must know the true value of $Q(s', a')$ in order to perform the SARSA update. This is not the case! SARSA is a reinforcement learning algorithm, ...
  • 35k
1 vote

Are the two policies in SARSA for choosing an action the same?

For learning, it doesn't matter much how you choose the first action before starting the main loop. That is because the agent doesn't need to learn about transitions to the first state of an episode. ...
  • 24.7k
1 vote
Accepted

Intuitively, how does it make sense to take an action $A'$ when the environment already ended?

Intuitively, how does it make sense to take an action A' when the environment already ended? It doesn't make sense, in that nothing can happen once the agent reaches a terminal state. However, it is ...
  • 24.7k
1 vote
Accepted

Implementing SARSA for a 2-stage Markov Decision Process

In this game you can view end of an episode two ways: There is an implied, terminal, fourth state $s_4$ representing the end of the game. You could view the process as a continuous repeating one, ...
  • 24.7k

Only top scored, non community-wiki answers of a minimum length are eligible