3
$\begingroup$

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

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

$\textbf{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?

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

$\textbf{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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.