11
$\begingroup$

Introduction

I am currently modelling a scenario where two queues need to be served by a single server in a non preemptive discipline. I am quite sorted on generating the optimal policy via Value or Policy Iteration when given the arrival and service rates of the two queues.

The Model

Let $A_1$ and $A_2$ denote the arrival operators for each queue and let $D_1$ and $D_2$ denote the departure/service operators.

We have $\lambda_1$, $\lambda_2$, $\mu_1$ and $\mu_2$ as the arrival and service rates whereas $u$ is the control and $u = 0$ corresponds to serve queue 2 and $u=1$ corresponds to serve queue 1.

Now we use uniformization to allow for the time-continuous process to be described as a discrete chain sampled at intervals of length $\gamma$. Here $\gamma = \lambda_1 + \lambda_2 + \mu_2 + \mu_2$. Hence the transition probabilities are given as:

$$p(x_{k+1},x_k,u_k)= \begin{cases} \frac{\lambda_1}{\gamma} & ,x_{k+1} = A_1(x_k) \\ \frac{\lambda_2}{\gamma} & ,x_{k+1} = A_2(x_k) \\ \frac{\mu_1}{\gamma}u & ,x_{k+1} = D_1(x_k) \\ \frac{\mu_2}{\gamma}(1-u) & ,x_{k+1} = D_2(x_k) \\ \frac{\mu_1}{\gamma}(1-u) + \frac{\mu_2}{\gamma}u &,x_{k+1} = x_{k}\end{cases} $$ Note that we have introduced fictitious transition rates.

Actual Question

Now we get to the actual question. The arrival rates change over time hence the poisson process is not stationary. However, it is stationary for a good amount of time. So I use a Bayesian change-point model to track any changes when they have occurred. I love these models as they are really quite robust and once can tune them to account for zero-inflated data etc.

The Bayesian change-point model gives the following output for the measurement of a single lambda, lets say the arrival rate of queue 1:

enter image description here

The $p_i$ values are to account for zero inflation so please ignore them. Focus must turn to the arrival rates. We note that the change has left us quite uncertain about what the new rate might be (the turquoise one is a wider distribution than the purple one).

So I can take the mean of the new arrival rate, plug it into the transition probabilities and then call it a day. However, the Bayesian change point suggests otherwise. We now have the turquoise distribution being our belief distribution of $\lambda_1$. Is this model uncertainty because we are now uncertain about the transition matrix $p(x_{k+1},x_k,u)$ as a result of $\lambda_1$ not being a single scalar but a belief distribution (please excuse I have not scaled the distribution yet to be considered valid probability distributions)?

I think it is not state uncertainty as state uncertainty results from errors in measurement or observations and should affect the state vector $x_k$ and not the transition model. Am I correct then in saying we are not dealing with a Partially Observable Markov Decision Process ?

If my assumption on model uncertainty is correct, how would you recommend I deal with it?

My Attempt at my own question

I propose the following which may be incorrect. Let $\lambda_{1} \sim b(\theta)$ be the belief distribution given in turquoise. Then we have $p(x_{k+1},x_{k},u\mid \lambda_1) =p(x_{k+1},x_{k},u\mid b(\theta)) $. So we can do the following:

$$ p(x_{k+1},x_k,u) = \sum_{i=1}^{N}p(x_{k+1},x_{k},u\mid b(\theta_i)) $$ Where we assume $b(\theta)$ to be the discrete multinomial turquoise distribution with $N$ categories over $\theta$.

Conclusion

I would love my policy to be sensitive to the arrival uncertainty produced by a change in the stationary distribution. I feel that this would make my controller robust in the sense of being prudent when a change in arrivals rate occurs and is detected. Please help to guide me where I have gone wrong and please recommend methods that you would know or feel to be superior. Thank you very much for your time.

$\endgroup$
4
$\begingroup$

After having read Chapter 5.3 of Decision Making Under Uncertainty by Mykel J. Kochenderfer, I have come to some conclusions.

We are dealing with model uncertainty, in which case we can formulate a Bayes Adaptive Model. In the book that I read, the term model uncertainty refers more to not knowing what the transition probabilities nor the structure of the model might be. In other papers that I read, model uncertainty pertaining to uncertainty of the arrival or service rates in queues might even refer to not knowing what the distribution of the arrival rate might be. So we actually know a lot about our model. We are just a bit uncertain about the exact value of the arrival rate but we know the model.

In the book by Kochenderfer, the compare the Bayes Adaptive Model that of a Partially Observeable Markov Decision Process (POMDP). The same algorithms can essentially be used to solve these problems. Basically, these models make use of belief states and include some form of observation along the way in order to update the beliefs.

I believe our model to be somewhat a bit different. We assume our model to be time-homogeneous/stationary and we will not be updating our beliefs at each epoch as a result. We assume our beliefs to be stationary until the Bayesian Filter is finished running. Only after it has completed do we do one of two things:

  1. We update our beliefs of the arrival rates and the distribution changes a bit (it likely will become thinner as certainty increases). Increased certainty should have a small effect on the policy (or so it is hypothesized).
  2. A change in arrival rate is detected by the filter with 95% confidence. The arrival rate changes completely. It is introduced along with its new beliefs. This should have a large effect on the policy (this is known).

We will thus create a new tuple to describe the state-space. Instead of having $(x_1,x_2)$ to describe the length of the two queues, we augment our belief of what the arrival rate might be and end up with $(x_1,\lambda_1^i,x_2,\lambda_2^j)$ where $i \in \{[0,N_{\lambda_1}] \cap \mathbb{Z}\}$ and $j \in \{[0,N_{\lambda_2}] \cap \mathbb{Z}\}$. The indices have to do with how many classes we divide the continuous distribution up into. The more classes, the more accurate but the strain on the size of the state-space. Our state-space is now of size $M\times N \times N_{\lambda_1}\times N_{\lambda_2}$ which is quite large and the "curse-of-dimensionality" is likely to have an effect of Value and Policy Iteration.

Now onto the new model. We want our policy to be based on the new 4 element tuple. Why? We can observe fully the queue lengths $x_1$ and $x_2$. However we can use the last observed arrival rate into each queue as our current beliefs. Thus we can then lookup our required action to perform for the given tuple based on the current observed states and beliefs.

We must account for the transitions resulting in both changes in state and belief. It is probably also worth mentioning at this point that only one event can cause a transition. I forgot to mention this in the description of the question. The transition rates are stated first (for the continuous time Markov chain) and then the transition probabilities (as for the uniformized Markov chain) as I want to discuss the uniformization factor.

$$ \begin{align} T(x_1+1,\lambda_1^i,x_2,\lambda_2^j\mid x_1,\lambda_1^k,x_2,\lambda_2^l,u) & = p(\lambda_1^i)p(\lambda_2^j)p(\lambda_1^k)p(\lambda_2^l)\times\lambda_1^i \\ T(x_1,\lambda_1^i,x_2+1,\lambda_2^j\mid x_1,\lambda_1^k,x_2,\lambda_2^l,u) & = p(\lambda_1^i)p(\lambda_2^j)p(\lambda_1^k)p(\lambda_2^l)\times\lambda_2^j \\ T(x_1-1,\lambda_1^i,x_2,\lambda_2^j\mid x_1,\lambda_1^k,x_2,\lambda_2^l,u) & = p(\lambda_1^i)p(\lambda_2^j)p(\lambda_1^k)p(\lambda_2^l)\times u \mu_1 \\ T(x_1,\lambda_1^i,x_2-1,\lambda_2^j\mid x_1,\lambda_1^k,x_2,\lambda_2^l,u) & = p(\lambda_1^i)p(\lambda_2^j)p(\lambda_1^k)p(\lambda_2^l)\times (1-u)\mu_2 \\ \end{align} $$ Note that in the above the indices $i,j,k$ and $l$ serve only to show different beliefs. We do assume that we may have $i = k$ and $j = l$ which corresponds to cases where the belief for the given arrival rate remains the same.

We will have to use some factor to unformize the transitions. Let us call the factor $\gamma$. We think of $\gamma$ as some sample rate. I we observe the continuous time system evolve at intervals of this sample rate then we should be able to observe any event occur and never miss it. This is where the tricky part comes in. We assume the following sample rate: $$ \gamma = \mu_1 + \mu_2 + \max_{i}(\lambda_1^i) + \max_{j}(\lambda_2^j) $$ We note that the upper bound of our beliefs (the largest assumed arrival rate) is accounted for and will be observed. If $\gamma$ is our sample rate, then $\gamma^a$ is our actual transition rate of the system to a change. Hence, denote $\gamma - \gamma^a$ as our fictitious self-transition rate. Thus we have $$\gamma - \gamma^a = (1-u)\mu_1 + u\mu_2$$ We know have transition probabilities as follows: $$ \begin{align} P(x_1+1,\lambda_1^i,x_2,\lambda_2^j\mid x_1,\lambda_1^k,x_2,\lambda_2^l,u) & = \frac{p(\lambda_1^i)p(\lambda_2^j)p(\lambda_1^k)p(\lambda_2^l)\times\lambda_1^i}{\gamma} \\ P(x_1,\lambda_1^i,x_2+1,\lambda_2^j\mid x_1,\lambda_1^k,x_2,\lambda_2^l,u) & = \frac{p(\lambda_1^i)p(\lambda_2^j)p(\lambda_1^k)p(\lambda_2^l)\times\lambda_2^j}{\gamma} \\ P(x_1-1,\lambda_1^i,x_2,\lambda_2^j\mid x_1,\lambda_1^k,x_2,\lambda_2^l,u) & = \frac{p(\lambda_1^i)p(\lambda_2^j)p(\lambda_1^k)p(\lambda_2^l)\times u \mu_1}{\gamma} \\ P(x_1,\lambda_1^i,x_2-1,\lambda_2^j\mid x_1,\lambda_1^k,x_2,\lambda_2^l,u) & = \frac{p(\lambda_1^i)p(\lambda_2^j)p(\lambda_1^k)p(\lambda_2^l)\times (1-u)\mu_2}{\gamma} \\ P(x_1,\lambda_1^i,x_2,\lambda_2^j\mid x_1,\lambda_1^k,x_2,\lambda_2^l,u) & = \frac{p(\lambda_1^i)p(\lambda_2^j)p(\lambda_1^k)p(\lambda_2^l)\times [(1-u)\mu_1 + u\mu_2]}{\gamma} \\ \end{align} $$ There we have it. This model should promise to account for the initial large uncertainty we face in the arrival rates once a change is detected in the Poisson process. I like this model as it separates the probe (Bayesian model for Poisson arrivals) and the actuator (control to implement from the updated policy). It would seem like it is quite an intuitive model and this would make it easier to understand/describe and troubleshoot. It might not be a computationally efficient approach though. Those are just opinions though.

I hope my solution is correct. Thank you for your time.

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