On Joint Convergence of Traffic State and Weight Vector in Learning-Based Dynamic Routing with Value Function Approximation

Let $\mathcal{N}=\{1,2,3,\ldots,N\}$ be the set of parallel servers. Each server $n$ has an exponentially distributed service rate $\mu_{n}$ and job number $x_{n}(t)$ at time $t\in\mathbb{R}_{\geq 0}$. The state of the system is $x=[x_{1},x_{2},\ldots,x_{N}]^{T}$, and the state space is $\mathbb{Z}^{N}_{\geq 0}$. Jobs arrive at origin $S$ according to a Poisson process of rate $\lambda>0$. When a job arrives, it will go to one of the $N$ servers according to a routing policy

That is, $\pi(a|x)$ is the probability of routing the new job to server $a$ conditional on state $x$. This paper focuses on a particular class of routing policies which we call the $weighted~{}shortest~{}queue$ (WSQ) policy. WSQ is based on the approximation for the action value function $\hat{Q}:\mathcal{N}\times\mathbb{Z}^{N}_{\geq 0}\times\mathbb{R}^{N}_{>0}\to\mathbb{R}_{\geq 0}$ defined as:

where $w=[w_{1},w_{2},\ldots,w_{N}]^{T}\in\mathbb{R}^{N}_{>0}$ is the weight vector. For technical convenience, we consider the softmax version of WSQ

where $\iota\in(0,\infty)$ is the temperature of the softmax function. Note that $\pi_{w}(a|x)$ converges to a deterministic policy greedy w.r.t. $\hat{Q}$ as $\iota$ approaches 0 [11].

We say that the traffic in the system is stable if there exists a constant $M<\infty$ such that for any initial condition,

We say that the system is stabilizable if

Note that the above ensures the existence of at least a stabilizing Bernoulli routing policy.

Since routing actions are made only at transition epochs [16, p.72], the routing problem of the parallel queuing system can be formulated as a discrete-time (DT) MDP with countably infinite state space $\mathbb{Z}^{N}_{\geq 0}$ and finite action space $\mathcal{N}$. With a slight abuse of notation, we denote the state and action of the DT MDP as $x[k]\in\mathbb{Z}^{N}_{\geq 0}$ and $a[k]\in\mathcal{N}$, respectively. Specifically, $x[k]=x(t_{k})$, where $t_{k}$ is the $k$-th transition epoch of the continuous-time process. As indicated in Section II-A, the routing policy can be parameterized via weight vector $w\in\mathbb{R}^{N}_{>0}$.

The transition probability $\mathsf{p}(x^{\prime}|x,a)$ of the DT MDP can be derived from the system dynamics in a straightforward manner. Let $e_{i}\in\{0,1\}^{N}$ denote the unit vector such that $e_{i,i}=1$ and $e_{i,j}=0,j\not=i$. Then we have

The one-step random cost of the MDP is given by

where $\|\cdot\|_{1}$ is the 1-norm for $\mathbb{R}^{N}$. Let $\bar{c}(x,a)=\mathsf{E}[c[k+1]|x[k]=x,a[k]=a]$ denote the expected value of cost. The total discounted cost over infinite-horizon process is thus given by

where $\gamma\in(0,1)$ is the discount factor of infinite-horizon MDP. Let $Q^{*}(x,a)$ denote the solution of Bellman optimal equation, that

and let $\pi^{*}$ denote the greedy policy with respect to $Q^{*}$.

Closed-form solution to $Q_{\pi}$ is not easy. Hence, we use the $\hat{Q}$ function defined by (1) as a proxy for $Q_{\pi}$. Motivated by [11, 15], we consider the function approximator as

where $\phi_{n}:\mathcal{N}\times\mathbb{Z}^{N}_{\geq 0}\to\mathbb{R}_{\geq 0}$ and $\{\{\phi_{n}\}_{x,a}\}_{n=1}^{N}$ are linearly independent basis functions. Let $w^{*}$ denote the optimal solution to

where $d^{*}(x)$ is the invariant state distribution under policy $\pi^{*}$. We select quadratic basis functions because $Q_{\pi}$ is non-linear and the quadratic function is one of the simplest non-linear functions. Besides, the analysis is generalizable to polynomials with higher order.

Inspired by [11], let $w[k]$ denote the weight vector at the $k$-th transition epoch, which is updated by an SARSA(0) algorithm

in the above, $\Gamma:\mathbb{R}_{>0}^{N}\to\mathbb{R}_{>0}^{N}$ is a projection operator, $\alpha_{k}$ is the stochastic step size, $\Delta[k]$ is the temporal-difference (TD) error, and $\nabla_{w}\hat{Q}(x[k],a[k];w[k])$ is the gradient, which are specified as follows.

The projection $\Gamma(\cdot)$ is defined with a positive constant $C_{\Gamma}$:

where $\|\cdot\|$ is the standard $2$-norm. Besides, we use $\langle x,y\rangle:=x^{T}y$ denote the standard inner product in Euclidean spaces.

The temporal difference (TD) error $\Delta[k]$ and the gradient $\nabla_{w}\hat{Q}(x[k],a[k];w[k])$ are as follows. Let $\phi=[\phi_{1},\phi_{2},\ldots,\phi_{N}]^{T}$, then we can compactly write

Then, for any $k\in\mathbb{Z}_{\geq 0}$, the TD error and the gradient are collectively given by

The step sizes ${\{\alpha_{k}\}}$ are generated by the following mechanism. We define an auxiliary sequence $\{\tilde{\alpha}_{\tilde{k}};\tilde{k}\in\mathbb{Z}_{\geq 0}^{N}\}$ satisfying the standard step size condition [10]

The step sizes can not be too small to stop the iteration process, while also can not be too large to impede convergence. Let $B_{\alpha}$ denote a finite positive constant and define

Then the step size sequence $\{\alpha_{k}\}$ can be constructed as

where $B_{\alpha}$ is a finite positive constant. That is, $\{\alpha_{k}\}$ consists of zeros and elements from the deterministic sequence $\{\tilde{\alpha}_{\tilde{k}}\}$ as demonstrated in Table I. Thus the weight vector $w[k+1]$ is updated only when the constraint $B_{\alpha}$ is satisfied.

The update equation thus becomes

It is known that SARSA chatters when combined with linear function approximation [10]. We say that Algorithm 1 is convergent to a bounded region if there exists a positive finite constant $B$ such that

for every initial traffic state $x[0]\in\mathbb{Z}_{\geq 0}^{N}$ and every initial weight $w[0]\in\mathbb{R}^{N}_{>0}$.

In this section we construct a Lyapunov function and argue the drift to show the convergence of traffic state $x[k]$, with policy $\pi$ and proper temperature parameter $\iota$. In particular, we considering the Lyapunov function

with the same weight vector as (5). We show that there exist $\iota>0,~{}\epsilon_{v}>0,~{}B_{v}<\infty$ such that for all $x\in\mathbb{Z}^{N}_{\geq 0}$ and for all $w\in\mathbb{R}^{N}_{>0}$

where $\mathcal{L}$ is the infinitesimal generator of the system under the (softmax) WSQ policy.

Let $l_{n}=\mathbb{I}_{\{x_{n}\geq 1\}}$, $m=\arg\min_{n\leq N}w_{n}(2x_{n}+1)$. We have

Suppose that $\iota$ is sufficiently small, since $(l_{n}-1)x_{n}=0$, we have

Then (9) holds when (4) holds. We can use Foster-Lyapunov criterion [14, Theorem 4.3.] conclude (3).

In this section, we show that $\sum_{k=1}^{\infty}\alpha_{k}=\infty$ a.s..

Let use $\tau_{\tilde{\mathcal{X}}}:=\sum_{k=1}^{\infty}\mathbb{I}_{x[k]\in\tilde{\mathcal{X}}}$ denote the occupation time of states $x\in\tilde{\mathcal{X}}$, since the chain is positive Harris recurrent, we have $P(\tau_{\tilde{\mathcal{X}}}=\infty)=1$. Since the arrival rate and service rates are well-defined, we have $P(t_{k+1}-t_{k}\leq B_{T})\geq P_{T}>0$. Then we have

as desired. ∎

In the following, we establish the convergence of $w[k]$ by showing (i) the convergence under fixed-policy evaluation and (ii) the difference among optimal weight vectors due to policy improvement is bounded.

With the above Proposition 1-3, we can analysis the fixed policy performance and bound the difference among distinct policies. For a better elucidation, we use subscript $w^{*}[k]$ denote the invariant steady-state dynamic of the chain under fixed policy $\pi_{w[k]}$, and use subscript $k$ denote the real dynamic at the $k$-th transition. That is $d_{w^{*}[k]}(\cdot)$ denotes the invariant distribution of policy $\pi_{w[k]}$, and $d_{k}(\cdot)$ denotes the state distribution at the $k$-th transition. Suppose that under the fixed policy $\pi_{w[k]}$ and according to [20], we have

where $A_{w^{*}[k]}$ is defined as

Which is negative definite since $\gamma\in(0,1)$. Analogous, we have $b_{w^{*}[k]}=\mathsf{E}_{w^{*}[k]}[\phi^{T}(x,a)c],b_{k}=\mathsf{E}_{k}[\phi^{T}(x,a)c],A_{k}=\mathsf{E}_{k}[\phi(x,a)(\gamma\phi^{T}(x^{\prime},a^{\prime})-\phi^{T}(x,a))]$ and $\mathsf{E}[\delta_{w[k]}(x,w)]=A_{k}w+b_{k}$.

According to [19, Theorem 14.0.1], we have

where $B_{f}$ is a finite positive constant. $\mathsf{p}^{t}_{k}(x^{\prime}|x)$ indicates the transition probability from state $x$ to $x^{\prime}$ after $t$ steps under policy $\pi_{w[k]}$, and there is $\mathsf{p}(x^{\prime}|x)=\sum_{a=1}^{N}\pi(a|x)\mathsf{p}(x^{\prime}|a,x)$. According to [15], with (III-C) holds, the iterative algorithm (7) has a unique solution $w^{*}$ satisfies that $\bar{\delta}(x,w^{*})=0$ under fixed policy. With a little abuse of notation, let $w^{*}_{k}$ denote the solution of

in SGS under fixed policy $\pi_{w[k]}$.

According to the inequality $e^{kx}>\sum_{q=0}^{\infty}\frac{k^{q}x^{q}}{q!}$ and note that there is $\phi(x,a)=\mathcal{O}(x^{2})$, the boundedness of $g_{p}(x)$ defined in Lemma 1 implies the boundedness of $A_{w^{*}[k]},b_{w^{*}[k]}$. With the constructed step size $\{\alpha_{k}\}$, we have $\|A_{w^{*}[k]}\|<B_{\phi}$, $\|b_{w^{*}[k]}\|<B_{r}$, and $\mathsf{E}[\alpha^{2}_{k}\|\delta_{w[k]}(x,w)-\bar{\delta}_{w[k]}(x,w)\|^{2}]\leq\alpha^{2}_{k}B^{2}_{\delta}$, where $B_{\phi},B_{r},B_{\delta}$ are finite positive constants.

Following [11], considering the weights update equation, the auxiliary sequence $\{u[k]\}$ is defined as

Since the $\hat{Q}$ and policy $\pi$ are both linearly related to $w$, we have $w[k]=\Gamma(u[k]),\forall k\in\mathbb{Z}_{\geq 0}$. Let $y^{\prime}=u[k+1]-w^{*}_{k+1},~{}y=w[k]-w^{*}_{k}$, then we have

where $\langle\cdot,\cdot\rangle$ is defined as section II-C. The second item can be rewritten as

For $T_{3}$, we have

Now we are ready to analyze the boundedness of each item. Note that $\alpha_{k}\not=0$ only when $x[k]\in\tilde{\mathcal{X}}$, with [11, Theorem 4.4., Lemma C.5., Lemma D.10.] and the analysis of $\delta_{w[k]}$ and $w^{*}_{k}$, we have