Indexability of Restless Bandit Problems and Optimality of Whittle's Index for Dynamic Multichannel Access

论文链接: Indexability of Restless Bandit Problems and Optimality of Whittle's Index for Dynamic Multichannel Access

Main

Contribution

• establish the indexability and obtain Whittle’s index in closed-form
• WI policy 在特定条件(仅 relaxed constraint)下的最优性
• equivalency between Whittle’s index policy and the myopic policy
• 在 stochastically identical arms 下的鲁棒性（无需具体转移概率数值，仅需 $p_{11},p_{01}$ 的大小比较）

Details

Introduction

• Restless Multi-armed Bandit Process is a generalization of the classical Multi-armed Bandit Processes

• Whittle’s index policy is the optimal solution to RMBP under a relaxed constraint: the number of activated arms can vary over time provided that its average over the infinite horizon equals to $K$.

• Dynamic Multichannel Access
  probing N independent Markov chains. The objective is to design an optimal policy that governs the selection of K chains at each time to maximize the long-run reward.
  

  The above general problem arises in a wide range of communication systems, including cognitive radio networks, downlink scheduling in cellular systems, opportunistic transmission over fading channels, and resource-constrained jamming and anti-jamming.

• when arms are stochastically identical, the approximation factor of Whittle’s index policy ${\rho }^{WI}\ge K/N$ when $p_{11}\ge p_{01}$ and at least $max\{1/2,K/N\}$ when $p_{11}<p_{01}$.

• algorithm runs in at most $O(N(logN{)}^2)$ time to compute the performance upper bound

• when arms are stochastically identical, Whittle’s index policy has a semi-universal structure that obviates the need to know the Markov transition probabilities. The only required knowledge about the Markovian model is the order of $p_{11}$ and $p_{01}$.
  This semiuniversal structure reveals the robustness of Whittle’s index policy against model mismatch and variations.

PROBLEM STATEMENT AND RESTLESS BANDIT FORMULATION

• $N$ independent Gilbert-Elliot channels, each with transmission rate $B_i$
• $U(t)$ denote the set of $k$ channels chosen in slot $t$.

• $\mathrm{\Omega }(t)\triangleq [{\omega }_1(t),\cdots ,{\omega }_N(t)]$
• policy $\pi$ : $\mathrm{\Omega }(t)\to U(t)$ is a function that maps from the belief vector $\mathrm{\Omega }(t)$ to the action $U(t)$ in slot $t$.
• performance measure
  expected total discounted reward over the infinite horizon ${\mathbb{E}}_{\pi }[{\mathrm{\Sigma }}_{t=1}^{\mathrm{\infty }}{\beta }^{t-1}{R}_{\pi (\mathrm{\Omega }(t))}(t)|\mathrm{\Omega }(1)]$
• $(\mathrm{\Omega }(1),\{{\mathbf{P}}_i{\}}_{i=1}^N,\{B_i{\}}_{i=1}^N,\beta =1)$: denote the RMBP with the average reward criterion

这里考虑的是最大化 reward 而非最小化 cost，因此后面的 subsidy 也是用于补助 passive arm

INDEXABILITY AND INDEX POLICIES

An index policy assigns an index for each state of each arm to measure how rewarding it is to activate an arm at a particular state.
A myopic policy is a simple example of strongly decomposable index policies. This policy ignores the impact of the current action on the future reward, focusing solely on maximizing the expected immediate reward.

• $V_{\beta ,m}(w)$, the value function represents the maximum expected total discounted reward that can be accrued from a single-armed bandit process with subsidy $m$ when the initial belief state is $w$.
• 动态规划

• The optimal policy is essentially given by an optimal partition of the state space $[0,1]$ into a passive set $\{w:u^{\ast }(w)=0\}$ and an active set $\{w:u^{\ast }(w)=1\}$, where $u^{\ast }(w)$ denotes the optimal action under belief state $w$.
• The passive set $\mathcal{P}(m)$ under subsidy $m$

• indexable&Whittle's index定义

• Whittle’s index policy achieves a near-optimal performance while the myopic policy suffers from a significant performance loss.
  

WHITTLE’S INDEX UNDER DISCOUNTED REWARD CRITERION

• Properties of Belief State Transition
  convergence of ${\mathcal{T}}^k(w)$ to the stationary distribution $w_0=p_{01}/(p_{01}+p_{10})$ for Positively correlated channel ($p_{11}\ge p_{01}$) and Negatively correlated channel ($p_{11}\le p_{01}$)
  

• closed-form expression$$V_{\beta ,m}(\omega )=\frac{1-{\beta }^{L(\omega ,{\omega }_{\beta }^{\ast }(m))}}{1-\beta }m+{\beta }^{L(\omega ,{\omega }_{\beta }^{\ast }(m))}{V}_{\beta ,m}({\mathcal{T}}^{L(\omega ,{\omega }_{\beta }^{\ast }(m))}(\omega );u=1)$$where $L(w,w^{\prime })$ is the minimum amount of time required for a passive arm to transit across $w^{\prime }$ starting from $w$.$$L(\omega ,{\omega }^{\prime })=\{\begin{array}{ll}0,& \mathrm{if}\omega >{\omega }^{\prime }\\ 1,& \mathrm{if}\omega \le {\omega }^{\prime }\mathrm{and}\mathcal{T}(\omega )>{\omega }^{\prime }\\ \mathrm{\infty },& \mathrm{if}\omega \le {\omega }^{\prime }\mathrm{and}\mathcal{T}(\omega )\le {\omega }^{\prime }\end{array}$$
• Whittle's Index
  Whittle’s index is the subsidy $m$ that is the solution to the following equation of $m$$$\underset{V_{\beta ,m}(\omega ;u=1)}{\underbrace{\omega +\beta (\omega V_{\beta ,m}(p_{11})+(1-\omega )V_{\beta ,m}(p_{01}))}}=\underset{V_{\beta ,m}(\omega ;u=0)}{\underbrace{m+\beta V_{\beta ,m}({\mathcal{T}}^1(\omega ))}}$$
  • $W_{\beta }(w)$ is a monotonically increasing function of $w$.
  • For a positively correlated channel ($p_{11}\ge p_{01}$), $W_{\beta }(w)$ is piecewise concave with countable pieces.
  • For a negatively correlated channel ($p_{11}\le p_{01}$), $W_{\beta }(w)$ is piecewise convex with finite pieces.

• Performance
  • optimal policy for RMBP under the relaxed constraint.
  • upper bound of the optimal performance
    $m^{\ast }=sup\{m:\frac{d(G_{\beta ,m}(\mathrm{\Omega }(1)))}{dm}={\mathrm{\Sigma }}_{i=1}^N{D}_{\beta ,m}^{(i)}({\omega }_i(1))-\frac{(N-K)}{1-\beta }\le 0\}$
    $\begin{array}{r}{G}_{\beta ,m^{\prime }}(\mathrm{\Omega }(1)))-G_{\beta ,m^{\ast }}(\mathrm{\Omega }(1))\le \frac{K}{1-\beta }(m^{\prime }-m^{\ast })\le \frac{\delta K}{1-\beta }=ϵ\end{array}$
    
    
• Algorithm with complexity $O(N^2\log N)$
  

WHITTLE’S INDEX POLICY FOR STOCHASTICALLY IDENTICAL CHANNELS

Based on the equivalency between Whittle’s index policy and the myopic policy for stochastically identical arms, we can analyze Whittle’s index policy by focusing on the myopic policy which has a much simpler index form.

• Simplicity of Whittle's index in this case
  • channel selection is reduced to maintaining a simple queue structure that requires no computation and little memory.
  • a semi-universal structure; it can be implemented without knowing the channel transition probabilities except the order of $p_{11}$ and $p_{01}$.
  • Shows robust
• 
• Performance
  • For negatively correlated channels, Whittle’s index policy achieves at least half the optimal performance.
  • For positively correlated channels, the approximation factor can be further improved under certain conditions on the transition probabilities. Specifically, we have $\eta \ge 1-p_{11}+w_0$.

Notes

Comment: submitted to IEEE Transactions on Information Theory
2024-09-24 | Zotero

Memo

• 📗 (RMBP

• 📗 dynamicmultichannel access,

• 📗 we establish the indexability and obtain Whittle’s index in closed-form for both discountedand average reward criteria

• 🏷 When these Markov chains are stochastically identical, we show that Whittle’s index policy is optimal under certain conditions

• 📗 optimality and the semi-universalstructure result

• 📗 For non-identical channels, we develop efficient algorithms for computing a performance upper bound given by Lagrangian relaxation

• 📘 Restless Multi-armed Bandit Process (RMBP) is a generalization of the classical Multi-armedBandit Processes (MBP)

• 📘 Closed-form Expression of

© 2024 LiQ :) 由 Obsidian&Github 强力驱动