2.1. Existence of optimal policies

The weakly coupled processes can be regarded as a single Markov decision process with finite state and action spaces. Specifically, the state space is $S^n$ and the action space for a given state is the subset of $A^n$ where the coupling constraints (2) hold. More precisely, a state $(i_1, \ldots, i_n) \in S^n$ and a tuple $(a_1, \ldots, a_n) \in A^n$ uniquely determine a vector y of state–action frequencies as in (1). The action space at a given state $(i_1, \ldots, i_n)$ is the subset of $A^n$ such that the state–action frequency vector y satisfies (2).

Consider the sets $\Pi_n^\mathrm{SD} \subset \Pi_n^\mathrm{SR} \subset \Pi_n^\mathrm{HR}$ of stationary and deterministic, stationary and randomized, and history-dependent and randomized policies for the latter Markov decision process; see [Reference Puterman21, Section 2.1.5] for precise definitions. Loosely speaking, stationary policies select actions using solely the current state, whereas the history-dependent policies select actions using the current state and the history of all past states and actions. Randomized policies can be regarded as mappings that assign to each state, or history of states and actions, a probability distribution defined over the action space of the current state; an action is then sampled from this distribution. The policy is called deterministic if the latter probability distribution is always concentrated at a single action.

It follows from [Reference Puterman21, Proposition 8.1.1] that the gain

\begin{equation*} g_n^\pi(s) \,:\!=\, \lim_{T \to \infty} \frac{1}{T}\sum_{t = 0}^{T - 1} \frac{1}{n}\sum_{m = 1}^n \mathbb{E}_s^\pi[r({\boldsymbol{{S}}}_n(t, m), {\boldsymbol{{A}}}_n(t, m))] = \lim_{T \to \infty} \frac{1}{T}\sum_{t = 0}^{T - 1} \sum_{a \in A} \mathbb{E}_s^\pi[{\boldsymbol{{y}}}_n(t, a)]r(a)\end{equation*}

exists for all policies $\pi \in \Pi_n^\mathrm{SR}$ and initial states $s \in S^n$ , i.e. the limits in (3) exist. Here, the expectation is taken with respect to the Markov chain defined by the initial state and the stationary and randomized policy. Also, [Reference Puterman21, Theorems 9.1.7 and 9.1.8] imply that

\begin{equation*} g_n^*(s) \,:\!=\, \sup\nolimits_{\pi \in \Pi_n^\mathrm{SD}} g_n^\pi(s)\end{equation*}

is attained simultaneously for all $s \in S^n$ by some $\pi^* \in \Pi_n^\mathrm{SD}$ , and [Reference Puterman21, Theorem 9.1.6] yields

\begin{equation*} g_n^*(s) = \sup_{\pi \in \Pi_n^\mathrm{HR}} \limsup_{T \to \infty} \frac{1}{T}\sum_{t = 0}^{T - 1} \frac{1}{n}\sum_{m = 1}^n \mathbb{E}_s^\pi[r({\boldsymbol{{S}}}_n(t, m), {\boldsymbol{{A}}}_n(t, m))].\end{equation*}

In other words, there exists a stationary and deterministic policy $\pi^*$ that has maximal gain across all the initial states. This policy maximizes the expressions in (3) over the set of policies for which the limits exist, and provides an expected average reward not smaller than any history-dependent and randomized policy, as stated in the previous equation.

An optimal policy $\pi^*$ does not typically admit a closed-form expression. While $\pi^*$ can be computed numerically using dynamic programming, the computation time is exponential in the number of processes n and thus exceedingly large in many applications. This creates an incentive for simple policies that perform well when n is large.

2.2. Fluid relaxation

In this paper we analyze a class of policies that are easy to compute and asymptotically optimal, i.e. they achieve the maximum gain as $n \to \infty$ . For this purpose we adopt the following assumption throughout the paper. It says that (2) is consistent in the limit.

Assumption 1. For each $a \in A$ , the following limits exist and are finite:

\begin{equation*} C(a) \,:\!=\, \lim_{n \to \infty} C_n(a), \qquad d \,:\!=\, \lim_{n \to \infty} d_n, \qquad E(a) \,:\!=\, \lim_{n \to \infty} E_n(a), \qquad f \,:\!=\, \lim_{n \to \infty} f_n. \end{equation*}

Let $e \in \mathbb{R}^S$ denote the column vector with each of its entries equal to one. The processes of state and state–action frequencies ${\boldsymbol{{x}}}_n$ and ${\boldsymbol{{y}}}_n$ take values in

\begin{equation*} X \,:\!=\, \{x \in [0, 1]^{S} \colon x e = 1\}, \qquad Y \,:\!=\, \Bigg\{y \in [0, 1]^{S \times A} \colon \sum_{a \in A} y(a)e = 1\Bigg\},\end{equation*}

respectively; x and $y(a) = (y(i, a) \colon i \in S)$ are regarded as row vectors. For each $a \in A$ , let P(a) denote the matrix such that the entry (i, j) is $p(j \mid i, a)$ . The following linear program will play an important role throughout the paper.

Definition 1. We call fluid relaxation the following optimization problem:

(4) \begin{align} & \underset{y \in Y}{\text{maximize}} \quad \sum_{a \in A} y(a)r(a) \nonumber\\ & \text{subject to} \quad \sum_{a \in A} y(a)P(a) = \sum_{a \in A} y(a), \sum_{a \in A} y(a)C(a) = d, \qquad \sum_{a \in A} y(a)E(a) \preceq f. \end{align}

Its optimal value is denoted by $g_r$ .

The optimization variables y(i, a) can be interpreted as

\begin{equation*} \lim_{n \to \infty} \lim_{T \to \infty} \frac{1}{T}\sum_{t = 0}^{T - 1} \mathbb{E}[{\boldsymbol{{y}}}_n(t, i, a)]\end{equation*}

when the limits exist. The first constraint in (4) is a balance equation that is satisfied by long-run averages as defined by the inner limit; see the proof of the next proposition. The other constraints say that these long-run averages must satisfy (2) as $n \to \infty$ . Moreover, the objective of the problem can be interpreted as the limiting gain.

The following proposition says that $g_r$ is an upper bound for the gain of the weakly coupled Markov decision processes as $n \to \infty$ . An intuitive explanation of this result, based on the above interpretation of (4), is that the constraints (2) must hold at each time and for each sample path, whereas the constraints of (4) are only imposed on long-run averages, thereby relaxing the problem. The proof of the proposition is standard but we provide it in Appendix A for completeness.

Proposition 1. For each $a \in A$ and some fixed n, suppose that

(5) \begin{equation} C_n(a) = C(a), \qquad d_n = d, \qquad E_n(a) = E(a), \qquad f_n = f. \end{equation}

Then $g_n^*(s) \leq g_r$ for all $s \in S^n$ . In the general case where (5) may not hold, we have

(6) \begin{equation} \limsup_{n \to \infty} \sup\nolimits_{s \in S^n} g_n^*(s) \leq g_r. \end{equation}

In the following two sections we will establish that the inequality in (6) is in fact an equality under mild assumptions. Moreover, we will provide stationary policies for the n weakly coupled processes with gains that approach $g_r$ as $n \to \infty$ .

3.1. Mean-field limit

Consider discrete controls $\phi_n$ associated with a fluid control $\phi$ . As observed earlier, the joint distribution of the state and state–action frequency processes associated with any policy that realizes $\phi_n$ is completely determined by $\phi_n$ and the initial state frequencies. Further, ${\boldsymbol{{x}}}_n$ is a discrete-time Markov chain and ${\boldsymbol{{y}}}_n(t) = \phi_n({\boldsymbol{{x}}}_n(t))$ for all $t \geq 0$ . Below we provide a convenient construction of these two processes.

For this purpose we consider a collection $\{B_t^l(j \mid i, a) \colon l \geq 1,\, t \geq 1,\, i, j \in S,\, a \in A\}$ of Bernoulli random variables with the following two properties. First, $B_t^l(j \mid i, a) = 1$ and $B_t^l(k \mid i, a) = 0$ for all $k \neq j$ with probability $p(j \mid i, a)$ for all $l \geq 1$ , $t \geq 1$ , $i \in S$ , and $a \in A$ . Second, the random vectors $(B_t^l(j \mid i, a) \colon j \in S)$ are independent across $l \geq 1$ , $t \geq 1$ , $i \in S$ , and $a \in A$ . The same collection of random variables can be used to construct the state and state–action frequency processes for any given n, and thus the notation does not account for the number of processes n.

At each time t, there are $n{\boldsymbol{{y}}}_n(t, i, a)$ processes in state i with action a selected, which we arrange according to their indexes. We postulate that the process with the lth largest index is in state j at $t + 1$ if $B_{t + 1}^l(j \mid i, a) = 1$ , which endows ${\boldsymbol{{x}}}_n(t + 1)$ with the desired distribution. More specifically, we construct ${\boldsymbol{{x}}}_n$ and ${\boldsymbol{{y}}}_n$ recursively as functions of ${\boldsymbol{{x}}}_n(0)$ and the above Bernoulli random variables such that, for each $t \geq 0$ ,

\begin{equation*} {\boldsymbol{{y}}}_n(t) = \phi_n({\boldsymbol{{x}}}_n(t)), \qquad {\boldsymbol{{x}}}_n(t + 1, j) = \frac{1}{n}\sum_{i \in S} \sum_{a \in A} \sum_{l = 1}^{n{\boldsymbol{{y}}}_n(t, i, a)} B_{t + 1}^l(j \mid i, a) \quad \text{for all} \ j \in S.\end{equation*}

We further define

\begin{equation*} {\boldsymbol{{z}}}_n(t + 1, j) \,:\!=\, \frac{1}{n}\sum_{i \in S} \sum_{a \in A} \sum_{l = 1}^{n{\boldsymbol{{y}}}_n(t, i, a)} \big[B_{t + 1}^l(j \mid i, a) - p(j \mid i, a) \big]\end{equation*}

for all $t \geq 0$ and $j \in S$ . Then we can write

(8) \begin{equation} {\boldsymbol{{x}}}_n(t + 1) = {\boldsymbol{{z}}}_n(t + 1) + \sum_{a \in A} {\boldsymbol{{y}}}_n(t, a)P(a) \quad \text{for all} \ t \geq 0.\end{equation}

Clearly, ${\boldsymbol{{z}}}_n(t)$ has mean zero for all $t \geq 1$ ; it is possible to check that ${\boldsymbol{{z}}}_n$ is in fact a martingale difference with respect to the natural filtration, but this will not be used explicitly. The next lemma bounds the variance of ${\boldsymbol{{z}}}_n(t)$ and is proved in Appendix A.

Lemma 1. Consider the constants

\begin{equation*} q_{\min}(j) \,:\!=\, \min_{i \in S, a \in A}[1 - p(j \mid i, a)] \leq \max_{i \in S, a \in A}[1 - p(j \mid i, a)] =: q_{\max}(j) \quad \text{for all} \ j \in S. \end{equation*}

For each $t \geq 1$ and $j \in S$ , we have

\begin{equation*} \frac{q_{\min}(j)}{n}\mathbb{E}[{\boldsymbol{{x}}}_n(t, j)] \leq \mathbb{E}\big[{\boldsymbol{{z}}}_n^2(t, j)\big] \leq \frac{q_{\max}(j)}{n}\mathbb{E}[{\boldsymbol{{x}}}_n(t, j)]. \end{equation*}

The lemma will be used in the proof of the following proposition, which establishes that the fluid trajectories defined by the fluid control $\phi$ are the mean-field limit of the state and state–action frequency processes ${\boldsymbol{{x}}}_n$ and ${\boldsymbol{{y}}}_n$ determined by $\phi_n$ . More precisely, the latter processes converge weakly to fluid trajectories provided that the initial state frequency vectors ${\boldsymbol{{x}}}_n(0)$ have a limit in distribution as $n \to \infty$ .

Proof. We proceed by induction, assuming that ${\boldsymbol{{x}}}_n(t) \Rightarrow {\boldsymbol{{x}}}(t)$ as $n \to \infty$ and then showing that ${\boldsymbol{{y}}}_n(t) \Rightarrow {\boldsymbol{{y}}}(t)$ and ${\boldsymbol{{x}}}_n(t + 1) \Rightarrow {\boldsymbol{{x}}}(t + 1)$ . Clearly, the assumption holds for $t = 0$ .

Assume that ${\boldsymbol{{x}}}_n(t) \Rightarrow {\boldsymbol{{x}}}(t)$ as $n \to \infty$ and let $\zeta \colon \mathbb{R}^{S \times A} \times X \longrightarrow \mathbb{R}^{S \times A}$ be defined by $\zeta(w, x) \,:\!=\, w + \phi(x)$ . If we let ${\boldsymbol{{w}}}_n(t) \,:\!=\, \phi_n({\boldsymbol{{x}}}_n(t)) - \phi({\boldsymbol{{x}}}_n(t))$ , then ${\boldsymbol{{y}}}_n(t) = \zeta({\boldsymbol{{w}}}_n(t), {\boldsymbol{{x}}}_n(t))$ . Moreover, ${\boldsymbol{{w}}}_n(t) \Rightarrow 0$ as $n \to \infty$ by Definition 3, because $||{\boldsymbol{{w}}}_n(t)|| \leq \max_{x \in X_n}||\phi_n(x) - \phi(x)||$ . By [Reference Billingsley3, Theorem 3.1], we have $({\boldsymbol{{w}}}_n(t), {\boldsymbol{{x}}}_n(t)) \Rightarrow (0, {\boldsymbol{{x}}}(t))$ as $n \to \infty$ ; see [Reference Goldsztajn, Borst and Van Leeuwaarden13, Lemma 9] for further details. The continuous mapping theorem yields ${\boldsymbol{{y}}}_n(t) \Rightarrow \zeta(0, {\boldsymbol{{x}}}(t)) = {\boldsymbol{{y}}}(t)$ .

Lemma 1 implies that ${\boldsymbol{{z}}}_n(t + 1) \Rightarrow 0$ as $n \to \infty$ since

\begin{equation*} \mathbb{P}\big(||{\boldsymbol{{z}}}_n(t + 1)||_2^2 \geq \varepsilon\big) \leq \frac{\mathbb{E}\big[||{\boldsymbol{{z}}}_n(t + 1)||_2^2 \big]}{\varepsilon} \leq \frac{\mathbb{E}[||{\boldsymbol{{x}}}_n(t)||_1]}{n\varepsilon} \leq \frac{1}{n\varepsilon} \quad \text{for all} \ \varepsilon > 0. \end{equation*}

Therefore, $({\boldsymbol{{y}}}_n(t), {\boldsymbol{{z}}}_n(t + 1)) \Rightarrow ({\boldsymbol{{y}}}(t), 0)$ as $n \to \infty$ by [Reference Billingsley3, Theorem 3.1]. Consider now the continuous function $\eta \colon \mathbb{R}^{S \times A} \times \mathbb{R}^S \longrightarrow \mathbb{R}^S$ such that $\eta(y, z) \,:\!=\, z + \sum_{a \in A} y(a)P(a)$ . Then ${\boldsymbol{{x}}}_n(t + 1) = \eta({\boldsymbol{{y}}}_n(t), {\boldsymbol{{z}}}_n(t + 1))$ by (8), and it follows from the continuous mapping theorem that ${\boldsymbol{{x}}}_n(t + 1) \Rightarrow \eta({\boldsymbol{{y}}}(t), 0) = {\boldsymbol{{x}}}(t + 1)$ as $n \to \infty$ .

3.2. Asymptotic optimality result

The next lemma assumes that the fluid control $\phi$ is continuous and satisfies (7). Under these assumptions, the lemma establishes that the gain achieved by the discrete control $\phi_n$ approaches the optimal value of the fluid relaxation $g_r$ as $n \to \infty$ whenever ${\boldsymbol{{x}}}_n(0)$ has a stationary distribution for each n; at least one stationary distribution for the Markov chain ${\boldsymbol{{x}}}_n$ always exists since its state space is finite, but this distribution may not be unique. The proof of the lemma relies on the mean-field limit obtained in Proposition 2.

Lemma 2. Assume that $\phi$ is continuous and that every fluid trajectory satisfies

\begin{equation*} \lim_{t \to \infty} \sum_{a \in A} {\boldsymbol{{y}}}(t, a) r(a) = g_r, \end{equation*}

regardless of the initial condition. Also, assume that ${\boldsymbol{{x}}}_n(0)$ is distributed as a stationary distribution of ${\boldsymbol{{x}}}_n$ , and thus ${\boldsymbol{{x}}}_n$ is stationary. Then

(9) \begin{equation} \lim_{n \to \infty}\sum_{a \in A}\mathbb{E}[{\boldsymbol{{y}}}_n(t, a)]r(a) = g_r \quad \text{for all} \ t \geq 0. \end{equation}

Proof. Consider the following limits in distribution:

(10) \begin{equation} \sum_{a \in A} {\boldsymbol{{y}}}_n(t, a)r(a) \Rightarrow g_r \quad \text{as} \ n \to \infty \ \text{for all} \ t \geq 0. \end{equation}

For each $t \geq 0$ , the sequence of random variables on the left-hand side, with t fixed and n varying, is uniformly integrable since it is uniformly bounded:

(11) \begin{equation} \Bigg|\sum_{a \in A}{\boldsymbol{{y}}}_n(t, a)r(a)\Bigg| \leq |S| |A| \max_{i \in S, a \in A} |r(i, a)|. \end{equation}

We conclude that (10) implies (9), so it suffices to prove (10). Because ${\boldsymbol{{x}}}_n$ is stationary, the following random variables are identically distributed:

\begin{equation*} \sum_{a \in A} {\boldsymbol{{y}}}_n(t, a)r(a) = \sum_{a \in A} \phi_n({\boldsymbol{{x}}}_n(t), a)r(a) \sim \sum_{a \in A} \phi_n({\boldsymbol{{x}}}_n(0), a)r(a) = \sum_{a \in A} {\boldsymbol{{y}}}_n(0, a)r(a). \end{equation*}

Hence, it is enough to prove that (10) holds for $t = 0$ .

It follows from (11) that $\big\{\sum_{a \in A} {\boldsymbol{{y}}}_n(0, a)r(a) \colon n \geq 1\big\}$ is tight, and thus every subsequence has a further subsequence that converges weakly. We will establish (10) for $t = 0$ by showing that the weak limit of every convergent subsequence is $g_r$ , i.e. the random variable equal to $g_r$ with probability 1.

Suppose that $\mathcal{L} \subset \mathbb{N}$ and $g_{\mathcal{L}}$ are such that

(12) \begin{equation} \sum_{a \in A} {\boldsymbol{{y}}}_l(0, a)r(a) \Rightarrow g_{\mathcal{L}} \quad \text{as} \ l \to \infty \ \text{while} \ l \in \mathcal{L}. \end{equation}

More specifically, $g_{\mathcal{L}}$ is the limit associated with the convergent subsequence indexed by $\mathcal{L}$ , and the subscript indicates that this limit could in principle depend on the specific set of indexes $\mathcal{L}$ . The random variables $\{{\boldsymbol{{x}}}_l(0) \colon l \in \mathcal{L}\}$ are tight because they are all supported on the compact set X. Therefore, we may assume without any loss of generality that there exists a random variable $x_{\mathcal{L}}$ such that ${\boldsymbol{{x}}}_l(0) \Rightarrow x_{\mathcal{L}}$ as $l \to \infty$ .

Define $\xi \colon \mathbb{R} \times \mathbb{R}^S \longrightarrow \mathbb{R}$ by $\xi(w, x) \,:\!=\, w + \sum_{a \in A} \phi(x, a)r(a)$ . Note that $\xi$ is a continuous function and satisfies

\begin{equation*} \sum_{a \in A} {\boldsymbol{{y}}}_l(0, a)r(a) = \xi\Bigg(\sum_{a \in A}\phi_l({\boldsymbol{{x}}}_l(0), a)r(a) - \sum_{a \in A}\phi({\boldsymbol{{x}}}_l(0), a)r(a), {\boldsymbol{{x}}}_l(0)\Bigg). \end{equation*}

The first argument of $\xi$ converges to zero in probability as $l \to \infty$ by Definition 3, because

\begin{equation*} \Bigg|\sum_{a \in A}\phi_l({\boldsymbol{{x}}}_l(0), a)r(a) - \sum_{a \in A}\phi({\boldsymbol{{x}}}_l(0), a)r(a)\Bigg| \leq \max_{x \in X_l}||\phi_l(x) - \phi(x)||\sum_{a \in A}||r(a)||. \end{equation*}

It follows from [Reference Billingsley3, Theorem 3.1] and the continuous mapping theorem that

\begin{equation*} \sum_{a \in A} {\boldsymbol{{y}}}_l(0, a)r(a) \Rightarrow \xi(0, x_{\mathcal{L}}) = \sum_{a \in A} \phi(x_{\mathcal{L}}, a)r(a) \quad \text{as} \ l \to \infty \ \text{while} \ l \in \mathcal{L}. \end{equation*}

We conclude from (12) that the following equality in distribution holds:

\begin{equation*} g_{\mathcal{L}} \sim \sum_{a \in A} \phi(x_{\mathcal{L}}, a)r(a). \end{equation*}

Suppose that $x_{\mathcal{L}}$ is defined on a set $\Omega$ , and for each $\omega \in \Omega$ let $\{{\boldsymbol{{x}}}(\omega, t), {\boldsymbol{{y}}}(\omega, t) \colon t \geq 0\}$ be the fluid trajectory starting at ${\boldsymbol{{x}}}(\omega, 0) = x_{\mathcal{L}}(\omega)$ . It follows from Proposition 2 that ${\boldsymbol{{x}}}_l(t) \Rightarrow {\boldsymbol{{x}}}(t)$ as $l \to \infty$ for all $t \geq 0$ . Because ${\boldsymbol{{x}}}_l$ is a stationary process, ${\boldsymbol{{x}}}_l(t) \sim {\boldsymbol{{x}}}_l(0)$ for each $t \geq 0$ , and this implies that ${\boldsymbol{{x}}}(t) \sim x_{\mathcal{L}}$ . We conclude that

\begin{equation*} \sum_{a \in A} {\boldsymbol{{y}}}(t, a)r(a) = \sum_{a \in A}\phi({\boldsymbol{{x}}}(t), a)r(a) \sim \sum_{a \in A} \phi(x_{\mathcal{L}}, a)r(a) \sim g_{\mathcal{L}} \quad \text{for all} \ t \geq 0. \end{equation*}

By assumption, $\lim_{t \to \infty} \sum_{a \in A} {\boldsymbol{{y}}}(t, a)r(a) = g_r$ with probability 1. In particular, the limit also holds in distribution, which implies that $g_{\mathcal{L}} \sim g_r$ , i.e. $g_{\mathcal{L}} = g_r$ with probability 1. This completes the proof of the lemma.

We can now prove the asymptotic optimality result.

Theorem 1. Suppose that $\phi$ is continuous and that every fluid trajectory satisfies

\begin{equation*} \lim_{t \to \infty} \sum_{a \in A} {\boldsymbol{{y}}}(t, a) r(a) = g_r, \end{equation*}

regardless of the initial condition. For arbitrary and possibly random vectors ${\boldsymbol{{x}}}_n(0)$ of initial state frequencies, the gain achieved by the discrete controls $\phi_n$ approaches the optimal value $g_r$ of the fluid relaxation as $n \to \infty$ . Specifically,

\begin{equation*} \lim_{n \to \infty} \lim_{T \to \infty} \frac{1}{T}\sum_{t = 0}^{T - 1} \sum_{a \in A} \mathbb{E}[{\boldsymbol{{y}}}_n(t, a)]r(a) = g_r. \end{equation*}

Proof. By [Reference Puterman21, Proposition 8.1.1], there exist random vectors $x_n^s$ such that the distribution of $x_n^s$ is stationary for the Markov chain ${\boldsymbol{{x}}}_n$ and satisfies

\begin{equation*} \lim_{T \to \infty} \frac{1}{T}\sum_{t = 0}^{T - 1} \sum_{a \in A} \mathbb{E}[{\boldsymbol{{y}}}_n(t, a)]r(a) = \sum_{a \in A} \mathbb{E}[\phi_n(x_n^s, a)]r(a). \end{equation*}

More precisely, the distribution of $x_n^s$ is a convex combination of the rows of the limiting matrix associated with the Markov chain ${\boldsymbol{{x}}}_n$ . If ${\boldsymbol{{x}}}_n(0)$ is deterministic, then the distribution of $x_n^s$ is given by the row of the limiting matrix associated with state ${\boldsymbol{{x}}}_n(0)$ . In general, the distribution of $x_n^s$ is the convex combination of the rows such that the weight of the row associated with state x is the probability that ${\boldsymbol{{x}}}_n(0) = x$ . The law of $x_n^s$ is stationary because the rows of the limiting matrix define stationary distributions.

Consider now the stationary Markov chains ${\boldsymbol{{x}}}_n$ with initial distributions $x_n^s$ . Then

\begin{equation*} \lim_{n \to \infty} \sum_{a \in A} \mathbb{E}[\phi_n(x_n^s, a)]r(a) = \lim_{n \to \infty} \sum_{a \in A} \mathbb{E}[{\boldsymbol{{y}}}_n(0, a)]r(a) = g_r \end{equation*}

by Lemma 2, which completes the proof.

The following corollary is a straightforward consequence of Theorem 1.

Corollary 1. Let $y^*$ be an optimal solution of the fluid relaxation (4), and suppose that $\phi$ is continuous and such that all fluid trajectories satisfy

(13) \begin{equation} \lim_{t \to \infty} {\boldsymbol{{y}}}(t) = y^*, \end{equation}

regardless of the initial condition. For arbitrary and possibly random initial state frequency vectors ${\boldsymbol{{x}}}_n(0)$ , the limit of the gain achieved by $\phi_n$ is given by

\begin{equation*} \lim_{n \to \infty} \lim_{T \to \infty} \frac{1}{T}\sum_{t = 0}^{T - 1} \sum_{a \in A} \mathbb{E}[{\boldsymbol{{y}}}_n(t, a)]r(a) = g_r. \end{equation*}

In the context of multi-armed restless bandits, global attractivity properties that are analogous to (13) have been used to establish the asymptotic optimality of the Whittle index and the LP-priority policies in [Reference Gast, Gaujal and Yan9, Reference Gast, Gaujal and Yan10, Reference Verloop23, Reference Weber and Weiss24], respectively; further conditions are also required, such as the single-arm and multi-arm problems being unichain. These global attractivity properties must be checked for each problem instance and there are remarkably simple instances where the property fails. One example, where the single-arm problem has three states and is ergodic, is given in [Reference Gast, Gaujal and Yan8] and is considered in Section 5.

In the following section we will construct continuous fluid controls that satisfy (13) when a technical condition holds. Unlike the global attractivity properties required by the Whittle index and LP-priority policies, our condition holds automatically for a broad class of problems. In particular, the condition always holds for multi-armed restless bandit problems where the unconstrained single-arm problem admits a policy that is unichain, aperiodic, and such that its unique irreducible class contains the set defined below.

Definition 4. Given an optimal solution $y^*$ of the fluid relaxation (4), let

(14) \begin{equation} x^* = \sum_{a \in A} y^*(a), \qquad S_+^* \,:\!=\, \{i \in S \colon x^*(i) > 0\}. \end{equation}

We emphasize that the above-mentioned policy for the single-arm problem need not comply with the constraints in (2) nor maximize the accumulated reward in any way. The only requirements are that the policy is unichain, aperiodic, and such that all transient states are outside of $S_+^*$ . Moreover, we establish that such a policy exists if and only if the policy that selects actions uniformly at random has the latter properties. Therefore, our asymptotic optimality condition is straightforward to check.

4.1. General constraints

We adopt the following notation for the composition of functions:

\begin{equation*} \eta \circ \zeta(x) \,:\!=\, \eta(\zeta(x)), \qquad \zeta^0(x) \,:\!=\, x, \qquad \zeta^k(x) \,:\!=\, \zeta \circ \zeta^{k - 1}(x) \quad \text{for all} \ k \geq 1,\end{equation*}

whenever the expressions on the right-hand sides are well-defined.

Condition 1. The fluid control $\psi$ is continuous. Moreover, consider the set

\begin{equation*} Z \,:\!=\, \{x \in X \colon \beta(x) = 0\} = \{x \in X \colon x(i) = 0\ \text{for some}\ i \in S_+^*\}. \end{equation*}

For each $z \in Z$ , there exists $t \geq 1$ such that $(L \circ \psi)^t(z) \notin Z$ .

Observe that the assumptions of Corollary 1 cannot be satisfied if the fluid control does not satisfy Condition 1. Indeed, a fluid control that does not satisfy Condition 1 is either discontinuous or such that some fluid trajectory is contained in Z and thus does not satisfy (13). The following theorem proves that the existence of a fluid control that satisfies Condition 1 is not only necessary for Corollary 1 but also sufficient.

Proof. As noted earlier, it is straightforward to check that $\phi$ is a fluid control. Further, Lemma 3 and Condition 1 imply that $\phi$ is continuous at x for all $x \neq x^*$ . In order to prove that $\phi$ is continuous at $x^*$ , suppose that $x_k \to x^*$ as $k \to \infty$ with $x_k \in X \setminus \{x^*\}$ . Then

\begin{equation*} \lim_{k \to \infty} \beta(x_k) = 1, \qquad ||\psi([1 - \beta(x_k)]^{-1}[x_k - \beta(x_k)x^*])||_1 = 1 \quad \text{for all} \ k \geq 1. \end{equation*}

It follows that $\phi(x_k) \to y^* = \phi(x^*)$ as $k \to \infty$ , and thus $\phi$ is continuous.

It only remains to prove that every fluid trajectory satisfies that ${\boldsymbol{{y}}}(t) \to y^*$ as $t \to \infty$ , and for this purpose it suffices to show that $\beta({\boldsymbol{{x}}}(t)) \to 1$ as $t \to \infty$ . We will do this by assuming that the latter property does not hold and arriving at a contradiction.

Suppose, then, that $\beta({\boldsymbol{{x}}}(t)) \nrightarrow 1$ as $t \to \infty$ for some fluid trajectory, and note that the function $t \mapsto \beta({\boldsymbol{{x}}}(t))$ is nondecreasing since

\begin{align*} {\boldsymbol{{x}}}(t + 1) & = L\circ\phi({\boldsymbol{{x}}}(t)) \\ & = \beta({\boldsymbol{{x}}}(t))x^* + L([1 - \beta({\boldsymbol{{x}}}(t))] \psi([1 - \beta({\boldsymbol{{x}}}(t))]^{-1}[{\boldsymbol{{x}}}(t) - \beta({\boldsymbol{{x}}}(t))x^*])), \end{align*}

where the last term is in $X \subset \mathbb{R}_+^S$ . Therefore, there exists

(16) \begin{equation} \gamma \,:\!=\, \lim_{t \to \infty} \beta({\boldsymbol{{x}}}(t)) < 1. \end{equation}

Because X is a compact set, there exist $x_\gamma \in X$ and some sequence $\{t_k \in \mathbb{N} \colon k \geq 1\}$ such that ${\boldsymbol{{x}}}(t_k) \to x_\gamma$ as $k \to \infty$ . Furthermore, $\beta(x_\gamma) = \lim_{k \to \infty}\beta({\boldsymbol{{x}}}(t_k)) = \gamma$ . Let $\{{\boldsymbol{{x}}}_\gamma(t), {\boldsymbol{{y}}}_\gamma(t) \colon t \in \mathbb{N}\}$ be the fluid trajectory such that ${\boldsymbol{{x}}}_\gamma(0) = x_\gamma$ . Then

(17) \begin{equation} \beta({\boldsymbol{{x}}}_\gamma(t)) = \gamma \quad \text{for all} \ t \in \mathbb{N}. \end{equation}

Indeed, assume that $\beta({\boldsymbol{{x}}}_\gamma(t)) > \gamma$ for some $t \geq 0$ , and note that

\begin{equation*} \lim_{k \to \infty} {\boldsymbol{{x}}}(t + t_k) = \lim_{k \to \infty}(L \circ \phi)^t({\boldsymbol{{x}}}(t_k)) = (L \circ \phi)^t(x_\gamma) = {\boldsymbol{{x}}}_\gamma(t) \end{equation*}

because $\phi$ is continuous. If (17) failed, then (16) would fail as well since

\begin{equation*} \lim_{k \to \infty}\beta({\boldsymbol{{x}}}(t + t_k)) = \beta({\boldsymbol{{x}}}_\gamma(t)) > \gamma. \end{equation*}

Define ${\boldsymbol{{z}}}(t) \,:\!=\, (1 - \gamma)^{-1}[{\boldsymbol{{x}}}_\gamma(t) - \gamma x^*] \in Z$ for all $t \in \mathbb{N}$ . Then

\begin{align*} {\boldsymbol{{z}}}(t + 1) & = (1 - \gamma)^{-1}[{\boldsymbol{{x}}}_\gamma(t + 1) - \gamma x^*] \\ & = (1 - \gamma)^{-1}[L\circ\phi({\boldsymbol{{x}}}_\gamma(t)) - \gamma x^*] \\ & = (1 - \gamma)^{-1}[\gamma x^* + L((1 - \gamma)\psi((1 - \gamma)^{-1}[{\boldsymbol{{x}}}_\gamma(t) - \gamma x^*])) - \gamma x^*] \\ & = L \circ \psi({\boldsymbol{{z}}}(t)) = (L\circ\psi)^{t + 1}({\boldsymbol{{z}}}(0)) \quad \text{for all} \ t \in \mathbb{N}, \end{align*}

where we used the linearity of L. Condition 1 implies that ${\boldsymbol{{z}}}(t) \notin Z$ for some $t \geq 1$ , but this is only possible if $\beta({\boldsymbol{{x}}}_\gamma(t)) > \gamma$ and thus contradicts (17).

The following definition can be helpful for checking Condition 1.

Definition 5. Let $\pi \,:\!=\, \{\pi(a \mid i) \in [0, 1] \colon i \in S, a \in A\}$ be a set of values such that

\begin{equation*} \sum_{a \in A} \pi(a \mid i) = 1 \quad \text{for all} \ i \in S. \end{equation*}

Consider diagonal matrices $\{D_\pi(a) \colon a \in A\}$ such that $D_\pi(i, i, a) \,:\!=\, \pi(a \mid i)$ for all $i \in S$ and $a \in A$ . We may define a function $\psi_1 \colon X \longrightarrow Y$ by letting $\psi_1(x, a) \,:\!=\, xD_\pi(a)$ for all $x \in X$ and $a \in A$ , where $\psi_1(x, a)$ is short-hand notation for y(a) when $\psi_1(x) = y$ . The fluid control $\psi$ is purely based on $\pi$ if $\psi = \psi_1$ , and we say that $\psi$ is partially based on $\pi$ if there exist a constant $\gamma \in (0, 1)$ and a function $\psi_2 \colon X \longrightarrow Y$ such that

(18) \begin{equation} \psi(x) = \gamma \psi_1(x) + (1 - \gamma)\psi_2(x) \quad \text{for all} \ x \in X; \end{equation}

i.e. $\psi$ can be expressed as a convex combination of $\psi_1$ and $\psi_2$ .

The set of constants $\pi$ corresponds to a stationary policy for a single-process problem without constraints. In particular, $\pi(a \mid i)$ can be interpreted as the probability that action a is selected whenever the process is in state i. If $\psi$ is purely based on $\pi$ , then

\begin{equation*} x\sum_{a \in A} D_\pi(a)C(a) = d, \qquad x\sum_{a \in A} D_\pi(a)E(a) \preceq f\end{equation*}

must hold for all $x \in X$ for $\psi$ to be a fluid control. However, these conditions need not hold when $\psi$ is only partially based on $\pi$ as in (18) because the function $\psi_2$ can help to satisfy the conditions in Definition 2, particularly the constraints of the problem.

The following corollary follows from Theorem 2.

Proof. It is enough to establish that Condition 2 implies Condition 1. For this purpose we will prove that, for all $z \in X$ and $k \geq 0$ ,

(19) \begin{equation} (L \circ \psi)^k(z) = \gamma^k z P_\pi^k + (1 - \gamma) w_k(z), \quad \text{with} \ w_k(z) \in \mathbb{R}_+^S. \end{equation}

Condition 2 implies that $P_\pi$ has a unique stationary distribution $x_\pi \in X$ that assigns positive probability to all $i \in S_+^*$ . Furthermore, $z P_\pi^k \to x_\pi$ as $k \to \infty$ for each initial distribution $z \in X$ . Therefore, there always exists $k \geq 1$ such that the right-hand side of (19) assigns positive probability to all $i \in S_+^*$ , and thus $(L \circ \psi)^k(z) \notin Z$ .

It only remains to prove that (19) holds for all $k \geq 0$ . For this purpose fix $z \in X$ and note that (19) holds for $k = 0$ . We now proceed by induction, assuming that (19) holds for some k and showing that it then holds for $k + 1$ as well. First, note that

\begin{equation*} (L \circ \psi)^{k + 1}(z) = \gamma L(\psi_1((L \circ \psi)^k(z))) + (1 - \gamma) L(\psi_2((L \circ \psi)^k(z))). \end{equation*}

We may compute the first term on the right-hand side by noting that

\begin{equation*} L\circ\psi_1(x) = \sum_{a \in A} x D_\pi(a)P(a) = x P_\pi \quad \text{for all} \ x \in X. \end{equation*}

Since (19) holds for k, the previous equation implies that

\begin{align*} \gamma L(\psi_1((L \circ \psi)^k(z))) & = \gamma L(\psi_1(\gamma^k z P_\pi^k + (1 - \gamma) w_k(z))) \\ & = \gamma^{k + 1} z P_\pi^{k + 1} + \gamma (1 - \gamma)w_k(z) P_\pi. \end{align*}

It follows that (19) holds for $k + 1$ with

\begin{equation*} w_{k + 1}(z) \,:\!=\, \gamma (1 - \gamma)w_k(z) P_\pi + (1 - \gamma) L(\psi_2((L \circ \psi)^k(z))). \end{equation*}

The first term on the right-hand side is in $\mathbb{R}_+^S$ since $w_k(z) \in \mathbb{R}_+^S$ and $P_\pi$ has nonnegative entries. Also, the second term is in $\mathbb{R}_+^S$ as well since $L \circ \psi$ and $L \circ \psi_2$ map X into X.

Suppose that the fluid control $\phi$ is defined as in (15) in terms of some fluid control $\psi$ that satisfies Condition 2. The functions $\psi_1$ and $\psi_2$ defining $\psi$ play different roles in ensuring that the assumptions of Corollary 1 hold. Informally speaking, $\psi_1$ is responsible for preventing $\beta({\boldsymbol{{x}}}(t))$ from getting stuck at a value strictly smaller than one when ${\boldsymbol{{x}}}$ is a fluid trajectory, which is necessary for (13). On the other hand, $\psi_2$ ensures that $\psi$ complies with the constraints of the problem and thus is indeed a fluid control.

The function $\psi_1$ is completely determined by the constants $\pi$ , which correspond to a stationary policy for a single process without constraints. Such a policy can be found by inspecting the transition diagrams of a single process for the different actions. Moreover, as noted in Remark 2, there exists $\pi$ that satisfies Condition 2 if and only if the policy $\nu$ that selects actions uniformly at random satisfies the condition. In contrast, the choice of $\psi_2$ depends on the constraints of the problem. In the following two sections we provide rules for defining $\psi_2$ when the constraints have specific structures. Nonetheless, we remark that asymptotically optimal policies can be obtained for problems with different constraint structures if an expression for $\psi_2$ , such that $\psi$ satisfies the constraints, is available.

4.2. Inequality constraints

In this section we impose the following assumption on the constraints.

As noted in Section 2, constraints with nonnegative coefficients as in Assumption 2 can be interpreted as resource allocation constraints. Besides nonnegative coefficients, the assumption imposes two further conditions. The first condition is that there are no equality constraints, which means that it is not compulsory to fully consume any of the resources. The second condition is that there exists an action $0 \in A$ that does not consume any of the resources, and can often be interpreted as doing nothing. In this setup, a fluid control that satisfies the assumptions of Corollary 1 exists if the unconstrained single-process problem admits a unichain and aperiodic policy such that the unique irreducible class is contained in $S_+^*$ . The following proposition proves this; the proof is provided in Appendix A.

Proposition 3. Suppose that Assumption 2 holds and there exists a set of values $\pi$ as in Definition 5 such that the associated matrix $P_\pi$ satisfies Condition 2. Define

\begin{equation*} \gamma \,:\!=\, \min\bigg\{1, \frac{f(k)}{E(i, k, a)} \colon E(i, k, a) \neq 0\bigg\} \in (0, 1] \end{equation*}

and $\psi_2 \colon X \longrightarrow Y$ such that $\psi_2(x, 0) \,:\!=\, x$ and $\psi_2(x, a) \,:\!=\, 0$ for $a \neq 0$ . Then Condition 2 holds for the mapping $\psi$ defined by $\psi(x, a) \,:\!=\, \gamma x D_\pi(a) + (1 - \gamma)\psi_2(x, a)$ for all $x \in X$ and $a \in A$ .

The proposition gives an expression for a fluid control that satisfies Condition 2. If the constraints (2) do not depend on n, then the following remark provides a simple rounding procedure for defining asymptotically optimal discrete controls.

Remark 3. Suppose that the assumptions of Proposition 3 hold, and $E_n(a) = E(a)$ for all $a \in A$ and $f_n = f$ for all $n \geq 1$ . Let $\phi$ and $\psi$ be as in (15) and Proposition 3, respectively, and define $\phi_n \colon X_n \longrightarrow Y_n$ by

\begin{equation*} \phi_n(x) (i, a) \,:\!=\, \frac{\lfloor n\phi(x) (i, a)\rfloor}{n} \quad \text{for all} \ a \neq 0, \qquad \phi_n(x) (i, 0) = x(i) - \sum_{a \neq 0} \phi_n(x) (i, a) \end{equation*}

for all $x \in X_n$ and $i \in S$ . In addition, note that $\max_{x \in X_n}||\phi(x) - \phi_n(x)||_\infty \leq {|A|}/{n}$ . Note that $\phi_n(x)$ puts less weight on the actions $a \neq 0$ than $\phi(x)$ , and thus $\phi_n(x)$ satisfies (2) for all $x \in X_n$ . Hence, the functions $\phi_n$ are discrete controls for $\phi$ . It follows from Corollary 1 and Proposition 3 that these discrete controls are asymptotically optimal.

4.3. Multi-armed restless bandits

Next, we consider multi-armed restless bandit problems with an equality constraint, as stated in the following assumption. Note that multi-armed restless bandit problems with an inequality constraint are already covered by the case under Assumption 2.

In this case there is a unique resource which must be fully consumed and there are only two actions. As in Section 4.2, there exists an action $0 \in A$ that does not consume the resource and can often be interpreted as doing nothing. In contrast, the other action consumes one unit of resource per arm, regardless of the state the arm is in. The following proposition provides a fluid control that satisfies the assumptions of Corollary 1 if the unconstrained single-arm problem has a unichain and aperiodic policy such that the unique irreducible class is contained in $S_+^*$ ; the proof is provided in Appendix A.

Proposition 4. Suppose that Assumption 3 holds and there exists a set of values $\pi$ as in Definition 5 such that the matrix $P_\pi$ satisfies Condition 2. Define $\psi_2 \colon X \longrightarrow Y$ by

\begin{equation*} \psi_2(x)(i, 1) \,:\!=\, \frac{d - \sum_{j \in S} x(j) d \pi(1 \mid j)}{(1 - d)\sum_{j \in S} x(j)[1 - d \pi(1 \mid j)]} x(i)[1 - d \pi(1 \mid i)] \end{equation*}

and $\psi_2(x)(i, 0) \,:\!=\, x(i) - \psi_2(x)(i, 1)$ for all $i \in S$ . Condition 2 holds with

\begin{equation*} \psi(x, a) \,:\!=\, d x D_\pi(a) + (1 - d) \psi_2(x, a) \quad \text{for all} \ x \in X, \quad a \in A. \end{equation*}

The following remark provides a simple rounding procedure for defining asymptotically optimal discrete controls using the fluid control defined above.

Remark 4. Suppose that the assumptions of Proposition 4 hold, and that $d_n = {\lfloor d n\rfloor}/{n}$ for all $n \geq 1$ , which is typically assumed for multi-armed restless bandit problems. Let $\phi$ and $\psi$ be as in (15) and Proposition 4, respectively, and define $\phi_n \colon X_n \longrightarrow Y_n$ as follows. First let

\begin{equation*} \theta_n(x, i) \,:\!=\, \lfloor d n\rfloor - \sum_{i \in S}\lfloor n\phi(x)(i, 1)\rfloor - \sum_{j = 1}^{i - 1}\mathbf{1}_{\{n\phi(x)(i,1)\notin\mathbb{Z}\}} \quad \text{for all} \ x \in X_n, \quad i \in S, \end{equation*}

where we have enumerated the states, i.e. $S = \{1, \ldots, |S|\}$ . Then define

\begin{equation*} \phi_n(x)(i, 1) \,:\!=\, \begin{cases} \phi(x)(i, 1) & \text{if} \ n\phi(x)(i, 1) \in \mathbb{Z}, \\ [\lfloor n\phi(x)(i, 1)\rfloor + 1]/n & \text{if} \ n\phi(x)(i, 1) \notin \mathbb{Z}, \quad \theta_n(x, i) > 0, \\ \lfloor n\phi(x)(i, 1)\rfloor/n & \text{otherwise}, \end{cases} \end{equation*}

and $\phi_n(x)(i, 0) \,:\!=\, x(i) - \phi_n(x)(i, 1)$ for all $x \in X_n$ and $i \in S$ . This can be interpreted algorithmically as follows. In a first stage, we let $\phi_n(x)(i, 1) = \lfloor n\phi(x)(i, 1)\rfloor / n$ for all $i \in S$ . If $n\phi_n(x)(i, 1) \notin \mathbb{Z}$ for some i, then we must select action 1 for more processes in order to exhaust the budget $\lfloor dn\rfloor$ . Therefore, in a second stage, we consider the states i in increasing order and increase $\phi_n(x)(i, 1)$ for some states until the budget is exhausted. We increase $\phi_n(x)(i, 1)$ by $1 / n$ if the budget has not been exhausted yet and $n\phi(x)(i, 1) \notin \mathbb{Z}$ . The above expression for $\phi_n(x)(i, 1)$ is obtained by noting that the remaining budget when state i is considered equals $\theta_n(x, i)$ . It is easy to check that $\max_{x \in X_n} ||\phi(x) - \phi_n(x)||_\infty \leq {1}/{n}$ , and that $\phi_n(x)$ satisfies the unique equality constraint for all $x \in X_n$ . Thus, the functions $\phi_n$ are discrete controls for $\phi$ . We conclude from Corollary 1 and Proposition 4 that these discrete controls are asymptotically optimal.

5.1. Multiple actions and constraints

Consider a fleet of n electric taxis and suppose that each process describes the battery level of a taxi. Namely, $S = \{0, \ldots, 7\}$ are the battery levels and ${\boldsymbol{{S}}}_n(t, m)$ represents the battery level at time t of taxi m. Also, the actions $A = \{0, 1, 2\}$ are: to deploy the taxi at the airport, to deploy the taxi at the city center, and to charge the taxi, respectively.

The battery level of a taxi that is being charged increases at a constant rate, whereas that of a deployed taxi decreases by a random amount. More precisely, the distribution of ${\boldsymbol{{S}}}_n(t + 1, m)$ given that ${\boldsymbol{{A}}}_n(t, m) = a$ and ${\boldsymbol{{S}}}_n(t, m) = i$ is known and given by

The random variable $X_a$ represents the power consumed by a taxi during period t, and tends to be larger for taxis that are deployed at the airport. Specifically, $X_a$ has a Poisson distribution with a mean that depends on a in the following way:

\begin{equation*} \mathbb{P}(X_a = k) \,:\!=\, \frac{\lambda_a^k \mathrm{e}^{-\lambda_a}}{k!} \quad \text{for all} \ k \geq 0, \quad \text{with} \ \lambda_a \,:\!=\, \begin{cases} 2 & \text{if} \ a = 0, \\ 1 & \text{if} \ a = 1. \end{cases}\end{equation*}

At most 70% of the taxis can be charged simultaneously since there are limited charging spots, and the taxi company has agreed with city hall to deploy at least 10% of the fleet at the airport. These constraints can be formulated in such a way that Assumption 2 holds, i.e. by requiring that the following inequalities hold for all $t \geq 0$ :

\begin{equation*} \sum_{i \in S} {\boldsymbol{{y}}}_n(t, i, 2) \leq 0.7, \qquad \sum_{i \in S} [{\boldsymbol{{y}}}_n(t, i, 1) + {\boldsymbol{{y}}}_n(t, i, 2)] \leq 0.9.\end{equation*}

Finally, the rewards are given by

The constants $b_a$ and $c_a$ can be interpreted as revenues and costs, respectively. On the one hand, taxis deployed at the airport do one trip per period and charge a flat fare $b_0 \,:\!=\, 3$ , whereas taxis deployed at the city center charge $b_1 \,:\!=\, 2.5$ per unit of distance traveled. On the other hand, a cost $c_2 \,:\!=\, 2$ is paid for charging a taxi and penalties $c_0 \,:\!=\, 3$ and $c_1 \,:\!=\, 2$ are incurred if a taxi is deployed and completely depletes its battery. The rewards defined in this way are plotted in the left panel of Figure 1.

Figure 1.

The left panel shows the reward obtained per process and per time step as a function of the state of the process and the action selected. The right panel charts the optimal value of the fluid relaxation, and the gain of the discrete control $\phi_n$ when all the batteries are initially empty.

Because the constraints of the problem do not depend on the number of taxis n, it follows from Proposition 1 that the optimal value $g_r = 0.8911$ of the fluid relaxation is an upper bound for the gain of any policy. The optimal solution $y^*$ of the fluid relaxation that we used to construct a discrete control $\phi_n$ is as follows:

\begin{equation*} y^* = \left[\begin{array}{c@{\quad}c@{\quad}c@{\quad}c@{\quad}c@{\quad}c@{\quad}c@{\quad}c} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0.1000 \\[4pt] 0 & 0 & 0 & 0 & 0 & 0 & 0.3236 & 0.2095 \\[4pt] 0.0009 & 0.0023 & 0.0100 & 0.0343 & 0.1004 & 0.2189 & 0 & 0 \end{array}\right]\!.\end{equation*}

The constraint that 10% of the fleet is deployed at the airport is satisfied with equality, whereas the other constraint is satisfied with a strict inequality; approximately 37% of the taxis are being charged while 53% of the taxis are in the city center.

The unconstrained single-process problem is multichain, e.g. the policy that always charges the taxi if the battery level is at least 4 and never charges the taxi if the battery level is strictly less than 4 is multichain with absorbing states 0 and 7. However, it is straightforward to check that the policy defined by (20) satisfies Condition 2. It follows that asymptotically optimal discrete controls $\phi_n$ can be obtained as explained in Remark 3. The right panel of Figure 1 compares the gains of these discrete controls against the upper bound $g_r$ for different values of n; the gains were computed by simulating the processes and averaging the rewards. The plot confirms that the gain of our discrete controls approaches the upper bound.

5.2. Multi-armed restless bandits

We are not aware of any policies for maximizing the expected average reward of weakly coupled processes with more than one constraint. Hence, we compare our assumptions on the transition kernels of the processes with those in the literature for multi-armed restless bandits, which are a narrower class of problems with only two actions and a single constraint with a specific structure. In particular, we consider multi-armed restless bandit problems where the budget constraint is an equality constraint, and we compare our discrete controls with the following four policies: the Whittle index policy proposed in [Reference Whittle25], the LP-priority policies introduced in [Reference Verloop23], the Follow-The-Virtual-Advice (FTVA) policy defined in [Reference Hong, Xie, Chen and Wang16], and the ID policy proposed in [Reference Hong, Xie, Chen and Wang18]. The asymptotic optimality of these policies has been proved in [Reference Gast, Gaujal and Yan9, Reference Gast, Gaujal and Yan10, Reference Hong, Xie, Chen and Wang16, Reference Hong, Xie, Chen and Wang18, Reference Verloop23, Reference Weber and Weiss24] under the assumptions that we discuss below.

1. (i) For the Whittle index and LP-priority policies, the Markov decision process formed by n arms must be unichain for all n as required in [Reference Gast, Gaujal and Yan9, Reference Gast, Gaujal and Yan10, Reference Verloop23, Reference Weber and Weiss24]; in fact, some of these papers even assume that each arm is ergodic.

2. (ii) For the Whittle index policy, the unconstrained single arm must satisfy a condition known as indexability, without which the policy is not well-defined; see [Reference Whittle25].

3. (iii) For the Whittle index and LP-priority policies, a discrete-time dynamical system must satisfy a global attractor property similar to (13); see [Reference Gast, Gaujal and Yan9, Reference Gast, Gaujal and Yan10, Reference Verloop23, Reference Weber and Weiss24]. We do not assume that (13) holds, but prove (13) under the assumption of Proposition 4.

4. (iv) For the FTVA policy, the synchronization assumption defined in [Reference Hong, Xie, Chen and Wang16] must hold.

5. (v) For the ID policy, the single-arm policy (20) must be unichain and aperiodic.

The synchronization assumption pertains to a single-arm problem with a relaxed budget constraint, which must hold on average and not at each time step. Loosely speaking, a system formed by a leader and a follower arm is considered, where the follower arm always selects the same action as the leader arm. The assumption is that there exists an optimal policy, for the aforementioned relaxed single-arm problem, that is unichain and such that the mean time until the leader and follower arms are in the same state is finite. We note that an optimal policy for the above-described relaxed single-arm problem can be obtained as in (20) by standard results for constrained Markov decision processes; see [Reference Altman2].

Conditions (i)–(iii) are significantly stronger than the assumption of Proposition 4, which only requires that the unconstrained single-arm problem admits a unichain and aperiodic policy such that the unique irreducible class contains $S_+^*$ . In addition, condition (v) implies that Proposition 4 holds since $x^*$ is the stationary distribution of the policy defined by (20) when this policy is unichain and aperiodic. On the other hand, condition (iv) is not entirely understood. However, the synchronization assumption seems to be connected with the existence of suitable aperiodic policies for a single arm; see [Reference Hong, Xie, Chen and Wang16, Appendix C].

Each of the conditions (i)–(v) is violated in one of the examples presented below, and each of the policies for multi-armed bandit problems mentioned above is not asymptotically optimal in one of the examples. In contrast, the assumption of Proposition 4 holds in all the examples, and thus our discrete controls are provably asymptotically optimal.

5.2.1. Counterexamples to Whittle index and LP-priority policies.

In this section we consider two examples where the number of states is three and the single-arm problem is ergodic. Further, the transition probability matrices have positive entries; these matrices, the rewards, and the constraints are provided in Appendix B.

The first example was first considered in [Reference Gast, Gaujal and Khun7] and is nonindexable. In particular, the Whittle index policy is not well-defined. The left panel of Figure 2 compares the gain of different policies with the optimal value $g_r = 0.3437$ of the fluid relaxation, which is an upper bound for the gain of any policy. For this particular problem instance, the LP-priority policy outperforms our policy $\phi_n$ and the FTVA and ID policies; the latter three policies perform similarly. However, all four policies perform extremely well, with optimality gaps that are less than 3% for $n = 200$ and 1% for $n = 2000$ .

Figure 2.

The left and right panels respectively correspond to the nonindexable problem and the problem where the global attractivity property does not hold for the Whittle index and LP-priority policies.

The second example was first considered in [Reference Gast, Gaujal and Yan8] and is such that the global attractivity assumption does not hold for the Whittle index and LP-priority policies, which in this case are the same policy. The plot in the right panel of Figure 2 shows that these policies are not asymptotically optimal for this problem instance. In contrast, our discrete control and the FTVA and ID policies approach $g_r = 0.1238$ at similar rates as n grows.

5.2.2. Counterexamples to FTVA.

We now consider an example where the synchronization assumption does not hold and the single-arm problem is multichain. Specifically, the budget constraint is $d = 0.25$ , the transition probabilities are depicted in Figure 3, and the rewards are given by

\begin{equation*} r = \left[\begin{array}{l@{\quad}l@{\quad}l@{\quad}l@{\quad}l} 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{array}\right]\!.\end{equation*}

Figure 3.

The diagrams depict the transition probabilities for both actions. The plot compares the optimal value of the fluid relaxation and the gain of several policies. The gains were computed by simulating systems where all the arms are initially in state 0.

In order to show that the synchronization assumption does not hold, let us consider the single-arm problem with the relaxed budget constraint, i.e. action 1 must be selected 25% of the time. Consider also the following policy for this problem: $\pi(0 \mid i) = 1$ if $i \in \{2, 4\}$ and $\pi(1 \mid i) = 1$ if $i \in \{0, 1, 3\}$ . This policy is unichain and aperiodic, and the probability that action 1 is selected in steady state is $0.25$ . Hence, $\pi$ is a feasible solution, and it is easy to check that its gain is 1, which is clearly the maximum gain that any policy can achieve. It is also possible to check that any other policy with gain 1 must coincide with $\pi$ in states 2, 3, and 4. Moreover, the set $\{2, 3, 4\}$ must be absorbing for the Markov chain associated with the policy.

Suppose now that a leader arm uses one of the optimal policies while a follower arm always selects the same action as the leader arm. Assume also that the leader and follower arms are in states 2 and 0 at time zero, respectively. Since the leader arm remains within $\{2, 3, 4\}$ , it can never select action 1 twice in a row and therefore the follower arm can never leave $\{0, 1\}$ . It follows that the synchronization assumption does not hold, and the plot in Figure 3 shows that FTVA is not asymptotically optimal if all the arms are initially in state 0. Similar counterexamples to FTVA are constructed in [Reference Hong, Xie, Chen and Wang18]; these examples satisfy the assumptions in [Reference Hong, Xie, Chen and Wang18] and thus also our weaker assumptions.

States 2 and 3 have the lowest and highest Whittle indexes, respectively, and our numeric computations indicate that the other three states have a common Whittle index that is strictly between the indexes of 2 and 3. If we arrange the states as (3, 1, 0, 4, 2), then we obtain the Whittle index policy plotted in Figure 3, which is also an LP-priority policy; arranging the states as (3, 1, 0, 2, 4), we obtain another LP-priority policy with nearly the same performance. However, there are no results that rigorously establish this asymptotic optimality because the example considered here is multichain and all the available results concern unichain setups. In contrast, our discrete controls $\phi_n$ and the ID policy are provably asymptotically optimal for this problem instance, as confirmed by Figure 3.

5.2.3. Counterexample to ID policy.

Finally, we consider multi-armed restless bandits with budget constraint $d = 0.5$ and the transition probabilities and rewards depicted in Figure 4. The objective of the fluid relaxation (4) is to maximize $y(0, 0) + y(1, 1) \leq 1$ , and $\max\{y(0, 0), y(1, 1)\} \leq 0.5$ by the budget constraint since at most half of the processes can use action 0 and at most half of the processes can use action 1. Then it is not difficult to check that there exists a unique solution $y^*$ which is given by $y^*(0, 0) = y^*(1, 1) = 0.5$ and $y^*(i, a) = 0$ otherwise.

Figure 4.

The diagrams depict the transition probabilities and rewards for both actions; all the transitions are deterministic. The chart compares the optimal value of the fluid relaxation and the gain of different policies; the gains were computed by simulating systems where all the arms are initially in state 0.

Consider now the single-arm policy $\mu$ defined by (20) when $y^*$ is as above. State 2 is transient while states 0 and 1 form an irreducible class with period 2. The synchronization assumption used in [Reference Hong, Xie, Chen and Wang16] does not hold because a leader starting in state 0 and a follower starting in state 2 will never be in the same state. In addition, the assumptions used in [Reference Hong, Xie, Chen and Wang18] to establish the asymptotic optimality of the ID policy do not hold either since $\mu$ is not aperiodic. However, the policy $\nu$ that selects actions uniformly at random is ergodic and thus yields discrete controls $\phi_n$ that are asymptotically optimal by Proposition 4.

The plot in Figure 4 confirms that our discrete controls $\phi_n$ are asymptotically optimal and further shows that all the other policies have gains that are far from the optimal value when all the arms are in state 0 at time zero. In fact, it is not difficult to check analytically that the Whittle index, LP-priority, and ID policies have gains equal to $\frac12$ .

For example, consider the ID policy, which follows the policy $\mu$ defined by (20) for as many arms as possible. More specifically, a permanent and unique ID in $\{1, \ldots, n\}$ is assigned to each arm at time $t = 0$ . Then, at each time, an action is sampled for each arm using the single-arm policy $\mu$ , and the sampled action is applied to the arms in order of their IDs for as many arms as allowed by the budget constraint; the actions for the rest of the arms are chosen so as to comply with the constraint. For the problem described in Figure 4, the action sampled at time $t = 0$ is 0 for all the arms. Hence, the half of the arms having the lowest IDs will move to state 1 at $t = 1$ , while the rest of the arms will move to state 2. Then the action sampled for the arms in state 1 will be 1 because $\mu$ is deterministic at state 1. Since these arms have the lowest IDs, action 1 will be used for these arms and action 0 will be used for the other arms. It follows that the state of the entire system at $t = 2$ is exactly the same as at $t = 0$ and that the system evolves periodically in the way just described. We conclude that half of the arms will obtain a reward equal to 1 at each time step while the other half will not obtain any reward.

Noting that the Whittle index and LP-priority policy give the highest priority for using action 1 in state 1, similar arguments as above can be used to show that both policies have gain $\frac12$ . The gain of the FTVA policy may depend on the tie-breaking rule used to decide which arms follow the virtual advice; the tie-breaking rule used in our simulations is the same as we described above for the ID policy. Nonetheless, we recall that the synchronization assumption does not hold for this problem instance.