What is a time-step in a Markov Decision Process?

Question

The "discounted sum of future rewards" (or return) using discount factor $\gamma$ is

$$\gamma^1 r_1 +\gamma^2 r_2 + \gamma^3 r_2 + \dots \tag{1}\label{1}$$

where $r_i$ is the reward received at the $i$th time-step.

I am confused as to what constitutes a time-step. Say, I take an action now, so I will get a reward in 1 time-step. Then, I will take an action again in timestep 2 to get a second reward in time-step 3. But the formula \ref{1} suggests something else.

How does one define a time-step? Can we take action as well receive a reward in a single step?

Examples are most helpful.

Answer 1

In a Markov Decision Process (MDP) model, we define a set of states ($S$), a set of actions ($A$), the rewards ($R$), and the transition probabilities $P(s' \mid s, a)$. The goal is to figure out the best action to take in each of the states, i.e. the policy $\pi$.

Policy

To calculate the policy we make use of the Bellman equation:

$$V_{i+1}(s)=R(s)+\gamma \max _{a \in A}\left(\sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s, a\right) V_{i}\left(s^{\prime}\right)\right)$$

When starting to calculate the values we can simply start with:

$$V_{1}(s)=R(s)$$

To improve this value, we should take into account the next action, which can be taken by the system and will result in a new reward:

$$V_{2}(s)=R(s)+\gamma \max _{a \in A}\left(\sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s, a\right) V_{1}\left(s^{\prime}\right)\right)$$

Here you take into account the reward of the current state $s$: $R(s)$, and the weighted sum of possible future rewards. We use $P(s' \mid s, a)$ to give the probability of reaching state $s'$ from $s$ with action $a$. $\gamma$ is a value between $0$ and $1$ and is called the discount factor because it reduces the importance of future rewards since these are uncertain. An often-used value is $\gamma = 0.95$.

When using value iteration this process is continued until the value function has converged, which means that the value function does not change significantly when doing new iterations:

$$\left\|V_{i+1}(s)-V_{i}(s)\right\|<\epsilon, \; \forall_{s \in S},$$

where $\epsilon$ is a really small value.

Discounted sum of future rewards

If you look at the Bellman equation and execute it iteratively you'll see:

$$ {\scriptstyle V(s)=R(s) + \gamma \max _{a \in A}\left(\sum_{a \in A} P\left(s^{\prime} \mid s, a\right)\left[R\left(s^{\prime}\right) + \gamma \max _{a \in A}\left(\sum_{s^{\prime \prime} \in S} P\left(s^{\prime \prime} \mid s^{\prime}, a\right)\left(R\left(s^{\prime \prime}\right) + \gamma \max _{a \in A}\left(\sum_{s^{\prime \prime \prime} \in S} P\left(s^{\prime \prime \prime} \mid s^{\prime \prime}, a\right) V\left(s^{\prime \prime \prime}\right)\right)\right]\right)\right.\right. }$$

This is like (without transition functions):

$$R(s)+\gamma R\left(s^{\prime}\right)+\gamma^{2} R\left(s^{\prime \prime}\right)+\gamma^{3} R\left(s^{\prime \prime \prime}\right)+\ldots$$

To conclude

So when we start in state s we want to take the action that gives us the best total reward taking into account not only the current, or next state, but all possible next states until we reach the goal. These are the time steps you refer to, i.e. each action taken is done in a time step. And when we learn the policy we try to take into account as many time steps as possible to choose the best action.

---

You can find quite a large number of examples if you search on the internet, for example, in the slides of the CMU, the UC Berkeley or the UW.

Answer 2

In the reinforcement learning setting, an agent interacts with an environment in (discrete) time steps, which are incremented after the agent takes an action, receives a reward and the "system" (the environment and the agent) moves to a new state.

More precisely, at time step $t=0$ (the first time step), the environment (including the agent) is in some state $s_t = s_0$, takes an action $a_t = a_0$ and receives and reward $r_t = r_0$ and the environment (including the agent) moves to a next state $s_{t+1} = s_{0 + 1} = s_1$, which will also be the state that the environment will be in at the next time step, $t+1$, hence the notation $s_{t+1}$. Here, the subscripts $_t$ refer to the time step associated with those "entities" (state, action and rewards). So, after one time step (or after $t=0$), the agent will be in state $s_{t+1}$ and the new time step will be $t + 1 = 0 + 1 = 1$. So, we are now at time step $t=1$ (because we have just incremented the time step) and the agent is in state $s_{t} = s_1$. The previously described interaction then repeats: the agent takes an action $a_{t} = a_1$, gets the reward $r_t = r_1$ and the environment moves to the state $s_{t+1} = s_{1+1} = s_{2}$, and so on.

In your summation, we are just discounting the rewards using a value denoted by $\gamma$ (which is usually between $0$ and $1$), that is often called the "discount factor". That summation represents the summation of the rewards the agent will received starting (in this case) from time step $t=1$. We could also just have $r_1 + r_2 + r_3 + \dots $, but, for technical or mathematical reasons, we often "discount" the rewards, that is, we multiply them by $\gamma$ (raised to a power associated with the time step that reward will be received).

In the above description, I said that, at some time step $t$, the agent takes an action $a_t$ and receives a reward $r_t$. However, it is often the case that the reward received after taken an action at time step $t$ is denoted by $r_{t+1}$. I think this is a little confusing, but not conceptually "wrong", because one might think that the reward for having performed an action at time step $t$ is only received at the next time step. (You should get used to slightly different notations and terminology. At the beginning, it is not easy to understand, if the notation is not precise and consistent across sources, but you will get used to it, the more you learn about the topic, in the same way that you get used to a new language).