Bandit-Based Rate Adaptation for a Single-Server Queue

技術要約：単一サーバ待ち行列におけるバンディットに基づくレート適応

問題定式化
本論文は、部分的なフィードバックの下で動作する離散時間スロットの単一サーバ待ち行列システムにおけるレート適応の問題を扱う。各スロット $t$ において、送信機は連続区間 $[0, 1]$ から送信レート $V(t)$ を選択する。チャネル容量 $C(t)$ と到着プロセス $A(t)$ は、既知ではあるが未知の分布から独立同一分布（i.i.d.）に従って生成される。送信が成功するのは、$V(t) \leq C(t)$ である場合に限られる。それ以外の場合は失敗となる。送信機は、成功または失敗を示すバイナリフィードバック（ACK/NACK）のみを受け取る。目的は、到着率 $\lambda$ がシステムの容量領域内に厳密に含まれている場合に、時間平均期待待ち行列サイズを一様に有界にするレート選択アルゴリズムを設計することである。「スラック（余裕）」は、到着率と最大達成可能サービスレートとの間の差として $\varepsilon > 0$ で表される。

著者らは、以下の2つのシナリオを区別している：

1. $\varepsilon$ が既知の場合： 送信機は、到着率と容量領域の間の下限に関する事前知識を持っている。
2. $\varepsilon$ が未知の場合： 送信機は $\varepsilon$ を知らず、このパラメータなしにシステムダイナミクスを学習しなければならない。

手法
本論文は、待ち行列理論と連続腕バンディット（continuum-armed bandit）学習を統合している。標準的な待ち行列バンディットが有限のアクション空間を扱うのに対し、本研究は、非可算無限のレート空間を扱う。

• $\varepsilon$ が既知の場合： 著者らは、連続的なレート空間 $[0, 1]$ をサイズ $d = \lceil \gamma/\varepsilon \rceil$ の有限なグリッドにマッピングする離散化戦略を提案する。これにより、問題を有限腕バンディット問題へと変換する。著者らは、離散化された集合に対して古典的な上限信頼限界（UCB1）アルゴリズムを適用する。彼らは、学習段階（最適な離散レートを特定する）と、レートが十分に最適に近くなった後に待ち行列サイズを抑えるための制御段階（リアプノフ・ドリフト解析を用いる）という、厳密な2段階の解析を行う。

• $\varepsilon$ が未知の場合： 著者らは、レート空間の離散化を反復的に洗練させるフェーズド・アルゴリズムを提案する。アルゴリズムはフェーズ $\ell = 1, 2, \dots$ で動作する。各フェーズ $\ell$ において、レート空間は $d_\ell$ 個のレベルに離散化され、$d_\ell$ はフェーズの長さ $T_\ell$ の関数として増加する。各フェーズ内では、現在の離散化に対してUCB1の適応が実行される。シーケンス $\{T_\ell\}$ および $\{d_\ell\}$ は、探索の負担と、安定性を確保するために必要な微細な離散化とのバランスを取るように、慎重に選択される（具体的には、$T_\ell = 2^{\ell+2}$ および $d_\ell \propto T_\ell^{1/2-\delta}$）。

主な貢献

1. 新規な定式化： 本論文は、待ち行列の安定性と連続腕バンディットの統合を初めて導入した。これは、未知の到着およびサービス分布の知識なしには、固定された有限の腕の集合では安定性を保証できないという課題に対処している。
2. 未知の $\varepsilon$ に対するアルゴリズム設計： $\varepsilon$ に関する事前知識なしに、レートの離散化を適応的に洗練させるフェーズドUCBアルゴリズムが設計されている。
3. コンバース結果（逆定理）： 著者らは、どのようなレート選択アルゴリズム（$\varepsilon$ が既知か未知かを問わず）に対しても、最悪の場合の時間平均期待待ち行列サイズが $\Omega(1/\varepsilon^2)$ となる環境が存在することを示す下限（コンバース）を確立している。
4. 既知の $\varepsilon$ に対する最適性： 本論文は、既知の $\varepsilon$ の場合、提案された固定離散化上のUCBベースのアルゴリズムが、時間平均期待待ち行列サイズとして $O(\log(1/\varepsilon)/\varepsilon^2)$ を達成することを証明している。これは、対数因子を除いてコンバースの下限と一致しており、この設定における最適性を確立している。

結果

• 未知の $\varepsilon$： 提案されたフェーズドアルゴリズムは、時間ホライゾンにわたって一様に、オーダー $O(\log^{3.5}(1/\varepsilon)/\varepsilon^3)$ の時間平均期待待ち行列サイズを達成する。
• 既知の $\varepsilon$： アルゴリズムは、オーダー $O(\log(1/\varepsilon)/\varepsilon^2)$ の時間平均期待待ち行列サイズを達成する。
• 下限： コンバース結果は、アルゴリズムの知識に関わらず、最悪の場合、待ち行列サイズは $\Omega(1/\varepsilon^2)$ より良くなることはないことを示している。

意義と主張
本論文は、IEEE 802.11システムにおけるレート選択のように、アクション空間が有限腕の定式化には大きすぎる実用的なアプリケーションを背景として、待ち行列の安定性と連続腕バンディットを初めて統合したものであると主張している。

著者らは、未知の $\varepsilon$ 設定における上界（$O(\varepsilon^{-3})$）と下限（$O(\varepsilon^{-2})$）の間のギャップを強調している。彼らは、$\varepsilon$ が未知の場合でも $O(\log^\alpha(1/\varepsilon)/\varepsilon^2)$ を達成するアルゴリズムが可能であると推測しており、これがギャップを埋めることになる。論文内では、このようなアルゴリズムの設計は今後の課題として明示的に残されている。また、連続腕待ち行列フレームワークをマルチキューまたはネットワーク設定へ拡張することも、別の将来的な方向として示唆している。

本研究は、部分的なフィードバックの下でのレート適応に関する理論的基礎を提供しており、$\varepsilon$ の知識がある場合はほぼ最適な性能が得られる一方で、この知識なしに学習を行う場合には、待ち行列の境界に多項式のペナルティが生じることを示している。