Answers.Body: <p>Personally, I find the best way to think of SMDPs intuitively by just imagining that you just discretise the time into such small steps (infinitesimally small steps if necessary) that you can treat it as a normal MDP again, but with some extra domain knowledge that you can exploit primarily for computational efficiency:</p>
  <ol>
  <li>Only at time steps that really correspond to &quot;events&quot; in your SMDP can you observe non-zero rewards; at all other time steps you just get rewards equal to <span class="math-container">$0$</span>.</li>
  <li>Only at time steps that really correspond to &quot;events&quot; in your SMDP do you have an action space greater than <span class="math-container">$1$</span>; in all the &quot;fake&quot; time steps, you have no agency, you just have a single action available (say, a &quot;dummy&quot; or &quot;null&quot; action). So all of these &quot;fake&quot; time steps do not contribute in any way to the &quot;credit assignment&quot; problem in RL, and you can kind of ignore them in your learning steps; only the time spent in them can still be important for discount factors <span class="math-container">$\gamma &lt; 1$</span>.</li>
  </ol>
  <hr />
  <blockquote>
  <p>If <span class="math-container">$\tau$</span> (real number not an integer number) shows the time between two arrivals, should I update Q-functions as follows:</p>
  </blockquote>
  <p>Yes, an update rule like that looks correct to me. Let's take an example situation, where <span class="math-container">$\tau = 2.0$</span>, and instead of using the update rule you suggest, we take the &quot;proper&quot; approach of discretising into smaller time steps, and treating it as a regular MDP. In this simple example case, it is sufficient to discretise by taking time steps that correspond to durations of <span class="math-container">$1.0$</span>.</p>
  <p>In the SMDP, we'll have only a single transition <span class="math-container">$s_0 \rightarrow s_2$</span> (it will become clear why I use slightly strange time-indexing here soon), after which we observe a reward, and this transition takes time <span class="math-container">$\tau = 2.0$</span>. In the corresponding MDP, we'll have two state transitions; <span class="math-container">$s_0 \rightarrow s_1$</span>, and <span class="math-container">$s_1 \rightarrow s_2$</span>, with two reward observations <span class="math-container">$R_1$</span> and <span class="math-container">$R_2$</span>, where we know for sure that:</p>
  <ol>
  <li><span class="math-container">$R_2 = 0$</span> (because it does not actually correspond to any event in the SMDP)</li>
  <li>We have a meaningful choice between multiple actions at <span class="math-container">$s_0$</span>, each of which can have different transition probabilities for taking us into different &quot;dummy&quot; states <span class="math-container">$s_1$</span>, and yield possibly-non-zero rewards <span class="math-container">$R_1$</span>. In the dummy state <span class="math-container">$s_1$</span>, we'll always only have the choice for a single dummy/null action (because this state does not correspond to any event in the SMDP), which always yields <span class="math-container">$R_2 = 0$</span> as mentioned above.</li>
  </ol>
  <p>So, the correct update rule for <span class="math-container">$s_1$</span> where we picked a forced dummy action <span class="math-container">$\varnothing$</span> and are doomed to receive a reward <span class="math-container">$R_2 = 0$</span>, would be:</p>
  <p><span class="math-container">$$Q(s_1, \varnothing) \gets Q(s_1, \varnothing) + \alpha \left( 0 + \gamma \max_{a'} Q(s_2, a') - Q(s_1, \varnothing) \right)$$</span></p>
  <p>and the correct update rule for <span class="math-container">$s_0$</span>, where we picked a meaningful action <span class="math-container">$a_0$</span> and may get a non-zero reward <span class="math-container">$R_1$</span>, would be:</p>
  <p><span class="math-container">$$Q(s_0, a_0) \gets Q(s_0, a_0) + \alpha \left( R_1 + \gamma \max_{a'} Q(s_1, a') - Q(s_0, a_0) \right)$$</span></p>
  <p>In this last update rule, we know that <span class="math-container">$s_1$</span> is a dummy state in which the dummy action <span class="math-container">$\varnothing$</span> is the <strong>only</strong> legal action. So, we can get rid of the <span class="math-container">$\max$</span> operator there and simplify it to:</p>
  <p><span class="math-container">$$Q(s_0, a_0) \gets Q(s_0, a_0) + \alpha \left( R_1 + \gamma Q(s_1, \varnothing) - Q(s_0, a_0) \right)$$</span></p>
  <p>Since we know that <span class="math-container">$s_1$</span> is a dummy state in which we are never able to make meaningful choices anyway, it seems a bit wasteful to actually keep track of <span class="math-container">$Q(s_1, \varnothing)$</span> values for it. Luckily, we can easily express <span class="math-container">$Q(s_1, \varnothing)$</span> directly in terms of <span class="math-container">$Q(s2, \cdot)$</span> -- which is exactly the next set of <span class="math-container">$Q$</span>-values that we would be interested in keeping track of again:</p>
  <p><span class="math-container">$$Q(s_1, \varnothing) = \mathbb{E} \left[ 0 + \gamma \max_{a'} Q(s_2, a') \right]$$</span></p>
  <p>So if we want to skip learning <span class="math-container">$Q$</span>-values for <span class="math-container">$s_1$</span> (because it's kind of a waste of effort), we can just use this definition and plug it straight into the update rule for <span class="math-container">$Q(s_0, a_0)$</span>. <span class="math-container">$Q$</span>-learning is inherently an algorithm that just concrete samples of experience to estimate expectations (and this is a major reason why it typically uses learning rates <span class="math-container">$\alpha &lt; 1.0$</span>, so we can simply get rid of the expectation operator when doing this:</p>
  <p><span class="math-container">$$Q(s_0, a_0) \gets Q(s_0, a_0) + \alpha \left( R_1 + \gamma \left[ \gamma \max_{a'} Q(s_2, a') \right] - Q(s_0, a_0) \right)$$</span></p>
  <p>and this is basically the update rule that you suggested. Note; here I assumed that you receive your rewards directly when you do take actions in your SMDP, which is why I had <span class="math-container">$R_1$</span> as a possibly-non-zero reward, and always <span class="math-container">$R_2 = 0$</span>. I suppose you could also in some cases envision SMDPs where the reward only arrives on the next SMDP-time-step, and that the amount of time that ends up being elpased in between the two events is important to take into account via the discount factor <span class="math-container">$\gamma$</span>. So you could also choose to model a problem where <span class="math-container">$R_1 = 0$</span> and <span class="math-container">$R_2$</span> may be non-zero, and this would yield a different update rule (I think one where the reward gets multiplied by <span class="math-container">$\gamma^{\tau - 1}$</span>? not sure, would have to go through the steps again).</p>
  <hr />
  <blockquote>
  <p>What measure should be used in the SMDP setting? I would be thankful if someone can explain the Q-Learning algorithm for the SMDP problem with this setting.</p>
  </blockquote>
  <p>I think it would be important to involve the amount of time that you take somehow in your evaluation criterion. You could run episodes for a fixed amount of time, and then just evaluate agents based on the sum of rewards. If you don't run for a fixed amount of time (but instead for a fixed number of steps, each of which may take variable amounts of time, for example), you would probably instead want to evaluate agents based on the average rewards per unit of time. You could also include discount factors in your evaluation if you want, but probably don't have to.</p>
  <hr />
  <blockquote>
  <p>Moreover, I am wondering when Q-functions are updated. For example, if a customer enters our website and purchases a product, we want to update the Q-functions. Suppose that the planning horizon (state <span class="math-container">$S_0$</span>) starts at 10:00 am, and the first customer enters at 10:02 am, and we sell a product and gain <span class="math-container">$R_1$</span> and the state will be <span class="math-container">$S_1$</span>. The next customer enters at 10:04 am, and buy a product, and gain reward <span class="math-container">$R_2$</span> (state <span class="math-container">$S_2$</span>). In this situation, should we wait until 10:02 to update the Q-function for state <span class="math-container">$S_0$</span>?</p>
  </blockquote>
  <p>This depends on you state representation, and how you model a &quot;state&quot;, and to what extent previous actions have influence the state you end up in. Keep in mind that the update rule for <span class="math-container">$Q(S_0)$</span> also requires for <span class="math-container">$S_1$</span> (or even <span class="math-container">$S_2$</span> if <span class="math-container">$S_1$</span> is a &quot;dummy state&quot; that you skip) to have been observed. So, if your state representation includes some features describing the &quot;current customer&quot; for which you want to pick an action (do you offer them a discount or not, for example?), then you can only update the <span class="math-container">$Q$</span>-value for the previous customer when the next customer has arrived. This model does assume that your previous actions have some level of influence over the future states that you may end up in though. For example, you might assume that if your actions make the first customer very happy, you get a better reputation and are therefore more likely to end up in future states where other customers visit more frequently.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-28T10:54:15.643Z
Answers.LastActivityDate: 2020-06-28T10:54:15.643Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>Suppose that the transition time between two states is a random variable (for example, unknown exponential distribution); and between two arrivals, there is no reward. If <span class="math-container">$\tau$</span> (real number not an integer number) shows the time between two arrivals, should I update Q-functions as follows:</p>
  <p><span class="math-container">$Q(s,a) = Q(s,a)+\alpha.(R+\gamma^{\tau} \max_{b \in A}Q(s^{\prime},b)-Q(s,a))$</span></p>
  <p>And, to compare different algorithms, total rewards (<span class="math-container">$TR=R_{1}+ R_2+R_{3}+...+R_{T}$</span>) is used.</p>
  <p><em>What measure should be used in the SMDP setting?</em> I would be thankful if someone can explain the Q-Learning algorithm for the SMDP problem with this setting.</p>
  <p>Moreover, I am wondering when Q-functions are updated. For example, if a customer enters our website and purchases a product, we want to update the Q-functions. Suppose that the planning horizon (state <span class="math-container">$S_{0}$</span>) starts at 10:00 am, and the first customer enters at 10:02 am, and we sell a product and gain <span class="math-container">$R_1$</span> and the state will be <span class="math-container">$S_1$</span>. The next customer enters at 10:04 am, and buy a product, and gain reward <span class="math-container">$R_2$</span> (state <span class="math-container">$S_{2}$</span>). <em>In this situation, should we wait until 10:02 to update the Q-function for state <span class="math-container">$S_0$</span>?</em></p>
  <p>Is the following formula correct?</p>
  <p><span class="math-container">$$V(S_0)= R_1 \gamma^2+  \gamma^2V(S_1)$$</span></p>
  <p>In this case, if I discretize the time horizon to 1-minute intervals, the problem will be a regular MDP problem. <em>Should I update Q-functions when no customer enters in a time interval (reward =0)?</em></p>
  
Tags: <reinforcement-learning><q-learning><markov-decision-process><discount-factor><semi-mdp>
Title: Updating action-value functions in Semi-Markov Decision Process and Reinforcement Learning
UserDisplayName: Amin
ThreadText: # Updating action-value functions in Semi-Markov Decision Process and Reinforcement Learning
  
  (Asked by: username_0 on 2020-06-21)
  
  Suppose that the transition time between two states is a random variable (for example, unknown exponential distribution); and between two arrivals, there is no reward. If $\tau$ (real number not an integer number) shows the time between two arrivals, should I update Q-functions as follows:
  
  $Q(s,a) = Q(s,a)+\alpha.(R+\gamma^{\tau} \max\_{b \in A}Q(s^{\prime},b)-Q(s,a))$
  
  And, to compare different algorithms, total rewards ($TR=R\_{1}+ R\_2+R\_{3}+...+R\_{T}$) is used.
  
  *What measure should be used in the SMDP setting?* I would be thankful if someone can explain the Q-Learning algorithm for the SMDP problem with this setting.
  
  Moreover, I am wondering when Q-functions are updated. For example, if a customer enters our website and purchases a product, we want to update the Q-functions. Suppose that the planning horizon (state $S\_{0}$) starts at 10:00 am, and the first customer enters at 10:02 am, and we sell a product and gain $R\_1$ and the state will be $S\_1$. The next customer enters at 10:04 am, and buy a product, and gain reward $R\_2$ (state $S\_{2}$). *In this situation, should we wait until 10:02 to update the Q-function for state $S\_0$?*
  
  Is the following formula correct?
  
  $$V(S\_0)= R\_1 \gamma^2+ \gamma^2V(S\_1)$$
  
  In this case, if I discretize the time horizon to 1-minute intervals, the problem will be a regular MDP problem. *Should I update Q-functions when no customer enters in a time interval (reward =0)?*
  
  **Tags:** reinforcement-learning, q-learning, markov-decision-process, discount-factor, semi-mdp
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-06-28. Score: 1
  
  Personally, I find the best way to think of SMDPs intuitively by just imagining that you just discretise the time into such small steps (infinitesimally small steps if necessary) that you can treat it as a normal MDP again, but with some extra domain knowledge that you can exploit primarily for computational efficiency:
  
  1. Only at time steps that really correspond to "events" in your SMDP can you observe non-zero rewards; at all other time steps you just get rewards equal to $0$.
  2. Only at time steps that really correspond to "events" in your SMDP do you have an action space greater than $1$; in all the "fake" time steps, you have no agency, you just have a single action available (say, a "dummy" or "null" action). So all of these "fake" time steps do not contribute in any way to the "credit assignment" problem in RL, and you can kind of ignore them in your learning steps; only the time spent in them can still be important for discount factors $\gamma < 1$.
  
  ---
  
  > If $\tau$ (real number not an integer number) shows the time between two arrivals, should I update Q-functions as follows:
  
  Yes, an update rule like that looks correct to me. Let's take an example situation, where $\tau = 2.0$, and instead of using the update rule you suggest, we take the "proper" approach of discretising into smaller time steps, and treating it as a regular MDP. In this simple example case, it is sufficient to discretise by taking time steps that correspond to durations of $1.0$.
  
  In the SMDP, we'll have only a single transition $s\_0 \rightarrow s\_2$ (it will become clear why I use slightly strange time-indexing here soon), after which we observe a reward, and this transition takes time $\tau = 2.0$. In the corresponding MDP, we'll have two state transitions; $s\_0 \rightarrow s\_1$, and $s\_1 \rightarrow s\_2$, with two reward observations $R\_1$ and $R\_2$, where we know for sure that:
  
  1. $R\_2 = 0$ (because it does not actually correspond to any event in the SMDP)
  2. We have a meaningful choice between multiple actions at $s\_0$, each of which can have different transition probabilities for taking us into different "dummy" states $s\_1$, and yield possibly-non-zero rewards $R\_1$. In the dummy state $s\_1$, we'll always only have the choice for a single dummy/null action (because this state does not correspond to any event in the SMDP), which always yields $R\_2 = 0$ as mentioned above.
  
  So, the correct update rule for $s\_1$ where we picked a forced dummy action $\varnothing$ and are doomed to receive a reward $R\_2 = 0$, would be:
  
  $$Q(s\_1, \varnothing) \gets Q(s\_1, \varnothing) + \alpha \left( 0 + \gamma \max\_{a'} Q(s\_2, a') - Q(s\_1, \varnothing) \right)$$
  
  and the correct update rule for $s\_0$, where we picked a meaningful action $a\_0$ and may get a non-zero reward $R\_1$, would be:
  
  $$Q(s\_0, a\_0) \gets Q(s\_0, a\_0) + \alpha \left( R\_1 + \gamma \max\_{a'} Q(s\_1, a') - Q(s\_0, a\_0) \right)$$
  
  In this last update rule, we know that $s\_1$ is a dummy state in which the dummy action $\varnothing$ is the **only** legal action. So, we can get rid of the $\max$ operator there and simplify it to:
  
  $$Q(s\_0, a\_0) \gets Q(s\_0, a\_0) + \alpha \left( R\_1 + \gamma Q(s\_1, \varnothing) - Q(s\_0, a\_0) \right)$$
  
  Since we know that $s\_1$ is a dummy state in which we are never able to make meaningful choices anyway, it seems a bit wasteful to actually keep track of $Q(s\_1, \varnothing)$ values for it. Luckily, we can easily express $Q(s\_1, \varnothing)$ directly in terms of $Q(s2, \cdot)$ -- which is exactly the next set of $Q$-values that we would be interested in keeping track of again:
  
  $$Q(s\_1, \varnothing) = \mathbb{E} \left[ 0 + \gamma \max\_{a'} Q(s\_2, a') \right]$$
  
  So if we want to skip learning $Q$-values for $s\_1$ (because it's kind of a waste of effort), we can just use this definition and plug it straight into the update rule for $Q(s\_0, a\_0)$. $Q$-learning is inherently an algorithm that just concrete samples of experience to estimate expectations (and this is a major reason why it typically uses learning rates $\alpha < 1.0$, so we can simply get rid of the expectation operator when doing this:
  
  $$Q(s\_0, a\_0) \gets Q(s\_0, a\_0) + \alpha \left( R\_1 + \gamma \left[ \gamma \max\_{a'} Q(s\_2, a') \right] - Q(s\_0, a\_0) \right)$$
  
  and this is basically the update rule that you suggested. Note; here I assumed that you receive your rewards directly when you do take actions in your SMDP, which is why I had $R\_1$ as a possibly-non-zero reward, and always $R\_2 = 0$. I suppose you could also in some cases envision SMDPs where the reward only arrives on the next SMDP-time-step, and that the amount of time that ends up being elpased in between the two events is important to take into account via the discount factor $\gamma$. So you could also choose to model a problem where $R\_1 = 0$ and $R\_2$ may be non-zero, and this would yield a different update rule (I think one where the reward gets multiplied by $\gamma^{\tau - 1}$? not sure, would have to go through the steps again).
  
  ---
  
  > What measure should be used in the SMDP setting? I would be thankful if someone can explain the Q-Learning algorithm for the SMDP problem with this setting.
  
  I think it would be important to involve the amount of time that you take somehow in your evaluation criterion. You could run episodes for a fixed amount of time, and then just evaluate agents based on the sum of rewards. If you don't run for a fixed amount of time (but instead for a fixed number of steps, each of which may take variable amounts of time, for example), you would probably instead want to evaluate agents based on the average rewards per unit of time. You could also include discount factors in your evaluation if you want, but probably don't have to.
  
  ---
  
  > Moreover, I am wondering when Q-functions are updated. For example, if a customer enters our website and purchases a product, we want to update the Q-functions. Suppose that the planning horizon (state $S\_0$) starts at 10:00 am, and the first customer enters at 10:02 am, and we sell a product and gain $R\_1$ and the state will be $S\_1$. The next customer enters at 10:04 am, and buy a product, and gain reward $R\_2$ (state $S\_2$). In this situation, should we wait until 10:02 to update the Q-function for state $S\_0$?
  
  This depends on you state representation, and how you model a "state", and to what extent previous actions have influence the state you end up in. Keep in mind that the update rule for $Q(S\_0)$ also requires for $S\_1$ (or even $S\_2$ if $S\_1$ is a "dummy state" that you skip) to have been observed. So, if your state representation includes some features describing the "current customer" for which you want to pick an action (do you offer them a discount or not, for example?), then you can only update the $Q$-value for the previous customer when the next customer has arrived. This model does assume that your previous actions have some level of influence over the future states that you may end up in though. For example, you might assume that if your actions make the first customer very happy, you get a better reputation and are therefore more likely to end up in future states where other customers visit more frequently.
  
  
  ---
  
  