1
$\begingroup$

As a branch of reinforcement learning, restless multi-armed bandits have been shown PSPACE-HARD but Whittle has offered an implementable solution called the Whittle Index Policy. Weber and Weiss showed that Whittle index is asymptotically optimal under certain conditions involving the global stability of a class of piece-wise linear ODEs.

Define for a fixed real number $0<\alpha<1$, any integer $1\le i\le k$ and any real vector $z=(z_1,\ldots,z_k)$,

$u_i(z):=\min\left\{z_i,\max\left\{0,\alpha-\sum_{h=i+1}^kz_h\right\}\right\}\big/z_i$,

$q_{ji}(z):=u_i(z)q_{ji}^1+(1-u_i(z))q_{ji}^2$,

where $u_i(z)=0$ if $z_i=0$, $(q_{ji}^1)$ and $(q_{ji}^2)$ are $k\times k$ transition rate matrices for some continuous-time Markov processes from state $i$ to $j$ with each column suming to $0$.

Define the path $z(t)$ starting at $z(0)$, $\sum z_i(0)=1$, by the differential equation,

$dz/dt=\sum_{i,j}q_{ji}(z)z_ie_{j}=Q(z)z,\tag{1}$

where $e_{j}$ is the column vector with all elements equal to $0$ except the $j$th element equal to $1$.

Let $q_i^s$ be the $i$th column of matrix $(q_{ji}^s)$ and define region $C_i$ as the closure of the set $\{z:0<u_i(z)<1,\sum z_i=1\}$, Equation (1) can be rewritten in each region $C_i$ as

$dz/dt=A_iz(t)+b,\tag{2}$

where

$b=(1-\alpha)q_i^2+\alpha q_i^1,$

$A_i=(q_1^2-q_i^2|\cdot\cdot\cdot |q_{i-1}^2-q_i^2|0|q_{i+1}^1-q_i^1|\cdot\cdot\cdot|q_k^1-q_i^1).$

So Equation (1) is a piece-wise linear ODE. Weber and Weiss showed that it has a unique globally stable solution if $k=3$ by the Poincaré-Bendixson Theorem. For $k=4$, they also found a numerical example of a limit cycle solution to (1). See more details here and also here.

Q: Under what conditions does (1) have a globally stable solution, or limit cycles, or behave chaotically?

$\endgroup$
1
  • $\begingroup$ Thanks Nawaf for improving the question writing! $\endgroup$
    – KLiu
    Jun 11 at 1:59

0

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.