Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

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$ ...
user avatar
7 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, ...
user avatar
  • 33.2k
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 ...
user avatar
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 ...
user avatar
  • 9,326
5 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 ...
user avatar
  • 33.2k
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 ϵ-...
user avatar
  • 490
4 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 $...
user avatar
  • 33.2k
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 ...
user avatar
  • 23.3k
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 ...
user avatar
  • 23.3k
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 ...
user avatar
  • 33.2k
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 ...
user avatar
  • 33.2k
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 ...
user avatar
  • 23.3k
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 ...
user avatar
  • 33.2k
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 ...
user avatar
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 ...
user avatar
  • 23.3k
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 ...
user avatar
  • 23.3k
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[ ...
user avatar
  • 9,326
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 ...
user avatar
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: ...
user avatar
  • 23.3k
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, ...
user avatar
  • 33.2k
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 ...
user avatar
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 ...
user avatar
  • 23.3k
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 ...
user avatar
  • 23.3k
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 ...
user avatar
1 vote
Accepted

Is it possible learning convergence is lost in Reinforcement Learning as the state space grows?

With tabular reinforcement learning (RL) methods, then catastrophic forgetting does not come into play, as it is a feature of online learning with approximators such as neural networks. Essentially ...
user avatar
  • 23.3k
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, ...
user avatar
  • 33.2k
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. ...
user avatar
  • 23.3k
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 ...
user avatar
  • 23.3k
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, ...
user avatar
  • 23.3k
1 vote
Accepted

What are the differences between SARSA and Q-learning?

The main difference between the two is that Q-learning is an off policy algorithm. That is, we learn about an policy that is different to the one we choose to make actions. To see this, lets look at ...
user avatar

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