Top-k帕累託賭博機：多目標候選集選擇的超體積遺憾
本文研究了一種隨機多目標賭博機問題，智能體每輪選擇k個臂的候選集，並觀察其d維獎勵向量（半帶狀反饋）。目標是維護一個能聯合近似帕累託前沿的小型動作子集，通過所選臂的子集支配的超體積來形式化目標。定義了α-近似超體積遺憾（α=1-1/e），並提出了基於樂觀邊際貢獻估計的貪心算法THV-UCB，給出了無間隙和有間隙的遺憾界。
在多目標優化中，決策者常常需要同時考慮多個相互衝突的目標。例如，在推薦系統中，我們希望推薦的結果既相關又多樣；在廣告投放中，則需要在點擊率和收益之間取得平衡。傳統的優化方法通常只尋找單一的最優解，但在許多實際應用中，我們更希望獲得一組能夠覆蓋帕累託前沿的多樣化解決方案。近日，arXiv上發表的論文《Top-k帕累託賭博機：多目標候選集選擇的超體積遺憾》正是針對這一問題提出了新穎的理論框架。
該論文由Nicolas Gutowski等四位研究者共同完成，將上述問題建模為隨機多目標賭博機問題。具體而言，每輪智能體從n個臂中選擇一個包含k個臂的候選集，並觀察每個所選臂的d維獎勵向量，反饋形式為半帶狀反饋（即僅觀測到所選臂的獎勵）。不同於經典賭博機問題追求單一最優臂，該研究的目標是維護一個能夠聯合近似帕累託前沿的小型動作子集。為了量化所選子集的質量，作者引入了支配超體積（dominated hypervolume）的概念，並定義了α-近似超體積遺憾，其中α=1-1/e。這一近似因子源於貪心算法對單調次模函數最大化的理論保證。
為了解決這一挑戰，論文提出了THV-UCB（Thresholded Hypervolume Upper Confidence Bound）算法。該算法基於樂觀原則，利用每個臂邊際超體積貢獻的置信上界，貪心地選擇臂組成候選集。理論分析表明，THV-UCB具有兩種遺憾界：無間隙遺憾界Ñ(d√(nkT))，適用於所有實例，隨時間的平方根增長；以及間隙依賴的遺憾界Ñ(nk^(2.5)/Δ_min)，當臂之間的分離度足夠大時，遺憾隨時間呈對數增長。這些結果為使用小規模子集近似帕累託前沿提供了堅實的理論支撐。
該工作不僅具有理論意義，還有廣闊的應用前景。研究人員指出，THV-UCB算法可應用於推薦系統、自動化決策、資源分配等多個領域。論文共21頁、包含7張圖表，並附有代碼和數據的鏈接。這項研究為多目標場景下的候選集選擇問題開闢了新的方向，也為後續工作奠定了基礎。