逆最適に近いプライマル・デュアルアルゴリズム：敵対的報酬を伴う線形混合CMDPの学習

概要: 我々は、完全な情報のフィードバックのもとで、遷移カーネルが未知であり、かつ報酬が敵対的な線形ミクスチャ制約付きマルコフ決定過程（CMDP）における有限ホライズンの安全強化学習を研究します。 我々は、穏やかな条件のもとで、損失（regret）と制約違反の上界が ()O(sqrt{d^2 H^3 K}) となることを達成する双対主問題（primal-dual）方策最適化アルゴリズムを提案します。ここで d は特徴量次元、H はホライズン、K はエピソード数です。 我々の知る限り、これは敵対的な報酬を伴う線形ミクスチャCMDPに対して、証明可能な意味で効率的な最初のアルゴリズムです。 特に、我々の損失の上界は準最適であり、対数因子まで既知のミニマックスの下限に一致します。 主なアイデアは、ドリフト（変位）に基づく解析を可能にする正則化された双対更新を導入することです。報酬関数がエピソード間で変化する場合には、強い双対性に基づく解析をそのまま直接適用できないため、この手順は本質的です。 さらに、我々は重み付きリッジ回帰に基づくパラメータ推定を制約付きの設定へ拡張し、準最適な損失上界を導出するために重要な、よりきつい信頼区間を構築できるようにします。