線性上下文賭博機罕見參數更新的實用最優演算法

研究論文探討在罕見參數更新情境下的線性上下文賭博機問題。在此設定中，學習者僅能在少數更新時間點將獎勵反饋納入參數估計，但仍需線上觀察上下文並依序選擇動作。論文澄清了文獻中常被混淆的實用區別：許多「嚴格批次」方法進一步限制了區間內的上下文適應性，導致動作規則無法依賴已實現的上下文或動作序列。針對線性上下文賭博機，研究提出兩個實用演算法，僅需 O(log log T) 次參數更新。第一個演算法 BLCE-G 在靜態排程下達到極小極大最優遺憾（在 T 的多項式對數因子內），同時適用於小 K 和大 K 制度。第二個演算法 BLCE 移除了近似 G 最優設計步驟——這是先前嚴格批次靜態網格方法的主要計算瓶頸——但仍保持極小極大最優遺憾，並在最優演算法中實現已知最低運行時間複雜度。研究進一步將這些罕見更新和計算原則擴展到廣義線性上下文賭博機。整體而言，論文提出的統計最優演算法在 O(log log T) 參數更新下，同時在實踐中具備計算效率。