PaperlayerView exact revision on arXiv

Source-linked AI summary

Approximation Algorithms for Restless Bandit Problems

Sudipto Guha, Kamesh Munagala, Peng Shi

arXiv:0711.3861v5cs.DS

TL;DR

The paper studies approximation for Feedback MAB, a partially observable restless bandit problem where arm states evolve while only becoming observed when played. It develops a duality-based index policy achieving a 2 + ϵ approximation for Feedback MAB and a 2 approximation for Monotone bandits.

  • Problem

    Restless bandits and related POMDPs are difficult to approximate, while Feedback MAB lacks optimal greedy index policies despite its practical relevance.

  • Method

    The paper develops a duality-based technique that constructs an index policy from a Lagrangian or dual solution, extending it to Monotone bandits.

  • Results

    The resulting policy gives a 2 + ϵ approximation for Feedback MAB and a 2 approximation for Monotone bandits, providing the first O(1) approximations for these problem classes.

  • Takeaways & Limitations

    The technique initiates approximation-algorithm study for non-trivial restless bandit and POMDP instances and extends to settings with blocking plays and switching costs.

  • Takeaways & Limitations

    Whittle index policies can perform arbitrarily poorly for non-preemptive machine replenishment, even though they are a 1.51 approximation when repairs are preemptible.

Abstract

from arXiv · show

The restless bandit problem is one of the most well-studied generalizations of the celebrated stochastic multi-armed bandit problem in decision theory. In its ultimate generality, the restless bandit problem is known to be PSPACE-Hard to approximate to any non-trivial factor, and little progress has been made despite its importance in modeling activity allocation under uncertainty. We consider a special case that we call Feedback MAB, where the reward obtained by playing each of n independent arms varies according to an underlying on/off Markov process whose exact state is only revealed when the arm is played. The goal is to design a policy for playing the arms in order to maximize the infinite horizon time average expected reward. This problem is also an instance of a Partially Observable Markov Decision Process (POMDP), and is widely studied in wireless scheduling and unmanned aerial vehicle (UAV) routing. Unlike the stochastic MAB problem, the Feedback MAB problem does not admit to greedy index-based optimal policies. We develop a novel and general duality-based algorithmic technique that yields a surprisingly simple and intuitive 2+epsilon-approximate greedy policy to this problem. We then define a general sub-class of restless bandit problems that we term Monotone bandits, for which our policy is a 2-approximation. Our technique is robust enough to handle generalizations of these problems to incorporate various side-constraints such as blocking plays and switching costs. This technique is also of independent interest for other restless bandit problems. By presenting the first (and efficient) O(1) approximations for non-trivial instances of restless bandits as well as of POMDPs, our work initiates the study of approximation algorithms in both these contexts.

1 Introduction

The paper develops efficient constant-factor approximation algorithms for Feedback MAB, a partially observed restless-bandit problem, and generalizes the technique to broader constrained settings. It provides a 2 + ϵ approximation for Feedback MAB, a 2 approximation for Monotone bandits, and extensions covering several practical variants.

  • Introduction: The approach addresses restless-bandit hardness by providing the first O(1) approximations for a large class of commonly studied problems.General restless bandits are PSPACE-hard even to approximate non-trivially, motivating tractable special cases.
  • Results and Roadmap: 2 + ϵ approximation is provided for Feedback MAB, which is both a restless bandit problem and a partially observable Markov decision problem.Feedback MAB models arms whose states evolve over time and are revealed only when played, making greedy index policies generally non-optimal.
  • Technical Contributions: The algorithm solves a balanced Lagrangian relaxation, converts its solution into a feasible index policy, and analyzes reward through amortized accounting.Its computation time is comparable to that of Whittle-index methods because both rely on solving a Lagrangian.
  • Results and Roadmap: Unlike the Whittle index, the technique uses one global Lagrange multiplier and remains applicable with varying-duration blocking plays, switching costs, and observation costs.The paper also identifies a general Monotone condition under which the technique applies.
  • Results and Roadmap: The technique generalizes to Monotone bandits, yielding a 2 approximation under separability and monotonicity, while their absence causes hardness or an unbounded integrality gap.The construction uses a balance constraint in the dual of a natural LP relaxation and derives the index policy from an optimal dual solution.
  • Specific Results: The paper derives a 2-approximation for non-preemptive machine replenishment, where the Whittle index can perform arbitrarily poorly.It also supplies an e/(e −1) integrality-gap instance showing that the Feedback MAB analysis is nearly tight.

2 The FEEDBACK MAB Problem

FEEDBACK MAB models independent two-state Markov arms whose states are partially observed, making greedy and generally optimal index policies unavailable. Whittle’s LP relaxes the one-play-per-step constraint and upper-bounds the optimal policy while remaining solvable to arbitrary precision in polynomial time.

  • Problem formulation: FEEDBACK MAB arms evolve through bursty good/bad Markov states, with the player observing an arm’s state only when it is played.A state can be encoded as the last observed state and the number of steps since observation.
  • Limits of index policies: The optimal policy has an Ω(n) gap over the myopic index policy and an Ω(1) gap over the optimal index policy.Thus, even the best index policy is generally non-optimal for FEEDBACK MAB.
  • Whittle’s LP: Whittle’s LP replaces playing exactly one arm per step with allowing multiple plays while requiring one play per step on average.The relaxation separates arms and can therefore yield an infeasible policy, but its objective upper-bounds the optimal policy value.
  • Whittle’s LP: The LP objective is at least the value of the optimal policy, so its optimum provides an upper bound for approximation analysis.The LP variables represent steady-state probabilities that an arm is in a state and is played or not played.
  • Whittle’s LP: Despite infinitely many constraints, Whittle’s LP can be solved to arbitrary precision in polynomial time by exploiting structure in its Lagrangean.The state-belief functions v_i^t and 1−u_i^t are monotonically increasing and concave in t.

2.2 Decoupling Arms via the Lagrangean

The Lagrangean removes the sole constraint coupling arms, decomposing the problem into independent single-arm reward-minus-penalty optimizations. Each arm’s optimum belongs to a threshold family whose reward and play rate admit closed-form expressions, enabling polynomial-time solution.

  • Decoupling arms: The Lagrangean charges λ for each play, removes the coupling constraint, and decomposes the problem into n independent single-arm maximization problems.Each arm maximizes expected reward minus its play penalty.
  • Characterizing the optimal single-arm policy: Each optimal single-arm policy belongs to the threshold family P_i(t), which exploits observed good states and explores after a waiting period.The never-play policy is represented by P_i(∞).
  • Solving the single-arm problems: The threshold t_i(λ), and hence H_i(λ), can be computed in polynomial time by closed-form maximization and binary search when needed.This yields an efficient solution to the Lagrangean subproblems.
  • Solving the single-arm problems: For policy P_i(t), F_i(λ,t)=R_i(t)−λQ_i(t), and the optimal excess value is H_i(λ)=max_t[R_i(t)−λQ_i(t)].The maximizing threshold t_i(λ) determines the optimal single-arm policy.
  • Solving the single-arm problems: The policy P(t) has average reward R(t)=r v_t/(v_t+tβ) and play rate Q(t)=(v_t+β)/(v_t+tβ), where v_t is the probability of being good after t steps from a bad observation.These quantities follow from the steady-state distribution of the policy’s t+1-state Markov chain.

2.3 The BALANCEDINDEX Policy

BALANCEDINDEX selects a Lagrange multiplier that balances the penalty with aggregate single-arm excess rewards, then prioritizes good and ready arms through a simple index rule. Duality and amortization show a polynomial-time 2+ε approximation.

  • Balanced multiplier: The algorithm chooses λ so that λ and the aggregate excess reward G(λ)=Σ_i H_i(λ) each provide an approximately OPT/2 contribution.A polynomial-time decreasing search uses the monotonicity of G(λ) to find λ≥(1−ε)OPT/2 and G(λ)≥OPT/2.
  • Index policy: For each arm with H_i(λ)>0, BALANCEDINDEX labels (g,1) good, bad states with t≥t_i ready, and remaining states bad.It plays good arms first, then ready arms, while ignoring bad arms; conflicts are resolved by the priority rule.
  • Guarantee: The BALANCEDINDEX policy is a 2+ε approximation to FEEDBACK MAB and can be computed in polynomial time.Its analysis links policy reward to the Whittle LP optimum through λ and the excess rewards h_i.
  • Analysis: On non-blocked steps, each arm earns at least its optimal single-arm reward, yielding h_i per step and at least λ per play under the amortization.A blocked step occurs when an arm is ready but another arm is played.
  • Analysis: When no arm is played, the policy obtains aggregate excess reward at least OPT/2; when an arm is played, that step earns at least λ≥(1−ε)OPT/2.A Lyapunov-potential argument provides an alternative generalizable proof because the potentials remain bounded over time.
  • Tightness: The Whittle LP gap can be arbitrarily close to e/(e−1)≈1.58, indicating the approximation analysis is nearly tight against this relaxation.The result concerns the gap between the LP and feasible policy performance.

3 Analyzing the Whittle Index for FEEDBACK MAB

The Whittle index is analyzed for FEEDBACK MAB, and a thresholded modification that prioritizes sufficiently valuable good states achieves a 2-approximation. The analysis connects index properties to a duality-based potential argument, including cases where non-target arms preempt target arms.

  • 3.1 Description of the Whittle Index: Whittle indices are nonnegative; Πi(g, 1) equals ri(1 −βi), while Πi(b, t) is nondecreasing in t and never exceeds Πi(g, 1).For bad states, Πi(b, t) is characterized as the largest λ for which the single-arm policy plays after t steps.
  • 3.2 The THRESHOLD-WHITTLE Policy: The policy modifies Whittle priorities by giving state (g, 1) infinite priority when its myopic reward ri(1 −βi) is at least λ.Otherwise, it retains the arm’s Whittle index.
  • 3.2 The THRESHOLD-WHITTLE Policy: THRESHOLD-WHITTLE(λ∗) is a 2-approximation for FEEDBACK MAB.The policy uses λ∗ satisfying the paper’s dual characterization, and the guarantee extends to playing M ≥1 arms simultaneously.
  • 3.2 The THRESHOLD-WHITTLE Policy: The analysis partitions arms into Type (1) arms with hi > 0 and Type (2) arms with hi = 0, with the former corresponding to the arms selected by the balanced index analysis.For Type (1) arms, the modified policy prioritizes good over ready over bad states and earns at least OPT/2.
  • 3.2 The THRESHOLD-WHITTLE Policy: When a Type (2) arm preempts a Type (1) arm, either its reward is at least λ∗ or the deferred Type (1) arm gains enough potential to preserve the approximation analysis.This accounts for plays of arms with hi = 0 without charging them potential change.

4 The General Technique: MONOTONE Bandits

MONOTONE bandits form a broad subclass of restless bandits captured by separable, monotone state-transition dynamics, including stochastic and feedback MABs. A balanced dual construction yields a 2-approximate index policy, while relaxing key assumptions causes strong hardness or LP gaps.

  • Special cases: The framework generalizes FEEDBACK MAB and stochastic MAB, with uncertainty increasing over time in the feedback setting.FEEDBACK MAB is recovered with two states and alternating transitions, while stochastic MAB is recovered by setting the escape function identically to one.
  • Model and assumptions: The model has independent arms, at most one play per step, rewards obtained on play, and infinite-horizon time-average reward as its objective.When an arm is idle, its state remains unchanged; after t idle steps, playing it yields state-dependent reward and transition behavior.
  • Model and assumptions: MONOTONE bandits allow an arm’s transition probability to factor into a time-dependent escape function and a state-transition probability.The separability property requires gi(k,j,t)=fi_k(t)qi(k,j), while the monotone property requires escape probabilities to be non-decreasing over time.
  • Policy construction: The balanced dual classifies states through potential changes, continuously exploiting good states and waiting until bad states become ready.This policy uses dual potentials and complementary slackness to determine when an arm should be played.
  • Approximation guarantee: A 2-approximation is achieved by the BALANCEDINDEX policy for MONOTONE bandits.The policy is constructed from an optimal balanced dual solution and analyzed through potentials and complementary slackness.
  • Lower bounds: The assumptions are close to necessary: relaxing monotonicity yields n^ε-hardness, while relaxing separability creates an Ω(n) Whittle-LP gap even with three states per arm.The lower bounds include NP-hardness of computing an optimal ergodic policy and an explicit instance where the LP value is Θ(1) but every feasible policy earns at most 1/n.

5 MONOTONE Bandits: Multiple Simultaneous Plays of Varying Duration

The MONOTONE-bandit framework extends to multiple simultaneous plays whose durations depend on the arm state. A modified BALANCEDINDEX policy remains a 2-approximation under these blocking and variable-duration constraints.

  • Variable-duration model: Each arm play lasts L_i_k steps, yields one reward at its beginning, and prevents that player from switching arms during the blocking period.The duration values are fixed beforehand and known to the players.
  • Balanced program: The modified linear program tracks play starts, steady-state occupancy during plays, arm-state flow balance, and an expected rate of M plays per step.The occupancy constraint sums the probability that each arm is active, while the final constraint equates rates of leaving and entering each state.
  • Policy construction: The balanced solution divides arms into U1, which are repeatedly played, and U2, which are scheduled using ready-state thresholds derived from tight dual constraints.Arms in U1 are continuously favored; U2 states are partitioned into G_i and I_i according to the sign of potential change.
  • Policy construction: The policy continuously plays eligible U1 arms and plays U2 arms in G_i until they transition into ready states I_i, preserving the simultaneous-play capacity invariant.At most M−|U1| U2 arms are maintained in G_i at any time.
  • Analysis: A Lyapunov-function argument amortizes reward and potential changes across variable-duration plays to establish the approximation bound.For U2 arms, the amortized per-step reward plus potential change equals λ+h_i; the global balance then supplies the required lower bound.
  • Guarantee: The BALANCEDINDEX policy is a 2-approximation with multiple simultaneous plays of variable duration.The guarantee applies when M players can act simultaneously and each play occupies a player for a state-dependent number of steps.

6 MONOTONE Bandits: Switching Costs

The section extends the duality-based approach to Monotone bandits with additive switching costs, producing a feasible balanced-index policy with a 2-approximation guarantee.

  • 6 MONOTONE Bandits: Switching Costs: The formulation explicitly tracks whether a play follows a switch or continuation, using separate probabilities for switched-in and same-arm plays.These variables define the LP relaxation for switching-cost variants.
  • 6 MONOTONE Bandits: Switching Costs: The balanced dual assigns a global multiplier and arm-specific quantities, with complementary slackness ensuring either sufficiently rewarding repeated play or tight state constraints.For each arm with positive h_i, one of these two structural cases holds.
  • 6 MONOTONE Bandits: Switching Costs: BALANCEDINDEX classifies states as good or ready, sticks with good arms, waits until ready states mature, and idles only when neither type is available.A state is ready after its prescribed waiting time; otherwise the policy plays any ready arm.
  • 6 MONOTONE Bandits: Switching Costs: A 2-approximation is obtained for Monotone bandits with switching costs, where closing and setup costs are subtracted from reward.The switching cost depends additively on the old arm’s closing cost and the new arm’s setup cost.
  • 6 MONOTONE Bandits: Switching Costs: The proof preserves the amortized dual accounting: waiting and playing an arm over its prescribed cycle yields reward plus potential change equal to λ + h_i per step.The switching-cost version changes the potential definition while retaining the core amortized argument.

7 FEEDBACK MAB with Observation Costs

This section handles observation costs by separating probing from reward-generating play in Feedback MAB. The resulting policy achieves a 2 + ε approximation through a balanced LP-duality construction and potential analysis.

  • 7 FEEDBACK MAB with Observation Costs: Observation costs model probing that reveals channel state while consuming energy, whereas playing deposits reward without revealing the state.This decouples information acquisition from reward collection in wireless scheduling.
  • 7 FEEDBACK MAB with Observation Costs: The LP and balanced dual use variables indexed by arm, observed state, and time since observation, with expected rewards defined from the underlying Markov state probabilities.The LP can be solved up to a 1 + ε factor.
  • 7 FEEDBACK MAB with Observation Costs: The policy uses parameters e_i, d_i, and m_i to classify arms as not ready or ready, then exploits good observations for e_i steps and probes at prescribed times.Arms with positive h_i are retained; a bad observation creates a waiting period before readiness.
  • 7 FEEDBACK MAB with Observation Costs: Potential accounting gives average reward-plus-potential change at least λ + h_i during both waiting-based and good-state exploitation stages.The two stage analyses establish this bound over m_i and e_i steps, respectively.
  • 7 FEEDBACK MAB with Observation Costs: Across the active stages, the total amortized value is at least OPT/2, and bounded potentials convert this inequality into the stated approximation guarantee.When fewer than M arms are active, non-ready arms contribute their h_i terms instead.

8 Non-Preemptive Machine Replenishment

The section applies the balancing technique to non-preemptive machine replenishment, obtaining a 2-approximation while showing that the Whittle index can fail arbitrarily badly.

  • 8 Non-Preemptive Machine Replenishment: Machines degrade through Markovian state transitions, can be sent to a non-preemptive repair queue at a cost, and yield no reward while under repair.Repair duration is geometric and at most M machines can be repaired per time step.
  • 8.3 Gap of the Whittle Index: This contrasts with the 1.51 approximation known for a restricted preemptive two-state setting, showing that non-preemption changes the index-policy behavior substantially.The earlier guarantee assumes M = 1, two states, zero broken-state reward, and preemptive repair.
  • 8 Non-Preemptive Machine Replenishment: The balanced dual assigns state potentials, machine-specific h_i values, and a global λ, with complementary slackness yielding the bound Mλ = Σ_i h_i ≥ OPT/2.The LP uses steady-state active probabilities and repair-transition probabilities.
  • 8 Non-Preemptive Machine Replenishment: The policy in Figure 15 is a 2-approximation for non-preemptive machine replenishment.The result covers general active-state sets, repair capacity M, and non-preemptive repairs.
  • 8 Non-Preemptive Machine Replenishment: Repair completion contributes λ + h_i in expected potential change, while active machines contribute h_i through reward plus potential change.If M machines are repaired, the total contribution is at least Mλ; otherwise unrepaired machines complete the Σ_i h_i bound.
  • 8.3 Gap of the Whittle Index: The Whittle index policy is arbitrarily poor even with two machines and one repair slot when repairs cannot be preempted.It may repair a broken machine for O(n^4) steps, blocking an active machine and obtaining O(1/n^3) reward versus the optimum’s 1/2.

9 Open Questions

The paper identifies extensions and complexity questions beyond its two-state Feedback MAB setting, including larger state spaces and matching hardness results.

  • 9 Open Questions: A central open question is whether the techniques extend to Feedback MAB with K > 2 states per arm.For K = 2, transition probabilities are monotone; with more states, the underlying Markov chain no longer preserves that monotonicity.
  • 9 Open Questions: The paper also asks whether matching hardness results can be established, particularly for Feedback MAB.These questions define directions for future complexity-theoretic analysis.

A Omitted Proofs

The proofs are deferred because they are lengthy and independent of the paper’s duality-based technique.

  • The proofs are deferred to preserve the paper’s flow because they are independent of the duality-based technique and lengthy.

A.1 Proof of Theorem 2.1

This section establishes that optimal behavior can be non-indexable and that myopic and index policies may suffer substantial gaps against the optimum.

  • The myopic policy can have an Ω(n) gap because it always selects the deterministic arm when all type 2 arms are bad.In that state, each type 2 arm’s myopic next-step reward is below 1, so the policy obtains long-term reward 1.
  • The optimal-policy computation uses value iteration and represents relevant states by how long ago arms 2 and 3 were observed bad.The resulting state representation is symmetric in arms 2 and 3 and is summarized by a policy table.
  • 1.46218 is the optimal policy’s average reward in the three-arm instance.The optimal policy’s decisions can switch between arms 1 and 2 depending on the state of arm 3.
  • The optimal policy is non-indexable because its choice between arms 1 and 2 depends on arm 3’s state.When arm 2 was observed bad four steps earlier, the policy plays arm 1 if arm 3 was bad two steps earlier, but arm 2 if arm 3 was bad three steps earlier.
  • The best nearby index policies achieve average rewards 1.46104 and 1.46167, and all other index policies perform worse.These evaluations imply a constant-factor gap between the optimal policy and the best index policy.

A.2 Proof of Theorem 2.6

The proof analyzes the single-arm objective F(λ, t), characterizes where its derivative can change sign, and shows that its maximizer can be found in polynomial time.

  • The single-arm value is F(λ, t) = R(t) − λQ(t), where R(t) is reward and Q(t) is the play rate.The proof uses this expression as the value of policy P(t).
  • The proof separately handles λ ≥ r and r > λ, showing in the relevant subcase that t = ∞ is optimal.
  • The derivative of F has a numerator g(t) with a unique maximum, so candidate optima occur at t = 1 or around the maximizer t3.If g(t3) is positive, the relevant candidates are 1, ⌊t3⌋, and ⌈t3⌉.
  • When the derivative is always negative, the optimum is t∗ = 1.
  • For sufficiently large t, the derivative changes sign from positive to negative, allowing binary search to locate the maximum of F.The search compares the resulting maximum with F at 1, ⌊t3⌋, and ⌈t3⌉.

A.3 Proof of Theorem 2.12

The proof characterizes Whittle’s LP through a penalty λ and single-arm policies, then evaluates a symmetric construction showing the LP value approaches its information-theoretic upper bound when nβ is small.

  • Whittle’s LP selects λ so that the aggregate expected play rate Q(λ) is approximately 1.The optimal solution uses a penalty and, when needed, a convex combination of adjacent single-arm policies.
  • The LP solution is feasible with expected play rate exactly 1, and varying λ moves the aggregate rate from n to 0.At λ = 0, all arms use t_i(λ) = 1; at λmax, all use t_i(λ) = ∞.
  • For nβ ≪1, the construction uses identical mixtures of policies P(t −1) and P(t), with P(t) always playing in state g and waiting t steps in state b.The value t is chosen so P(t) plays below rate 1/n while P(t −1) plays above it.
  • The resulting Whittle LP objective is nR(t) = 1 − Θ(n/t), with t determined from the single-arm play-rate constraint.

A.4 Proof of Lemma 3.1

The proof establishes that the single-arm threshold t_i(λ) is non-decreasing in the penalty and characterizes the state-index value Π_i(b,t) through the penalties inducing each threshold policy. It also bounds the value at (g,1) and distinguishes the Feedback MAB setting from broader Monotone bandits.

  • t_i(λ) is monotonically non-decreasing in λ.
  • Because F_i(λ,t) decreases faster in λ for smaller t, increasing the penalty shifts the maximizing threshold to some t_i(λ′) ≥ t_i(λ).
  • At state (g,1), the optimal index is Π_i(g,1) = r_i(1 − β_i): playing is optimal below this penalty, while not playing is optimal above it.
  • The argument relies on Feedback MAB’s underlying two-state process evolving regardless of plays; the corresponding claim need not hold for Monotone bandits.
  • For each state (b,t), Π_i(b,t) equals the largest penalty λ for which the optimal single-arm policy is P_i(t).
Loading 0711.3861v5…