# Limit cycles or stable solutions for k-dimensional piece-wise linear ODEs

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, 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?

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