Limited Resource Allocation in a Non-Markovian World: The Case of Maternal and Child Healthcare

Panayiotis Danassis, Shresth Verma, Jackson A. Killian, Aparna Taneja, Milind Tambe

TL;DR

This paper challenges the long-standing Markovian assumption in Restless Multi-armed Bandit (RMAB) frameworks used for healthcare resource allocation. By proving that real-world patient engagement data exhibits strong non-Markovian properties, the authors introduce a novel, scalable Time-series Arm Ranking Index (TARI) policy that leverages deep learning time-series forecasting to optimize continuous-state patient interventions, outperforming state-of-the-art Whittle index methods by over 90% in preventing patient dropouts.

What Problem Does This Paper Address?

In public health programs, especially in low-resource settings, keeping participants engaged is a major hurdle. For instance, the Indian NGO ARMMAN runs an automated mHealth messaging program to deliver critical prenatal and postnatal advice to mothers. However, adherence naturally dwindles over time. To prevent dropouts, health workers can make personalized support calls, but their time and resources are strictly limited.

To schedule these interventions efficiently, researchers typically model the problem as a Restless Multi-armed Bandit (RMAB). In an RMAB, each participant (an "arm") has a state of engagement that evolves over time, even if they aren't selected for an intervention. The standard approach relies on the Whittle index policy, which calculates the immediate value of intervening on an arm.

However, traditional RMAB solutions suffer from two major flaws:

  1. The Markov Assumption: They assume a participant's future state depends only on their current state, ignoring historical behavior patterns.
  2. Discrete State Spaces: They require continuous engagement metrics (like call duration) to be chopped into coarse, binary bins (e.g., "engaging" vs. "non-engaging"), leading to severe approximation losses.

Trying to fix the Markov assumption using traditional methods causes a combinatorial explosion in the state space, making the problem computationally intractable (PSPACE-hard) and data-starved.

Methods

The authors bypass the limitations of traditional Markov Decision Processes (MDPs) by reframing the RMAB problem as a Time-Series Forecasting (TSF) task.

Instead of computing transition probabilities across a massive, discretized state space, they train a model (specifically an LSTM-based architecture) to independently predict each participant's future engagement trajectory based on a rolling history window of their past states and actions. This allows the framework to natively handle continuous state spaces and capture long-term temporal dependencies.

Using these forecasts, they propose the Time-series Arm Ranking Index (TARI) policy:

  1. Look-Ahead Forecasting: For each participant, the TSF model recursively forecasts two future trajectories:
  2. Scenario A ($u$): The number of timesteps the participant will remain engaged if given one intervention right now and never again.
  3. Scenario B ($v$): The number of timesteps the participant will remain engaged if no intervention is given.
  4. Index Calculation: The TARI value for an arm is computed as the ratio: $$\text{TARI}(n) = \frac{u_n}{v_n}$$
  5. Greedy Selection: At each decision epoch, the planner ranks all participants by their TARI value and intervenes on the top-$k$ individuals who stand to benefit the most.
Figure 5: Graphical representation of the calculation of the proposed TARI. We consider two options for the planner: (i) act once (green box, at = 1) and then never act (at+j = 0), or (ii) never act (orange box). We recursively call the TSF model to predict the next state in the trajectory (feedback loop on the left), until the state switches from engaging (green bar) to non-engaging (red bar). Let this be at timestep u (i.e., st+u < s∗) and v (i.e., st+v < s∗) for options (i), and (ii), respectively. The ratio between the timesteps needed for the switch if we had acted, compared to not, constitutes the TARI. This is computed independently for each arm.

Datasets

The authors evaluated their approach using two primary datasets:

  • Synthetic Data: Simulated trajectories representing three distinct behavioral archetypes: Habit Formers (whose engagement stabilizes if it hits a threshold), Motivation-based individuals (who reset to baseline after an intervention), and Random actors.
  • Real-World ARMMAN Dataset: Anonymized data from a 2022 large-scale mHealth quality improvement study in India. It tracks 12,000 participants over 31 weeks, recording weekly call listening times (normalized to a continuous $[0, 1]$ scale) alongside 43 static socio-demographic features (age, income, education, etc.). The secondary analysis focused on a test set of 2,252 participants over a 23-week horizon.

Key Insights and Ideas

  • Human Behavior is Quantifiably Non-Markovian: By analyzing the empirical log-likelihood of participant trajectories from the ARMMAN dataset, the authors proved that increasing the history order ($h$) of the underlying model dramatically increases the probability of accurately observing real-world trajectories. Moving from a first-order Markov model ($h=1$) to a seventh-order model ($h=7$) yielded up to a 23% improvement in log-likelihood, fundamentally invalidating the standard Markov assumption in this domain.
Figure 3: Relative (with respect to h = 1) improvement in log like- lihood. As we increase the order h of the underlying Markov model, the probability of observing the trajectories in our dataset increases. This suggests non-Markovian behaviour.
  • Decoupling Planning from MDPs: By shifting the workload to independent time-series forecasting models per arm, the authors decoupled the complexity of the history length from the optimization policy. This makes non-Markovian tracking computationally lightweight and highly scalable for real-world deployment.

Key Results

The TARI policy was tested against the state-of-the-art (SOTA) deployed Whittle index baseline, random selection, and round-robin policies.

  • Synthetic Performance: TARI achieved 44.2% higher engagement on average compared to the Whittle index, maintaining a remarkably low standard deviation (3.1%) because it successfully learned to ignore purely random agents.
  • Real-World Impact (ARMMAN Data):
  • TARI delivered a 90.8% improvement in preventing engagement drops compared to the Whittle index baseline.
  • It successfully reached 71.6% of critical, high-dropout-risk beneficiaries, more than doubling the Whittle index's reach of 30.4%.
  • In concrete health terms, this translated to 16.3 additional hours of critical medical content listened to by vulnerable mothers over the Whittle baseline.
Figure 7: Real data on maternal and child healthcare awareness from ARMMAN. N = 2252 beneficiaries (arms), budget k = 0.02 × N = 45. Results are averaged over 10 independent runs.

Limitations and Future Work

  • Dependency on Forecast Quality: TARI's performance is inherently bound to the accuracy of the underlying time-series forecasting model. While modern architectures perform well, domains with extreme noise or unpredictable behavioral shifts might suffer from error accumulation during multi-step rollouts.
  • High-Budget Open Question: TARI was explicitly designed for highly resource-constrained environments where an individual receives at most one call over a long period. How TARI scales or adapts to high-budget scenarios—where participants can be intervened upon frequently or continuously—remains an open research question.

Summary updated

Abstract

The success of many healthcare programs depends on participants' adherence. We consider the problem of scheduling interventions in low resource settings (e.g., placing timely support calls from health workers) to increase adherence and/or engagement. Past works have successfully developed several classes of Restless Multi-armed Bandit (RMAB) based solutions for this problem. Nevertheless, all past RMAB approaches assume that the participants' behaviour follows the Markov property. We demonstrate significant deviations from the Markov assumption on real-world data on a maternal health awareness program from our partner NGO, ARMMAN. Moreover, we extend RMABs to continuous state spaces, a previously understudied area. To tackle the generalised non-Markovian RMAB setting we (i) model each participant's trajectory as a time-series, (ii) leverage the power of time-series forecasting models to learn complex patterns and dynamics to predict future states, and (iii) propose the Time-series Arm Ranking Index (TARI) policy, a novel algorithm that selects the RMAB arms that will benefit the most from an intervention, given our future state predictions. We evaluate our approach on both synthetic data, and a secondary analysis on real data from ARMMAN, and demonstrate significant increase in engagement compared to the SOTA, deployed Whittle index solution. This translates to 16.3 hours of additional content listened, 90.8% more engagement drops prevented, and reaching more than twice as many high dropout-risk beneficiaries.
BibTeX
@inproceedings{danassis2023limited,
  author = {Panayiotis Danassis and Shresth Verma and Jackson A. Killian and Aparna Taneja and Milind Tambe},
  title = {{Limited Resource Allocation in a Non-Markovian World: The Case of Maternal and Child Healthcare}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/660},
}
Figure