Abstract
Motivated by runtime verification of QoS requirements in self-adaptive and self-organizing systems that are able to reconfigure their structure and behavior in response to runtime data, we propose a QoS-aware variant of Thompson sampling for multi-armed bandits. It is applicable in settings where QoS satisfaction of an arm has to be ensured with high confidence efficiently, rather than finding the optimal arm while minimizing regret. Preliminary experimental results encourage further research in the field of QoS-aware decision making.
Introduction
In modern self-adaptive systems, such as autonomous smart factories or reconfigurable robotic swarms, decision-making agents must frequently select new configurations in response to environmental shifts or hardware failures. These decisions are often constrained by strict Quality of Service (QoS) requirements, such as maximum error rates or minimum throughput.
Traditional Multi-Armed Bandit (MAB) algorithms, like Thompson Sampling (TS), are designed to minimize cumulative regret by identifying the single optimal arm. However, in safety-critical engineering contexts, the priority is often not to find the absolute best configuration, but to quickly identify and verify any configuration that satisfies safety constraints with high confidence. Standard exploration strategies can lead to excessive risk-taking, potentially violating QoS requirements during the learning phase. This paper introduces QoS-Aware Thompson Sampling (QATS) to address this gap.
Methodology: QoS-Aware Thompson Sampling (QATS)
QATS modifies the selection logic of standard Thompson Sampling to prioritize safety and verification. While standard TS maintains a belief distribution (typically a Beta distribution for Bernoulli bandits) and selects the arm with the highest random sample, QATS introduces a risk-averse selection criterion.
For each arm $i$, the algorithm calculates two key probabilities based on the current belief distribution:
- $p_v$ (Violation Probability): The probability that the true performance of the arm violates the QoS requirement $q$.
- $p_u$ (Underestimation Probability): The probability that the current sample drawn from the distribution is an underestimation of the true performance.
Instead of maximizing the sample value directly, QATS selects the arm that maximizes the ratio $o = p_u / p_v$. This "defensive sampling" approach favors arms that are likely to be safe ($low\ p_v$) and for which the current estimate is conservative ($high\ p_u$).
Experimental Evaluation
The authors evaluated QATS against standard Thompson Sampling using synthetic Bernoulli bandit experiments. The setup involved a four-armed bandit where success probabilities were randomly instantiated between 0 and 0.2. The QoS requirement was set at $q = 0.1$. The performance was measured over 1000 decision steps and averaged across 350 independent runs to ensure statistical significance.
Key Results
The experimental results demonstrate that QATS effectively shifts the focus from optimality to verification.
- Rapid Confidence Gains: QATS reached higher levels of average confidence regarding QoS satisfaction significantly faster than the standard TS baseline.
- Risk Mitigation: Most importantly, QATS drastically reduced the cumulative risk. As shown in the performance metrics, the probability of selecting an arm that actually violates the QoS requirement was consistently lower for QATS throughout the trial.
Discussion and Future Work
QATS represents a shift from the traditional exploration-exploitation tradeoff to an exploration-verification tradeoff. By prioritizing the verification of promising candidates, the algorithm establishes QoS compliance more rapidly, making it better suited for industrial applications where safety violations carry high costs.
As a preliminary study, several avenues for future research remain. The current model relies on simple Bernoulli distributions; extending QATS to handle continuous variables (like latency) and multi-dimensional QoS requirements is a priority. Additionally, the authors aim to provide formal theoretical bounds for QATS and explore its integration into more complex decision structures, such as Monte Carlo Tree Search (MCTS).
Summary updated