Abstract
This paper introduces a novel framework for "restless" hidden Markov bandits where rewards are linear and the system state is not directly observable. By leveraging structural side information—specifically, a global Markovian state shared across arms and unique arm-specific parameters—the authors develop an algorithm that achieves logarithmic regret even in high-dimensional action spaces, effectively overcoming the "curse of dimensionality" that plagues traditional bandit solvers.
Problem Statement: The Challenge of Hidden States and High Dimensionality
In Multi-Armed Bandit (MAB) problems, the "Restless" variant is particularly challenging because the state of every arm evolves over time, regardless of whether it is pulled. Most existing work assumes the decision-maker knows the system state before acting. However, in real-world applications like cognitive radio networks, the state is often "hidden"—the learner only receives clues about the state through observed rewards.
Furthermore, when the set of possible actions is a complex geometric shape, such as a convex polytope, the number of extreme points (vertices) grows exponentially with the number of dimensions. Standard algorithms usually scale with the number of these vertices, making them computationally prohibitive for high-dimensional problems. The authors aim to bridge this gap by creating a learner that is both state-blind and efficient in high dimensions.
Methodology: Leveraging Linear Structure and Structural Side Information
The authors propose Algorithm 1, an Upper Confidence Bound (UCB) reinforcement learning approach tailored for this specific structure. The key components include:
- Structural Decomposition: The model assumes the reward is the inner product of an action vector and a state-dependent parameter. The state is split into a "global" state (common to all arms, following a Markov chain) and an "arm-specific" state (unique to each arm, i.i.d.).
- Probability Estimation over Reward Estimation: Instead of trying to estimate the expected reward for every possible action-state combination, the algorithm estimates the transition probabilities of the global Markov chain and the probability distributions of the arm-specific parameters.
- $ε$-Optimal State Recovery: Since the state is hidden, the learner must infer it from the reward. The authors use a clever trick: they choose an action slightly perturbed from the optimal one. This small "nudge" ensures that the resulting reward uniquely identifies which hidden state the system was in, allowing the learner to update its internal model without sacrificing significant performance.
- Confidence Intervals: The algorithm maintains confidence bounds on the estimated distributions and only updates its policy when these bounds shrink significantly, reducing computational overhead.
Experimental Results and Performance Analysis
The paper validates the theoretical bounds using two synthetic setups:
- Setup 1: A 2-dimensional action space (a square) with 2 arms and 2 global states.
- Setup 2: A 5-dimensional action space (a hypercube) with 4 arms and 3 global states, testing the algorithm's ability to handle exponential growth in vertices (32 vertices for a 5D hypercube).
Key Findings:
- Logarithmic Regret: The authors prove that the expected regret grows as $O(\log T)$, the gold standard for efficiency in bandit problems.
- Dimensionality Independence: Crucially, the regret does not depend on the number of extreme points in the action space.
- Performance Gain: In Setup 2, Algorithm 1 achieved regret nearly an order of magnitude lower than standard UCRL implementations that ignored the linear structure.
- State Recovery Validation: Numerical results confirmed that the state recovery scheme tracks the hidden Markovian process accurately.
Conclusion and Future Directions
The proposed framework demonstrates that by focusing on underlying state distributions rather than individual action vertices, one can achieve high efficiency in high-dimensional restless bandit problems. While the results are promising, future work could extend this model to continuous state spaces or "weakly communicating" Markov chains. Additionally, addressing potential communication overhead or feedback delays in resource-constrained environments remains an open challenge.
Summary updated