ヴィッツェンハウゼンの反例

下の図に示すWitsenhausen の反例は、分散型確率制御における一見単純なおもちゃの問題です。これは1968 年にHans Witsenhausenによって定式化されました。 ^[1]これは、集中型線形–二次–ガウス制御システムの重要な結果 (線形ダイナミクス、ガウス擾乱、二次コストを持つシステムでは、アフィン (線形) 制御則が最適であるという結果) を分散型システムに一般化できるという自然な推測に対する反例です。Witsenhausen は、2 つの決定が分散情報を持つ意思決定者によって行われる 2 段階の線形二次ガウス システムを構築し、このシステムではすべての線形法則よりも優れた非線形制御則が存在することを示しまし た。最適な制御則を見つける問題は未解決のままです。^[2]

反例の記述は単純です。2 つのコントローラが、ちょうど 2 つの時間ステップで状態をゼロに近づけることでシステムを制御しようとします。最初のコントローラは初期状態を観察します。最初のコントローラの入力にはコストがあり、2 番目のコントローラの入力後の状態にもコストがあります。2 番目のコントローラの入力は無料ですが、最初のコントローラの入力後の状態のノイズの多い観察に基づいています 。2 番目のコントローラは最初のコントローラと通信できないため、元の状態も最初のコントローラの入力も観察できません。したがって、システムのダイナミクスは次のようになります。 ${\displaystyle x_{0}.}$${\displaystyle u_{1}}$${\displaystyle x_{2}}$${\displaystyle u_{2}}$${\displaystyle y_{1}=x_{1}+z}$${\displaystyle x_{1}}$${\displaystyle x_{0}}$${\displaystyle u_{1}}$

${\displaystyle x_{1}=x_{0}+u_{1},}$

${\displaystyle x_{2}=x_{1}-u_{2},}$

2番目のコントローラの観測方程式

${\displaystyle y_{1}=x_{1}+z.}$

目的は期待コスト関数を最小化することであり、

${\displaystyle k^{2}E[u_{1}^{2}]+E[x_{2}^{2}],}$

ここで、期待値は、独立に分布する初期状態と観測ノイズのランダム性に基づいて算出されます。観測ノイズはガウス分布すると仮定されますが、初期状態値の分布は問題の特定のバージョンによって異なります。 ${\displaystyle x_{0}}$${\displaystyle z}$${\displaystyle z}$${\displaystyle x_{0}}$

問題は制御機能を見つけることだ

${\displaystyle u_{1}(x_{0})\quad {\text{and}}\quad u_{2}(y_{1})}$

少なくとも他の制御関数のペアと同じくらい良い目的関数の値を与えるもの。Witsenhausen は、最適関数とが線形ではあり得ないことを示しました。 ${\displaystyle u_{1}(x_{0})}$${\displaystyle u_{2}(y_{1})}$

Witsenhausen は以下の結果を得ました。

• 最適値が存在する（定理1）。
• 最初のコントローラの最適制御則は次のようになる（補題9）。${\displaystyle E(x_{1})=0}$
• 両方のコントローラが線形に制約されている場合（補題11）の正確な解が与えられます。
• がガウス分布を持ち、コントローラの少なくとも 1 つが線形になるように制約されている場合、両方のコントローラが線形であることが最適です (補題 13)。${\displaystyle x_{0}}$
• 2点対称分布を持つ場合の正確な非線形制御法則が与えられている（補題15）。${\displaystyle x_{0}}$
• がガウス分布を持つ場合、選好パラメータのいくつかの値に対して、制御法則の非最適非線形解が与えられ、期待コスト関数の値は制御法則の最良の線形ペアよりも低くなります (定理 2)。${\displaystyle x_{0}}$${\displaystyle k}$

反例は制御理論と情報理論の交差点に位置します。その難しさから、最適制御法則を見つける問題は理論計算機科学コミュニティからも注目されています。この問題の重要性は、メキシコのカンクンで開催された第47回IEEE意思決定および制御会議(CDC)2008で検討され、^[2]セッション全体が反例が最初に定式化されてから40年後の反例の理解に充てられました。

この問題は分散制御において概念的に重要な問題であり、コストを最小化するために制御器が暗黙的に相互に通信することが重要であることを示している^[3]。これは、分散制御における制御動作が制御と通信という2つの役割を持つ可能性があることを示唆している。

この問題の難しさは、2番目のコントローラの情報が最初のコントローラの決定に依存するという事実に起因します。^[4] Tamer Basar ^[5]が検討したバリエーションは、難しさはパフォーマンスインデックスの構造と異なる決定変数の結合によるものであることも示しています。また、コントローラを接続する外部チャネルに沿った伝送遅延が問題内の伝播遅延よりも小さい場合、Witsenhausen の反例の精神の問題が簡単になることも示されています。ただし、この結果にはチャネルが完全かつ瞬時であることが必要であるため、^[6]適用範囲が限られています。実際の状況では、チャネルは常に不完全であるため、外部チャネルが存在する場合の分散制御問題が簡単であると想定することはできません。

問題を離散化する試みの失敗の正当化は、コンピュータサイエンスの文献から生まれました。クリストス・パパディミトリウとジョン・ツィツィクリスは、反例の離散バージョンが NP完全であることを示しました。^[7]

反例を解くために、多くの数値的試みがなされてきた。問題のパラメータの特定の選択に焦点を当てて、研究者らは離散化とニューラルネットワークの使用による戦略を得てきた。^{[8]さらなる研究（特に、} Yu-Chi Hoの研究、^[9]とLi、Marden、Shammaの研究^[10]）では、同じパラメータ選択に対してわずかに改善されたコストが得られている。前述のものを含むさまざまなパラメータに対する最もよく知られた数値結果は、2017年にS.-H. TsengとA. Tangによって提案された局所探索アルゴリズムによって得られている。 ^[11]最初の証明可能な近似最適戦略は2010年に登場し（Grover、Park、Sahai）^[12]、情報理論を使用して反例における通信を理解している。反例の最適解はまだ未解決の問題である。 ${\displaystyle (k=0.2,\;\sigma _{0}=5)}$