이종 비동기 다중 플레이어 밴딧에서 최적 정책 근사화

요약

본 논문은 인지 무선 네트워크 응용 분야에서 중요한 이종 비동기 다중 플레이어 밴딧(MMAB) 문제를 다룹니다. 기존 연구가 동종 플레이어에 집중했던 것과 달리, 본 연구는 활성화 확률이 다른 플레이어의 최적 할당 계산을 목표로 합니다. 논문은 이 문제의 NP-난하성을 증명하고, 그리디 알고리즘을 통해 최적 할당의 근사치를 제공합니다.

핵심 포인트

• 비동기 MMAB는 실제 분산 네트워크를 반영하는 실용적인 문제입니다.
• 활성화 확률이 다른 이종 플레이어 설정은 미해결 문제였습니다.
• 제안된 그리디 알고리즘은 최적 할당의 근사치를 제공합니다.
• 플레이어 순서 처리 시, 근사 보장이 $\frac{1}{\sqrt{e}}$까지 향상됩니다.