# 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 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 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 ... 3 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 ... 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, ... 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 ... 2 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. ... 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 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 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 ... 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. ... 1 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 ...