# Tag Info

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$ in the episode we do the following: Take action $A_t$ and observe $R_{t+1}$, $S_{t+1}$ Choose $A_{t+1}$ using $S_{t+1}$ in our policy $Q(S_t, A_t) = Q(S_t, A_t)... 4 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 solution has not changed (much) with respect to the previous one. In your case, the solutions are value functions, so you could check if your algorithm has ... 4 The true answers are 1 and 3. 1 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 directly about the greedy policy,$\pi(a|s) := \arg \max_a Q_\pi(s,a)$, and because Q-learning converges to the optimal Q-value function we know that the policy will be ... 4 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 should hold for any action, as long as$s'$is terminal). It is easier to understand why this should be the case by dissecting what the different terms in the ... 4 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 ϵ-greedy? I don't quite understand the question. SARSA is on-policy evaluation with$\epsilon$-greedy policy. Q-learning is off-policy evaluation with$\epsilon$-... 4 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$\epsilon $. The problem with$\epsilon$-greedy is that, when it chooses the random actions (i.e. with probability$\epsilon$), it chooses them uniformly (i.e. ... 4 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 to teach. As you have noted, the main difference between reinforcement learning (RL) and supervised learning is that RL does not use labeled datasets. If you ... 3 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 taken this action$a$from$s$, the reward$r$and the next state$s'$are observed. At this point, to update the estimate of the$Q$function, you use a target ... 3 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 has zero probability under the target policy, then$Q$isn't updated at all, which is good. Alternatively, if only$G$is scaled by$\rho$, taking zero ... 3 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 the current state$s$is known. However, in POMDP, at each time step, the agent does not know the current state, but it maintains a "belief" (which, ... 2 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 agent, and treat it as training data for the neural network model, using the same loss function and other hyperparameters as you intend to use when the NN is being ... 2 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[ R + \gamma \max_{A'} Q(S', A') \right].$$ Both of these update rules are formulated for single-agent Markov Decision Processes. Sometimes you can make them ... 2 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 implementing a reward function where a specific reward is associated with the end of the episode such as "r(robot ran into a wall) = -100" then one can imagine that there ... 2 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 policy that actually took the action, then you are using Expected SARSA in an off-policy way. Q-learning is a special case of Expected SARSA, where the target ... 2 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: $$V^\pi(s) = Q^\pi(s, \pi(s))$$ Intuitively, this is because the$V^\pi(s)$is the expected future return when following the policy$\pi$from state$s$, ... 1 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 often modelled as an "absorbing state" where the action is unimportant (either null or value ignored) with value by definition of$0$. And you can't ... 1 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, where no matter what the choice is made in$s_2$or$s_3$, the following state is$s_1$. The first, terminating, view is a simpler and entirely natural view ... 1 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 the update rule. Q-Learning $$Q(s,a) = Q(s,a) + \alpha (R_{t+1} + \gamma \max_aQ(s',a) - Q(s,a))$$ SARSA$$Q(s,a) = Q(s,a) + \alpha (R_{t+1} + \gamma Q(s',a'... 1 There are a couple of things to break down here. The first thing is to correct this: For example, the reward for the game tic-tac-toe is decided at the end of the episode, when the player wins, loses, or draws the match. The reward is not available at each step$t$. In a Markov Decision Process (MDP), there is always an immediate reward for each time$t$... 1 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, converges to the optimal value function, provided certain assumptions are met Infinite visits to every state-action pair The learning policy becomes greedy ... 1 I have the conditions for convergence in these notes SARSA convergence by Nahum Shimkin. The Robbins-Monro conditions above hold for$α_t$. Every state-action pair is visited infinitely often The policy is greedy with respect to the policy derived from$Q$in the limit The controlled Markov chain is communicating: every state can be reached from any other ... 1 The important part, where you can see a single reward value is used for$n$different updates, is the part where a sum of$R_i$values with$i$ranging from$\tau + 1$to$\tau + n$is assigned to$G$. So yes, the outer loop of the algorithm always does at most one update per iteration, but for that update it uses multiple previously observed$R_i\$ values. ...