The mean-field limit of a restless bandit

higherPriorityMass — For an arbitrary finite type $S$ (no further structure assumed) this defines a real number from three inputs: a "priority" function $\nu : S \to \mathbb{R}$, a "mass" function $m : S \to \mathbb{R}$, and a point $x \in S$. Its value is

$$\mathrm{HPM}_\nu(m,x) \;=\; \sum_{\substack{y \in S \\ \nu(x) < \nu(y)}} m(y),$$

i.e. the sum of $m$ over exactly those $y$ whose priority is strictly greater than the priority of $x$. Ties ($\nu(y) = \nu(x)$) are excluded, and in particular $x$ itself never contributes. Nothing requires $m$ to be nonnegative, to sum to $1$, or to be a distribution of any kind, and nothing requires $\nu$ to be injective; $m$ may take negative values and the sum may be negative. If no $y$ has strictly larger priority the sum is over the empty set and the value is $0$; if $S$ is empty the function has no arguments $x$ to be applied to.

activateFraction — For a finite type $S$, priorities $\nu : S \to \mathbb{R}$, a real scalar $\alpha$, a mass function $m : S \to \mathbb{R}$ and a point $x \in S$, this is the real number

$$\mathrm{act}_{\nu,\alpha}(m,x) \;=\; \min\Bigl(m(x),\; \max\bigl(0,\; \alpha - \mathrm{HPM}_\nu(m,x)\bigr)\Bigr),$$

where $\mathrm{HPM}_\nu(m,x) = \sum_{y:\ \nu(x)<\nu(y)} m(y)$ is the total mass carried by states of strictly higher priority than $x$. So one takes the "budget left over after all strictly higher-priority states are served", $\alpha - \mathrm{HPM}_\nu(m,x)$, truncates it below at $0$, and then caps it at $m(x)$. There is no hypothesis that $m \ge 0$, that $\alpha \ge 0$, or that $\alpha \le \sum_x m(x)$: if $m(x) < 0$ the outer minimum returns $m(x)$ itself, so the value is then negative rather than lying in $[0, m(x)]$; if $\alpha \le \mathrm{HPM}_\nu(m,x)$ the value is $\min(m(x), 0)$.

meanFieldMap — Given a finite type $S$, two arbitrary real square matrices $P_0, P_1$ indexed by $S \times S$ (no stochasticity, nonnegativity, or row-sum hypothesis is imposed on either), priorities $\nu : S \to \mathbb{R}$, a real scalar $\alpha$, and a mass function $m : S \to \mathbb{R}$, this produces a new function $S \to \mathbb{R}$ whose value at $y \in S$ is

$$\bigl(\Phi_{P_0,P_1,\nu,\alpha}(m)\bigr)(y) \;=\; \sum_{x \in S} \Bigl[\bigl(m(x) - \mathrm{act}_{\nu,\alpha}(m,x)\bigr)\,P_0^{x,y} \;+\; \mathrm{act}_{\nu,\alpha}(m,x)\,P_1^{x,y}\Bigr],$$

where $\mathrm{act}_{\nu,\alpha}(m,x) = \min\bigl(m(x), \max(0, \alpha - \sum_{y':\ \nu(x)<\nu(y')} m(y'))\bigr)$ is the clamped leftover-budget quantity described above. That is, at each source state $x$ the mass is split into an "active" part $\mathrm{act}_{\nu,\alpha}(m,x)$ pushed through $P_1$ and a "passive" remainder $m(x) - \mathrm{act}_{\nu,\alpha}(m,x)$ pushed through $P_0$, and the contributions are summed over all $x$. Nothing constrains $m$ to be a probability vector, so the passive remainder and the output need not be nonnegative. If $S$ is empty, the result is the empty function and every such sum is $0$.

IsPriorityRegion — This is a proposition (not a number) about a finite type $S$, priorities $\nu : S \to \mathbb{R}$, a real scalar $\alpha$, a mass function $m : S \to \mathbb{R}$, and a point $x \in S$. It asserts the conjunction of two inequalities:

$$\mathrm{HPM}_\nu(m,x) \;\le\; \alpha \qquad\text{and}\qquad \alpha \;<\; \mathrm{HPM}_\nu(m,x) + m(x),$$

where $\mathrm{HPM}_\nu(m,x) = \sum_{y:\ \nu(x)<\nu(y)} m(y)$ is the mass of strictly-higher-priority states. Equivalently, $\alpha$ lies in the half-open interval $[\mathrm{HPM}_\nu(m,x),\ \mathrm{HPM}_\nu(m,x) + m(x))$ — closed on the left with a non-strict $\le$, open on the right with a strict $<$. Note that the two conditions can only both hold if $m(x) > 0$; for $m(x) \le 0$ the interval is empty and the proposition is unsatisfiable for that $x$. No hypotheses are placed on $\nu$, $\alpha$, or $m$.

meanFieldActivationProb — For a finite type $S$, priorities $\nu : S \to \mathbb{R}$, a real scalar $\alpha$, a mass function $m : S \to \mathbb{R}$, and a point $x \in S$, this is the real number defined by cases: it equals $0$ when $m(x) = 0$, and otherwise equals the ratio

$$\frac{\mathrm{act}_{\nu,\alpha}(m,x)}{m(x)}, \qquad \mathrm{act}_{\nu,\alpha}(m,x) = \min\Bigl(m(x),\ \max\bigl(0,\ \alpha - \textstyle\sum_{y:\ \nu(x)<\nu(y)} m(y)\bigr)\Bigr).$$

The $m(x) = 0$ branch is a stipulated value, chosen to avoid division by zero rather than derived. Despite the name, nothing forces this quantity into $[0,1]$: it is a ratio of two unconstrained reals, and when $m(x) < 0$ the numerator equals $m(x)$, making the value exactly $1$. No hypothesis states that $m$ is nonnegative or a distribution, or that $\alpha \ge 0$.

meanFieldLocalPolicy — For a finite type $S$, priorities $\nu : S \to \mathbb{R}$, a real $\alpha$, a mass function $m : S \to \mathbb{R}$, a state $x \in S$ and a Boolean $a$, this is the real number

$$\pi_{\nu,\alpha,m}(x, a) \;=\; \begin{cases} p(x) & a = \text{true},\\[2pt] 1 - p(x) & a = \text{false},\end{cases}$$

where $p(x)$ is the quantity of the previous declaration: $p(x) = 0$ if $m(x) = 0$, and $p(x) = \mathrm{act}_{\nu,\alpha}(m,x)/m(x)$ otherwise, with $\mathrm{act}_{\nu,\alpha}(m,x) = \min\bigl(m(x), \max(0, \alpha - \sum_{y:\ \nu(x)<\nu(y)} m(y))\bigr)$. By construction the two values sum to $1$ for every $x$, but there is no hypothesis making either of them nonnegative or at most $1$; the action set is the two-element Boolean type.

rmabStep — Fix a natural number $N$ (which may be $0$), a finite type $S$ with decidable equality, and two arbitrary real $S \times S$ matrices $P_0, P_1$ (no row-stochasticity or nonnegativity assumed). Given an arbitrary real-valued function $\pi$ of a joint state $s \in S^{N}$ (a function $\{0,\dots,N-1\} \to S$) and a joint action $a \in \{\text{false},\text{true}\}^{N}$ — with no hypothesis that $\pi$ is nonnegative, normalized, or budget-respecting — and given joint states $s, s' \in S^N$, this defines

$$\mathrm{Step}(s, s') \;=\; \sum_{a \in \{\text{false},\text{true}\}^{N}} \pi(s,a) \prod_{j=0}^{N-1} K\bigl(s_j,\, a_j,\, s'_j\bigr), \qquad K(x,b,y) = \begin{cases} P_1^{x,y} & b = \text{true},\\ P_0^{x,y} & b = \text{false}.\end{cases}$$

The sum ranges over all $2^N$ Boolean tuples and the product over all $N$ coordinates, so the per-arm transitions are taken to be conditionally independent given the action. In the degenerate case $N = 0$ there is exactly one (empty) action tuple and the empty product is $1$, so the value reduces to $\pi(s, a_{\text{empty}})$ for the unique empty state tuples.

rmabLaw — Fix $N : \mathbb{N}$, a finite type $S$ with decidable equality, arbitrary real $S \times S$ matrices $P_0, P_1$, an arbitrary real-valued function $\pi$ on (joint state, joint action) pairs with no assumption that it is a probability distribution, and an initial joint state $s_0 \in S^N$. This defines, by recursion on a time index $t \in \mathbb{N}$, a real-valued function on joint states:

$$L_0(s) = \begin{cases} 1 & s = s_0,\\ 0 & \text{otherwise},\end{cases} \qquad L_{t+1}(s') \;=\; \sum_{s \in S^N} L_t(s)\,\mathrm{Step}(s, s'),$$

where $\mathrm{Step}(s,s') = \sum_{a \in \{\text{false},\text{true}\}^N} \pi(s,a) \prod_{j} K(s_j, a_j, s'_j)$ with $K(x,\text{true},y) = P_1^{x,y}$ and $K(x,\text{false},y) = P_0^{x,y}$. So $L_0$ is the point mass (as an indicator function) at $s_0$ and each subsequent time step is left-multiplication of the current row vector by the one-step matrix. Since no positivity or normalization hypotheses are present on $\pi$, $P_0$, or $P_1$, the values $L_t(s)$ are arbitrary reals and need not be nonnegative or sum to $1$. The sums range over the full finite set $S^N$ of joint states; when $N = 0$ this set is a single point.

l1Norm — For a finite type $S$ and an arbitrary function $v : S \to \mathbb{R}$, this is the real number $\sum_{x \in S} |v(x)|$, the sum of absolute values of the coordinates over all of $S$. If $S$ is empty the value is $0$. No normalization or sign hypothesis is placed on $v$.

IsDist — For an arbitrary finite type $\iota$ and an arbitrary function $\mu : \iota \to \mathbb{R}$, this is the proposition asserting both of:

$$\forall p \in \iota,\; 0 \le \mu(p) \qquad\text{and}\qquad \sum_{p \in \iota} \mu(p) = 1.$$

That is, $\mu$ is pointwise nonnegative and its total mass over the whole index type is exactly $1$. Note that when $\iota$ is empty the sum is $0 \ne 1$, so the proposition is unsatisfiable in that case. The index type $\iota$ here is a fresh type variable independent of the ambient $S$.

IsExchangeableDist — For a natural number $N$, an arbitrary finite type $X$, and an arbitrary function $\mu : X^N \to \mathbb{R}$ defined on tuples $p : \{0,\dots,N-1\} \to X$, this is the proposition

$$\forall\, \sigma \in \mathfrak{S}_N,\; \forall\, p : \{0,\dots,N-1\} \to X,\qquad \mu(p \circ \sigma) = \mu(p),$$

quantifying over all permutations $\sigma$ of the index set $\{0,\dots,N-1\}$ and all tuples $p$; $p \circ \sigma$ is the tuple whose $i$-th entry is $p(\sigma(i))$. This asserts only permutation-invariance of the function $\mu$; despite the name, nothing here requires $\mu$ to be nonnegative or to sum to $1$, so any constant function — including the zero function — satisfies it. When $N = 0$ there is a single tuple and a single permutation and the condition holds trivially.

IsNonDegenerateMeanField — For a finite type $S$, priorities $\nu : S \to \mathbb{R}$, a real scalar $\alpha$, and a function $m^\star : S \to \mathbb{R}$, this is the proposition that there exists a state $x \in S$ satisfying all three of:

$$0 < m^\star(x), \qquad 0 < \alpha - \mathrm{HPM}_\nu(m^\star, x), \qquad \alpha - \mathrm{HPM}_\nu(m^\star, x) < m^\star(x),$$

where $\mathrm{HPM}_\nu(m^\star,x) = \sum_{y:\ \nu(x)<\nu(y)} m^\star(y)$ is the total $m^\star$-mass of the states with strictly higher priority than $x$. Equivalently: some state carries strictly positive mass and the residual budget $\alpha - \mathrm{HPM}_\nu(m^\star,x)$ at that state lies strictly between $0$ and $m^\star(x)$ — both endpoints excluded. Existence, not uniqueness, is asserted; no hypothesis says $m^\star$ is a distribution, is nonnegative, or is a fixed point of anything, and no hypothesis constrains $\alpha$. If $S$ is empty the proposition is false.

IsStableOnTangent — For a finite type $S$ and an arbitrary real square matrix $K$ indexed by $S \times S$ (with no stochasticity, nonnegativity, or symmetry hypothesis), this is the proposition that there exist real numbers $C$ and $\rho$ such that

$$0 \le C, \qquad 0 \le \rho, \qquad \rho < 1,$$

and such that for every vector $v : S \to \mathbb{R}$ whose coordinates sum to zero, $\sum_{x \in S} v(x) = 0$, and for every natural number $t$ (including $t = 0$),

$$\bigl\| v\,K^{t} \bigr\|_\infty \;\le\; C\,\rho^{t}\,\|v\|_\infty ,$$

where $v K^t$ denotes the row-vector-times-matrix product, i.e. the function $y \mapsto \sum_{x} v(x)\,(K^t)^{x,y}$, with $K^t$ the $t$-th matrix power ($K^0$ being the identity matrix), and where $\|w\|_\infty$ denotes the supremum $\sup_{x \in S} |w(x)|$ over the finite index type (for empty $S$ this supremum is $0$ by the convention for the supremum of an empty set of reals). The bound is a non-strict $\le$, the decay rate satisfies a strict $\rho < 1$ but is allowed to be $0$, and $\rho^0$ is $1$. Because the case $t = 0$ is included, the condition at $t=0$ reads $\|v\|_\infty \le C\|v\|_\infty$ for all zero-sum $v$. The zero vector always satisfies the zero-sum hypothesis; if $S$ is empty, or more generally if the only zero-sum vector considered is $0$, the universally quantified condition is satisfiable trivially.