批次隨機線性Bandits與1位元通信約束

研究論文提出一個關於隨機線性Bandits的新模型，結合了批次處理和1位元通信約束。在這個設定中，時間範圍被分為等長的批次，每個批次中學習者發送多個臂拉請求給代理，代理觀察對應的獎勵後，只回應一個位元的反饋給學習者。論文建立了最小最大遺憾下界，顯示由於1位元通信瓶頸，即使在無噪音情況下，遺憾也不可避免地受到限制。作者發展了兩個基於G-最優設計和1位元均值估計的分階段消除算法：第一個算法在特定條件下達到對數因子內的匹配下界，第二個算法通過安全臂識別和暖啟動程序，在廣泛的縮放範圍內實現近似最優遺憾。這些結果表明，即使批次大小達到Θ(√T)時，每個批次一個位元的反饋也足以在廣泛的縮放範圍內接近無約束線性Bandits的最小最大遺憾。