2
$\begingroup$

From Sutton and Barto's book Reinforcement Learning (Adaptive Computation and Machine Learning series) (p. 99), the following definition for first-visit MC prediction, for estimating $V \sim V_\pi$ is given:

enter image description here

Is determining the reward for each action a requirement of SARSA? Can the agent wait until the end of the episode to determine the reward?

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$.

Does this mean then that depending on the task it is not always possible to determine reward at time step $t$, and the agent must wait until the end of an episode? If the agent does not evaluate reward until the end of an episode, is the algorithm still SARSA?

$\endgroup$
1
$\begingroup$

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$ from $t=1$ to $t=T$ (terminal state). This is the reward distribution that the algorithms refer to as $R_t$.

It does not matter if nearly all the rewards are $0$. That is still a reward value, even if it is not an interesting or informative one. Some environments will have non-zero rewards on nearly all time steps. Some environments might have zero rewards for every transition apart from one or two important exceptions that define the goal of the agent.

So in tic-tac-toe, if the game has not ended, the reward will be $0$ because neither player has won or lost, and obtaining a win is a learning objective. If you use $0$ reward value for all incomplete time steps in tic-tac-toe, and SARSA algorithm as written from Sutton & Barto, then it will work as expected. You don't need to wait until the end of the episode, and the algorithm will still learn to predict values of moves despite experiencing many $r_t = 0$ during start and middle of the game.

You show the MC prediction algorithm, which does wait until the end of each episode until calculating estimated values, using the experienced return.

I think one of the things that you might want to review is the difference between immediate reward following a timestep (noted $R_{t+1}$) and return (noted $G_t$). There is a relationship between the two $G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$. All the value based methods, such as MC prediction, or SARSA, are ways to estimate the expected return $\mathbb{E}_{\pi}[G_t]$ given some context, such as the state or state and action at time $t$.

Given that, this should answer your other questions.

Is determining the reward for each action a requirement of SARSA?

It is a general requirement for MDPs, and is expected by all solvers. However, a default of $0$ is fine, if that's how the environment works. The reinforcement learning (RL) algorithms can all cope with delays to important reward values (such as those from winning or losing a game). Bigger delays - e.g. thousands of $0$ reward steps between more meaningful values - are often associated with harder problems to solve, so the simpler algorithms might not be practical. But they all cope in theory given enough experience.

Can the agent wait until the end of the episode to determine the reward?

No, you should always be able calulate an immediate reward value $r_{t+1}$ after taking each action $a_t$ from state $s_t$.

However, it is OK in general to wait until you have summed up more of those rewards (e.g. $r_{t+1}$ to $r_{t+n}$) before making an estimate of the return $g_t$ to update a value estimate. Single step SARSA (sometimes called SARSA(0)) does not wait - it makes update steps using a single immediate reward value. However, other agent types including Monte Carlo (MC), and some variants of SARSA, can and do wait - sometimes just for some steps, sometimes until the end of each episode.

It is a choice you can make when designing agents, there are consequences. Waiting until end of the episode (as in MC) means you have unbiased estimates of value, but takes longer, and leads to higher variability in updates. Using reward values after each step (as in SARSA(0)) means you get to make more frequent updates which may converge fatser, but you start with biased incorrect values.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.