[Paper] LP 기반 샘플링 정책 for Multi-Armed Bandits with Side-Observations and Stochastic Availability

Source: arXiv - 2603.26647v1

Overview

이 논문은 고전적인 다중 팔 밴딧(MAB) 문제에 현실적인 변형을 적용합니다. 행동(팔)들이 부관측 네트워크를 통해 연결되어 있으며, 항상 임의의 팔 집합만이 이용 가능합니다. 이는 사용자가(팔이) 오프라인일 수 있지만, 그들이 제공하는 정보가 친구들의 선호도를 밝혀줄 수 있는 온라인 플랫폼과 같은 상황을 모델링합니다. 저자들은 Upper‑Confidence‑Bound(UCB) 아이디어와 선형 계획법(LP) 단계를 결합하여 이러한 제약 하에서 효율적으로 탐색 방법을 결정하는 새로운 알고리즘 UCB‑LP‑A를 소개합니다.

주요 기여

• Formal model: 부수 관측과 확률적 팔 가용성을 갖는 확률적 다중 무장 밴딜(MAB) 문제에 대해, 각 팔이 어떤 알려지지 않은 보상 파라미터를 드러내는지를 포착하는 이분 그래프를 사용한 모델.
• UCB‑LP‑A algorithm: (i) 선형 계획법(LP)을 이용해 실현 가능한 활성화 집합에 대한 최적 샘플링 분포를 계산하고, (ii) 활성 집합 내에서 팔을 선택하기 위해 UCB 스타일의 지수를 적용하는 새로운 정책.
• Regret analysis: (a) 그래프 구조(얼마나 많은 팔이 정보를 공유하는가)와 (b) 팔의 활성화 확률을 명시적으로 반영하는 증명 가능한 상한을 제공한다.
• Empirical validation: 부수 관측을 무시하거나 가용성을 정적으로 취급하는 기존 휴리스틱보다 UCB‑LP‑A가 더 우수함을 보여주는 시뮬레이션 결과.

Methodology

1. Problem formulation

   • There are (K) arms and a set of unknown reward means ({\mu_i}).
   • A bipartite graph (G = (A, U, E)) connects each arm (a \in A) to a subset of unknowns (u \in U). Pulling arm (a) yields a noisy observation of every (\mu_u) for which ((a,u) \in E).
   • At each round (t), a random activation set (\mathcal{S}_t \subseteq A) is drawn according to known probabilities (e.g., each arm independently available with probability (p_a)). The learner can only choose an arm from (\mathcal{S}_t).

2. Linear‑programming (LP) layer

   • The authors construct an LP that, given the activation distribution, finds a sampling distribution (\mathbf{x}) over arms that minimizes the total expected number of pulls needed to estimate all unknowns within a target confidence.
   • Constraints enforce that, for each unknown (\mu_u), the expected number of observations (summing over arms that can reveal it and over activation probabilities) meets a required information budget.

3. UCB‑LP‑A policy

   • Exploration phase: Use the LP solution to decide how many times each arm should be sampled in expectation.
   • Exploitation phase: Within the currently active set (\mathcal{S}_t), compute a UCB index for each arm based on its empirical mean and confidence width (standard (\sqrt{\frac{2\log t}{N_a(t)}}) term).
   • Selection rule: Pick the arm in (\mathcal{S}_t) whose scaled UCB index (scaled by the LP‑derived target frequency) is highest. This ensures that arms that are under‑sampled relative to the LP plan get priority.

4. Regret bound derivation

   • By coupling the LP‑derived target frequencies with the classic UCB analysis, the authors bound the cumulative regret as
     [ R(T) = O!\Bigl(\sum_{u\in U} \frac{\log T}{\Delta_u} \cdot \frac{1}{\sum_{a\in N(u)} p_a}\Bigr), ]
     where (\Delta_u) is the sub‑optimality gap for unknown (u) and (p_a) is the activation probability of arm (a). The term (\sum_{a\in N(u)} p_a) captures how often the network can provide information about (u).

결과 및 발견

• Synthetic graphs (dense vs. sparse side‑observation structures) show that UCB‑LP‑A’s regret scales inversely with the effective availability of each unknown, confirming the theoretical bound.
• Baseline comparisons:
  • UCB‑NoSide: side‑observations를 무시 → 특히 밀집 그래프에서 후회가 더 커짐.
  • Greedy‑Avail: LP‑기반 샘플링 빈도를 무시 → 일부 팔이 거의 사용되지 않을 때 성능 저하.
• Performance gain: 모든 테스트 시나리오에서 UCB‑LP‑A는 최상의 베이스라인에 비해 누적 후회를 30‑70 % 감소시키며, 특히 (i) side‑information이 풍부하고 그리고 (ii) 활성화 확률이 이질적일 때 가장 큰 개선을 보인다.

실용적 함의

• Online recommendation / ad placement: 플랫폼은 사용자를 팔로우(arm)처럼 취급할 수 있다; 사용자가 오프라인이라도 그 친구들의 상호작용(부관측)이 모델에 정보를 제공한다. UCB‑LP‑A는 시스템이 현재 온라인인 사용자들 사이에 제한된 쿼리 예산을 어떻게 할당하여 가장 많이 학습할지 알려준다.
• Edge‑computing and IoT: 센서는 간헐적으로 접근 가능할 수 있다. 상관된 측정값들의 네트워크를 모델링함으로써, 컨트롤러는 접근 가능한 센서 중 어느 것을 폴링하여 전체 필드를 빠르게 추정할지 결정할 수 있다.
• A/B testing with flaky traffic: 트래픽 소스(예: 지리적 지역)가 나타나거나 사라질 때, LP 계층이 자동으로 샘플링 계획의 가중치를 재조정하여 드물게 보이는 소스에 대한 과도한 탐색을 방지한다.
• Implementation simplicity: LP는 작으며(변수 = 팔) 오프라인으로 해결하거나 주기적으로 업데이트할 수 있다; 라운드당 계산은 활성 집합에 대한 UCB 인덱스 평가만으로, 이는 이미 많은 밴딧 라이브러리에서 표준적으로 제공된다.

제한 사항 및 향후 연구

• 알려진 활성화 분포: 분석은 확률 (p_a) (또는 활성화 집합에 대한 분포)가 사전에 알려져 있다고 가정합니다. 실제로는 이를 온라인으로 추정해야 할 수도 있습니다.
• 선형 보상 모델: 사이드 관측 그래프는 이진 형태이며 (팔이 정보를 공개하거나 하지 않음). 가중치가 있거나 노이즈가 있는 관측 구조로 확장하면 적용 범위를 넓힐 수 있습니다.
• LP의 확장성: 수십 개의 팔에 대해서는 적당하지만, 수천 개와 같이 매우 큰 팔 집합의 경우 근사 LP 솔버나 분해 기법이 필요할 수 있습니다.
• 비정상 환경: 현재의 regret 한계는 정적인 보상 평균에 대해 성립합니다; 선호도 변화나 시간에 따라 변하는 가용성을 다루는 것은 아직 해결되지 않은 과제입니다.

저자

• Ashutosh Soni
• Peizhong Ju
• Atilla Eryilmaz
• Ness B. Shroff

논문 정보

• arXiv ID: 2603.26647v1
• 카테고리: cs.LG, eess.SY
• 출판일: 2026년 3월 27일
• PDF: PDF 다운로드