Technical Summary: Learning in Markovian Bandits with Non-observable States and Constrained Decision Epochs

1. Problem Definition

This paper addresses the problem of regret minimization in Markovian bandits under two specific constraints:

1. Non-observable States: The controller does not observe the internal state of the arms (Markov chains). The only feedback available is the reward generated by the activated arm. This corresponds to a "full bandit feedback" setting where the state space is hidden.
2. Constrained Decision Epochs: The controller cannot switch arms arbitrarily at every time step. Instead, switching is only permitted at specific decision epochs ($\tau_i$), which are stopping times determined by the stream of rewards. Specifically, the controller must remain committed to an arm until a specific signal (e.g., a non-zero reward) is received.

The arms are modeled as Markov Decision Processes (MDPs) where the transition dynamics depend on whether the arm is active or passive. The system evolves such that non-activated arms continue to transition according to their passive kernels ($p^0_a$), while activated arms transition according to active kernels ($p^1_a$).

2. Learning Framework and Benchmark

The authors restrict their analysis to a "pure regret" benchmark.

• Pure Policies: A policy is defined as "pure" if it selects a single arm from the start to the finish of the learning horizon without ever switching.
• Regret Definition: The regret is the difference between the cumulative reward of the learning algorithm and the cumulative reward of the best pure policy (the arm with the highest asymptotic gain).

Motivation for Pure Policies:
While pure policies are generally sub-optimal for "restless" bandits (where non-activated arms evolve), the authors introduce a class of bandits called self-degrading restless bandits. In these instances, if an arm is left inactive, its expected bias (a measure of deviation from the mean reward) tends to decrease or stay constant relative to the controller's observations. The paper proves that for self-degrading bandits, pure policies are asymptotically optimal. This class generalizes "rested" bandits (where inactive arms freeze) and includes non-trivial restless examples like non-preemptive Gilbert-Elliott channels and Nerlove-Arrow models.

3. Methodology: UCB-NOM

The paper proposes UCB-NOM (Upper Confidence Bound for Non-Observable Markovian bandits), an optimistic algorithm inspired by the UCB principle.

Key Components of UCB-NOM:

1. Empirical Gain Estimator: The algorithm estimates the gain ($g_a$) of an arm $a$ by averaging the rewards collected when that arm was active.
2. Optimistic Index Construction: To handle the non-observability of states and the constraints, the algorithm constructs an optimistic upper bound $\tilde{g}_a(t)$ for the true gain. This index includes:
   • The empirical mean reward.
   • An exploration bonus (confidence interval) that accounts for:
     • The number of pulls ($N_a(t)$).
     • The number of times the algorithm switched to arm $a$ (switching cost).
     • The bias span ($sp(b_a)$) of the arm's Markov chain, which quantifies the maximum deviation of the bias function.
3. Doubling Trick: To satisfy the "rarely switching" property required for theoretical guarantees, the algorithm employs a doubling trick. Once an arm is selected, it is played until the number of its visits doubles. This ensures the number of switches grows logarithmically with the number of pulls.

Theoretical Challenges Addressed:

• Non-observability: Unlike previous works (e.g., RCA by Tekin & Liu) that rely on observing states to trigger regeneration cycles, UCB-NOM cannot use regeneration. Instead, it bounds the error using the bias span and the number of switches.
• Constrained Epochs: The algorithm must account for the delay between decision epochs. The analysis assumes a bound ($C_\tau$) on the expected time until the next decision epoch.

4. Key Results and Theoretical Guarantees

A. Lower Bounds (Impossibility of Logarithmic Regret)

The paper establishes that without prior knowledge of the bandit's structure, logarithmic regret ($O(\log T)$) is unattainable for consistent, rarely-switching algorithms.

• Theorem 4: For any consistent, rarely-switching algorithm, the expected regret scales as $\omega(\log T)$ (super-logarithmic). This is proven by constructing alternative models that are indistinguishable from the true model via rewards alone but have different optimal arms, forcing the algorithm to pull suboptimal arms excessively to distinguish them.

B. UCB-NOM Performance (General Case)

• Theorem 6: UCB-NOM achieves a regret bound of $O(f(T)^2 \log T)$, where $f(T)$ is a "span proxy" function that diverges to infinity.
• Significance: By choosing $f(T)$ to diverge arbitrarily slowly, UCB-NOM can approach the idealistic logarithmic regime arbitrarily closely, effectively matching the super-logarithmic lower bound.

C. Performance with Prior Knowledge (Bounded Bias Span)

If the algorithm is provided with a known upper bound $D$ on the bias span of all arms (and the decision epoch delay), the performance improves significantly.

• Theorem 8 (Instance-Dependent): With a fixed span proxy $f \equiv D$, UCB-NOM achieves $O(\log T)$ instance-dependent regret.
• Theorem 9 (Worst-Case): Under the same bounded span assumption, the algorithm achieves a worst-case regret of $O(\sqrt{T \log T})$.

D. Tuning and Confidence Parameters

The paper analyzes the choice of the confidence parameter $\delta(t)$. It suggests that being "under-optimistic" (choosing a smaller $\delta(t)$ to widen confidence intervals) is preferable in Markovian settings compared to stochastic bandits. This is because the noise in Markovian estimators can be larger than the reward variance suggests due to the bias span, requiring larger exploration bonuses to maintain the optimistic property.

5. Significance and Contributions

The paper claims the following contributions:

1. Problem Formulation: It formalizes a learning setting combining non-observable states and endogenous constrained decision epochs, motivated by communication networks (e.g., non-preemptive channel scheduling).
2. Self-Degrading Bandits: It identifies and defines a class of restless bandits where pure policies are optimal, justifying the use of pure regret as a benchmark.
3. Fundamental Limits: It proves that the non-observability of states combined with constrained epochs inherently prevents logarithmic regret in the general case, establishing a super-logarithmic lower bound.
4. Algorithm Design: It introduces UCB-NOM, an algorithm that achieves near-optimal regret without state observation. Crucially, the regret bounds do not depend on the number of states ($|S_a|$) of the underlying Markov chains, but rather on the bias span.
5. Structural Insights: It demonstrates that with a simple prior knowledge (a bound on the bias span), the classical logarithmic regret guarantees of stochastic bandits can be recovered, suggesting that state non-observability is a "mild inconvenience" in self-degrading settings provided structural bounds are known.

The authors conclude that while the setting is more complex than standard stochastic bandits, the proposed framework and algorithm provide robust theoretical guarantees without requiring the complex techniques typically associated with Partially Observable Markov Decision Processes (POMDPs), provided one adheres to the pure regret benchmark.