Answers.Body: <p>In a <a href="https://en.wikipedia.org/wiki/Markov_decision_process" rel="nofollow noreferrer">Markov Decision Process (MDP)</a> model, we define a set of states (<span class="math-container">$S$</span>), a set of actions (<span class="math-container">$A$</span>), the rewards (<span class="math-container">$R$</span>), and the transition probabilities <span class="math-container">$P(s' \mid s, a)$</span>. The goal is to figure out the best action to take in each of the states, i.e. the policy <span class="math-container">$\pi$</span>.</p>
  <h2>Policy</h2>
  <p>To calculate the policy we make use of the <a href="https://en.wikipedia.org/wiki/Bellman_equation" rel="nofollow noreferrer">Bellman equation</a>:</p>
  <p><span class="math-container">$$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)$$</span></p>
  <p>When starting to calculate the values we can simply start with:</p>
  <p><span class="math-container">$$V_{1}(s)=R(s)$$</span></p>
  <p>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:</p>
  <p><span class="math-container">$$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)$$</span></p>
  <p>Here you take into account the reward of the current state <span class="math-container">$s$</span>: <span class="math-container">$R(s)$</span>, and the weighted sum of possible future rewards. We use <span class="math-container">$P(s' \mid s, a)$</span> to give the probability of reaching state <span class="math-container">$s'$</span> from <span class="math-container">$s$</span> with action <span class="math-container">$a$</span>. <span class="math-container">$\gamma$</span> is a value between <span class="math-container">$0$</span> and <span class="math-container">$1$</span> and is called the <em>discount factor</em> because it reduces the importance of future rewards since these are uncertain. An often-used value is <span class="math-container">$\gamma = 0.95$</span>.</p>
  <p>When using <a href="http://artint.info/html/ArtInt_227.html" rel="nofollow noreferrer">value iteration</a> this process is continued until the value function has <em>converged</em>, which means that the value function does not change significantly when doing new iterations:</p>
  <p><span class="math-container">$$\left\|V_{i+1}(s)-V_{i}(s)\right\|&lt;\epsilon, \; \forall_{s \in S},$$</span></p>
  <p>where <span class="math-container">$\epsilon$</span> is a really small value.</p>
  <h2>Discounted sum of future rewards</h2>
  <p>If you look at the Bellman equation and execute it iteratively you'll see:</p>
  <p><span class="math-container">$$ {\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. }$$</span></p>
  <p>This is like (without transition functions):</p>
  <p><span class="math-container">$$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$$</span></p>
  <h2>To conclude</h2>
  <p>So when we start in state <em>s</em> 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.</p>
  <hr />
  <p>You can find quite a large number of examples if you search on the internet, for example, in the slides of <a href="http://www.cs.cmu.edu/afs/andrew/course/15/381-f08/www/lectures/HandoutMDP.pdf" rel="nofollow noreferrer">the CMU</a>, the <a href="https://people.eecs.berkeley.edu/%7Epabbeel/cs287-fa12/slides/mdps-exact-methods.pdf" rel="nofollow noreferrer">UC Berkeley</a> or the <a href="https://homes.cs.washington.edu/%7Etodorov/courses/amath579/MDP.pdf" rel="nofollow noreferrer">UW</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-02T15:33:06.990Z
Answers.Text: While this is nicely detailed, I think you could have answered the question more directly and succinctly
Answers.UserDisplayName: hisairnessag3
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2016-11-08T14:38:24.750Z
Answers.LastActivityDate: 2020-07-18T14:46:59.737Z
Answers.LastEditDate: 2020-07-18T14:46:59.737Z
Answers.UserDisplayName: agold
Answers.Body: <p>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. </p>
  
  <p>More precisely, at time step <span class="math-container">$t=0$</span> (the first time step), the environment (including the agent) is in some state <span class="math-container">$s_t = s_0$</span>, takes an action <span class="math-container">$a_t = a_0$</span> and receives and reward <span class="math-container">$r_t = r_0$</span> and the environment (including the agent) moves to a next state <span class="math-container">$s_{t+1} = s_{0 + 1} = s_1$</span>, which will also be the state that the environment will be in at the next time step, <span class="math-container">$t+1$</span>, hence the notation <span class="math-container">$s_{t+1}$</span>. Here, the subscripts <span class="math-container">$_t$</span> refer to the time step associated with those "entities" (state, action and rewards). So, after one time step (or after <span class="math-container">$t=0$</span>), the agent will be in state <span class="math-container">$s_{t+1}$</span> and the new time step will be <span class="math-container">$t + 1 = 0 + 1 = 1$</span>. So, we are now at time step <span class="math-container">$t=1$</span> (because we have just incremented the time step) and the agent is in state <span class="math-container">$s_{t} = s_1$</span>. The previously described interaction then repeats: the agent takes an action <span class="math-container">$a_{t} = a_1$</span>, gets the reward <span class="math-container">$r_t = r_1$</span> and the environment moves to the state <span class="math-container">$s_{t+1} = s_{1+1} = s_{2}$</span>, and so on.</p>
  
  <p>In your summation, we are just discounting the rewards using a value denoted by <span class="math-container">$\gamma$</span> (which is usually between <span class="math-container">$0$</span> and <span class="math-container">$1$</span>), 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 <span class="math-container">$t=1$</span>. We could also just have <span class="math-container">$r_1 + r_2 + r_3 + \dots $</span>, but, for technical or mathematical reasons, we often "discount" the rewards, that is, we multiply them by <span class="math-container">$\gamma$</span> (raised to a power associated with the time step that reward will be received).</p>
  
  <p>In the above description, I said that, at some time step <span class="math-container">$t$</span>, the agent takes an action <span class="math-container">$a_t$</span> and receives a reward <span class="math-container">$r_t$</span>. However, it is often the case that the reward received after taken an action at time step <span class="math-container">$t$</span> is denoted by <span class="math-container">$r_{t+1}$</span>. 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 <span class="math-container">$t$</span> 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).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-02T16:40:21.590Z
Answers.LastActivityDate: 2019-04-02T16:52:50.700Z
Answers.LastEditDate: 2019-04-02T16:52:50.700Z
Answers.UserDisplayName: nbro
Body: <p>The &quot;discounted sum of future rewards&quot; (or return) using discount factor <span class="math-container">$\gamma$</span> is</p>
  <p><span class="math-container">$$\gamma^1 r_1 +\gamma^2 r_2 + \gamma^3 r_2 + \dots \tag{1}\label{1}$$</span></p>
  <p>where <span class="math-container">$r_i$</span> is the reward received at the <span class="math-container">$i$</span>th time-step.</p>
  <p>I am confused as to what constitutes a <em>time-step</em>. 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.</p>
  <p>How does one define a time-step? Can we take action as well receive a reward in a single step?</p>
  <p>Examples are most helpful.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-19T01:16:23.860Z
Comments.Text: Hello. This is an old question, but you should accept one of the answers below, if they answer your question. Take a look at https://ai.stackexchange.com/help/someone-answers.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><terminology><markov-decision-process><return><time-step>
Title: What is a time-step in a Markov Decision Process?
UserDisplayName: Abhishek Bhatia
ThreadText: # What is a time-step in a Markov Decision Process?
  
  (Asked by: username_0 on 2016-10-27)
  
  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.
  
  **Tags:** reinforcement-learning, terminology, markov-decision-process, return, time-step
  > **Comments:**
  > **username_1**: Hello. This is an old question, but you should accept one of the answers below, if they answer your question. Take a look at https://ai.stackexchange.com/help/someone-answers.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2016-11-08. Score: 6
  
  In a [Markov Decision Process (MDP)](https://en.wikipedia.org/wiki/Markov_decision_process) 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](https://en.wikipedia.org/wiki/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](http://artint.info/html/ArtInt_227.html) 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](http://www.cs.cmu.edu/afs/andrew/course/15/381-f08/www/lectures/HandoutMDP.pdf), the [UC Berkeley](https://people.eecs.berkeley.edu/%7Epabbeel/cs287-fa12/slides/mdps-exact-methods.pdf) or the [UW](https://homes.cs.washington.edu/%7Etodorov/courses/amath579/MDP.pdf).
  
  > **Comments:**
  > **username_3**: While this is nicely detailed, I think you could have answered the question more directly and succinctly  
  
  ---
  
  ### Answer by username_1 on 2019-04-02. Score: 4
  
  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).
  
  
  ---
  
  