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:
- 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$.
- 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:
- $R_2 = 0$ (because it does not actually correspond to any event in the SMDP)
- 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.
