合理的強化学習はボトルネックに達しました。進化的アルゴリズムがその後継者となるでしょうか?

人工知能とゲーム理論の交差点から強化学習が生まれましたが、ゲーム理論に基づく問題解決は通常、合理性と完全情報という仮定に依存しています。マルチエージェントゲーム環境では、この条件を満たすことはほぼ不可能です。著者らは、この点に関して従来の強化学習の限界を分析し、代替手段としての進化型強化学習の可能性について議論しています。

[[233562]]

人工知能 (AI) の研究分野には、答えられない質問と、適切な質問に割り当てることができない答えが溢れています。過去に、AI は「間違った」実践を続けた代償を払い、いわゆる「AI の冬」と呼ばれる停滞期を経験しました。しかし、人工知能の暦はちょうど春に変わり、関連する応用分野は活況を呈しています。

人工知能の中で長い間無視されてきた分野の一つが強化学習です。強化学習は最近、AlphaGo や Atari ゲームで素晴らしい結果を示しました。しかし、正直に言うと、これらは強化学習の勝利ではありません。これらの例では、強化学習よりもディープ ニューラル ネットワークの方がより深い役割を果たしており、強化学習は数十年前と同じ深さで現在も研究が続けられています。

強化学習を現実の問題に適用すると、状況はさらに悪化します。ロボットにロープの上でバランスを取るよう訓練するのが難しそうなら、サッカーの試合に勝つためのロボットのチームや、動くターゲットを監視するためのドローンの艦隊を訓練してみましょう。

枝（強化学習）や木全体（人工知能）を失う前に、これらのアプリケーションに対する理解を深める必要があります。ゲーム理論は、ゲームにおいて共通の目標を持つプレイヤーのチームの対応戦略を研究するために使用される最も一般的な方法です。このような環境で機械学習アルゴリズムをガイドするためのツールを提供できます。

しかし、この一般的なアプローチは常識に合致していないことに注意することが重要です。その理由を見てみましょう。

まず、いくつかの用語とこれらの分野の基礎を理解して、謎の探求を始めましょう。

ゲーム理論

1. 一般的な用語

• ゲーム: 人々が通常理解しているように、ゲームとは、参加者が行動を起こし、ゲームの結果がその行動によって決まる環境を指します。
• プレイヤー: ゲーム内で決定を下す人々。
• 戦略: ゲーム中に発生する可能性のある一連の状況を考慮して、プレイヤーが実行できる一連のアクションの完全な流れ。
• ペイオフ: ゲームの特定の結果からプレイヤーが受け取る利益。
• 均衡: ゲームにおいてプレイヤーが決定を下し、結果を達成した状態。
• ナッシュ均衡: 他のプレイヤーの戦略が変更されない場合、どのプレイヤーも自分の戦略を変更しても利益を得ることができない均衡状態。
• 優勢均衡: 対戦相手がどのように戦略を選択するかに関係なく、参加者の戦略が対戦相手の戦略よりも優れている均衡状態。

2. 囚人のジレンマ

これはおそらく、文献に出てくるゲームに関する最も有名な例でしょう。その利益マトリックスは下の図に示されています。 「リターン マトリックス」(支払いマトリックスとも呼ばれる) の概要を説明するには、1,000 語かかるかもしれません。経験豊富な人にとって、ペイオフマトリックスは、ゲームを説明するために必要なすべての情報を提供するのに十分です。さて、囚人のジレンマとは何かを少し理解してみましょう。

囚人のジレンマの利得マトリックス

警察は容疑者Aと容疑者Bの2人を逮捕した。容疑者2人は悪名高いにも関わらず、証拠不足のため捜査中の犯罪で投獄されることはない。しかし、より軽い罪で拘留される可能性もある。

彼らがどれくらい監禁されるかは、尋問室で彼らが何を言うかによって決まり、運任せのゲームとなる。各容疑者（参加者）には、黙秘するか、他の容疑者を密告するかを選択する機会が与えられます。報酬マトリックスは、ゲームの結果に応じて各プレイヤーが何年間投獄されるかを示します。たとえば、容疑者 A が黙秘し、容疑者 B が密告した場合、容疑者 A は懲役 3 年（報酬は -3）となり、容疑者 B は懲役なし（報酬は 0）となります。

この報酬マトリックスを注意深く研究すると、参加者にとって合理的な行動は他の人を裏切ることであり、ゲーム理論の観点からは、他人を裏切ることが優勢な戦略であることがわかります。しかし、全員が裏切ることを選択した場合、ゲームはナッシュ均衡に向かって進み、各プレイヤーは -2 の報酬を受け取ることになります。

奇妙だと思いませんか? ええ、少なくともそうあるべきです。両方の参加者が沈黙することに同意した場合、両者とも「-1」というより高い報酬を受け取ります。囚人のジレンマは、合理的な行動が協力よりも悪い結果につながることがあることを示すゲームの例です。

3. 歴史的評価

ゲーム理論は経済学から生まれましたが、現在では学際的な研究分野に発展しています。ゲーム理論の父、ジョン・フォン・ノイマン（フォン・ノイマンがこの分野で非常に優れた経歴を持っていたことはおわかりでしょう）は、「ゲーム」の一般的な概念を厳密に正式に定義した最初の人物でした。分析を容易にするために、彼はゲームの研究を 2 人のプレイヤーが関与する状況に限定しました。

その後、彼はオスカー・モルゲンシュテルンと共著で期待効用理論の基礎を築き、最終的にはゲーム理論の講座につながった本を執筆しました。ジョン・ナッシュがゲームの結果を説明するのに役立つナッシュ均衡の概念を導入したのはその頃でした。

2. 強化学習

ゲーム理論の応用範囲がゲームから生物学、哲学、そしてその後すぐに人工知能まで多岐にわたることに人々が気づくまで、そう時間はかかりませんでした。今日のゲーム理論は、強化学習によって複数のエージェントがトレーニングされる状況、つまりマルチエージェント強化学習と呼ばれる分野と密接に関係しています。このコンテキストでのアプリケーションの例としては、ロボット (参加者) のチームがあり、各ロボットがチームに利益をもたらすために何をすべきかを学習する必要があるとします。

1. 一般的な用語

• エージェント: 参加者に相当します。
• 報酬：収入と同等
• 状態: エージェントの状況を説明するために必要なすべての情報。
• アクション: ゲーム内のアクションに相当します。
• 戦略: ゲーム理論の戦略と同様に、エージェントが特定の状態で実行するアクションを定義します。
• 環境: 学習プロセス中にエージェントが対話するすべてのもの。

2. 応用

次のシナリオを想像してください。ドローンの一団が森林に放たれ、できるだけ早く火災を予測して場所を特定し、消防士がタイムリーに対応できるようにします。ドローンは自律型で、森林を探索し、火災の原因となる状況を学習し、互いに協力して、ほとんど電力を消費せず、最小限の通信で広大な森林地帯をカバーできるようにする必要があります。

このアプリケーションは環境モニタリングの分野に属し、人工知能技術の予測機能を使用して人間の介入行動を導くことができます。テクノロジーがますます複雑化し、物理的な世界が前例のない課題に直面している世界では、キプリングの有名な格言「神はどこにでもいられないので、母親を創造した」は、「人間はどこにでもいられないので、ドローンを創造した」と書き換えることができるようになりました。

分散型アーキテクチャは、もう 1 つの興味深いアプリケーション領域です。 IoTやブロックチェーンなどのテクノロジーは広大なネットワークを構築します。情報と処理はさまざまな物理的エンティティに分散されており、プライバシー、効率性、民主主義を実現するアーキテクチャとして認識されています。

センサーを使用して国の家庭のエネルギー消費を最小限に抑えたい場合でも、銀行システムを置き換えたい場合でも、分散化は新しく魅力的なソリューションです。

しかし、これらのネットワークをインテリジェントにすることは困難です。私たちが誇りに思っているアルゴリズムのほとんどにはトレーニングデータが不足しており、さらなる計算能力を必要としているからです。強化学習アルゴリズムは効率的なデータ処理に使用でき、ネットワークが環境の変化に適応できるようにします。この文脈では、全体的な効率を向上させるために個々のアルゴリズムがどのように連携できるかを研究することは興味深いことです。

ディープラーニングと集合学習のどちらを使うべきでしょうか? AI 研究はますます深いネットワークに基づいて成果を上げていますが、難しい問題に対する答えは、ディープラーニングに基づく個人ではなく集合的な知識から得られる可能性があります。大きな森が欠けているのでしょうか?

3. 単なるゲーム以上のもの

AI の問題を囚人のジレンマのような単純なゲームに変換したくなるものです。これは、計算コストが安く、直感的なテスト プラットフォームを提供するため、新しいテクノロジをテストするときによく使用されるアプローチです。ただし、ノイズ、レイテンシ、メモリ制限などの実際的な特性がアルゴリズムに与える影響を無視しないことが重要です。

おそらく、AI 研究で最も誤解を招く仮定は、反復される静的ゲームによるインタラクティブな表現という仮定です。たとえば、エージェントが学習しておらず、変更されていないと仮定すると、アルゴリズムは、決定や計画を立てるたびに囚人のジレンマ ゲームを適用できます。しかし、学習はエージェントのパフォーマンスにどのような影響を与えるのでしょうか? 他のエージェントとのやり取りはエージェントの戦略に影響を与えませんか?

この分野の研究は協力の進化に焦点を当てており、ロバート・アクセルロッド氏は囚人のジレンマの反復バージョンから生まれる最適な戦略を研究してきました。アクセルロッド氏のトーナメントは、タイミングと相互作用に適応する戦略（たとえそれが報復のように単純に聞こえるとしても）が非常に効果的であることを示しています。最近の進歩（https://arxiv.org/abs/1803.00162）では、AIコミュニティは「順次囚人のジレンマ」の下での学習を研究してきましたが、この分野の研究はまだ初期段階にあります。

マルチエージェント学習とシングルエージェント学習の違いは、複雑さが大幅に増加していることです。単一のディープ ニューラル ネットワークをトレーニングするだけでも大変ですが、エージェントの一部として新しいネットワークを追加すると、問題の難しさは飛躍的に増大します。

あまり明白ではないがより重要な問題は、そのような質問には理論的な性質が欠けているということです。シングルエージェント強化学習は、リチャード・ベルマンとクリストファー・ワトキンスが学習に必要なアルゴリズムを提案し、証明して以来、よく理解されている研究分野です。しかし、マルチエージェント学習の場合、この証明は成り立ちません。

発生する混乱を招く問題のいくつかを説明すると、エージェントは学習アルゴリズムを実行して、環境に最適な対応方法を学習します。ここで示す例では、環境は学習アルゴリズムを実行する他のエージェントで構成されています。したがって、アルゴリズムは行動を起こす前にその行動の影響を考慮する必要があります。

4. 早期の焦点

ゲーム理論（経済学）の始まりから生じてきた懸念。まず、古典的なゲーム理論に基づいてシステムが立てたいくつかの仮定を見てみましょう。

• 合理性: 一般にゲーム理論では、ナッシュ均衡を達成するために完全な合理性が想定されます。これは、エージェントが常に自身の利益のために行動することを意味します。
• 完全情報: 各エージェントは、ルール、他のプレイヤーが知っていること、他のプレイヤーの戦略など、ゲームに関するすべてを知っています。
• 共通知識: すべてのエージェントが P を知っていて、すべてのエージェントが「すべてのエージェントが P を知っている」ことを知っていて、すべてのエージェントが「すべてのエージェントが「すべてのエージェントが P を知っている」ことを知っている」ことを知っている場合...このサイクルは無限に続き、これが存在する共通知識です。 Blue-Eyed Islander Puzzle (http://mesosyn.com/mental1-2.html) など、共通の知識が問題に与える影響を示す興味深いパズルがいくつかあります。

ケン・アローは 1986 年に古典的なゲーム理論に対する懸念を表明しました。

この記事 (http://dieoff.org/_Economics/RationalityOfSelfAndOthersArrow.pdf) では、経済理論で使用される合理性の仮定の意味のいくつかを検討したいと思います。特に強調したいのは、合理性はしばしば個人的な形で表現されるが、それは単に個人の性質ではないということである。それどころか、理性はそれ自身の力だけでなく、それが置かれている社会的文脈からその意味も集めます。非常に理想的な条件下では、これが最も合理的な見方です。これらの条件が満たされない場合、合理的な仮定は維持できなくなり、自己矛盾が生じる可能性さえあります。

アローの古典的ゲーム理論に関する仮定が少々厳しすぎると思うなら、あなたは前回の購入でどれほど合理的だったと思いますか？あるいは、今日の食事にどれほどの考えと努力を注ぎましたか？

しかし、アローは合理性の仮定そのものにはあまり関心がありません。彼は合理性についての仮定の意味を懸念していた。合理的なエージェントがこのように行動するには、意思決定に必要なすべての情報をエージェントに提供する必要があります。これには全知全能の参加者が必要であり、2 つの欠点があります。まず、参加者の情報の保存と処理に非現実的な要求が課せられます。第二に、参加者全員のゲームを中央管理者のルールに置き換えることができるため（それでは面白くない）、ゲーム理論はもはや「複数当事者の敵対的ゲームの理論」ではなくなります。

情報の価値は、この見方におけるもう一つの興味深い点です。すべての情報を入手することは現実的ではないということについてはすでに議論しました。しかし、参加者全員が限られた知識しか持っていないと仮定したらどうなるでしょうか? それは役に立つでしょうか?

この分野で働いたことがある人なら誰にでも尋ねることができますが、不確実性の下での最適化は難しいと言うだけで十分でしょう。はい、幸運なことに、古き良きナッシュ均衡が存在します。しかし問題は、このプロセスが無限ループになっていることです。ゲーム理論では、それらを評価するための基礎は提供されません。したがって、ナッシュ均衡に達したとしても、大した問題ではありません。

5. 強化学習の焦点

ここで、AI アプリケーションは従来のゲーム理論に含まれる例よりもはるかに複雑であると考えるべきです。ロボット工学アプリケーションでナッシュ均衡法を使用する際の障害をいくつか考えてみましょう。ロボカップのサッカーロボットチームのキャプテンであると想像してください。あなたの選手や対戦相手はどれくらい速く、強く、賢いでしょうか? 相手チームはどんな戦略を採用するでしょうか? 選手にはどのように報いるべきですか? ゴールだけが祝うべき理由でしょうか? それとも、良いパスを褒めることでチーム全体のパフォーマンスも向上するでしょうか? 明らかに、サッカーのルールを知っているだけでは試合に勝てません。

ゲーム理論が何十年も議論されてきたのなら、それが現実世界の課題に対する非現実的な仮定に基づいているのなら、そしてそれが提案する解決策が複雑で理解しにくいのなら、なぜ私たちはそれを研究し続けるのでしょうか? どうやら、これが集団推論に関して私たちが得た唯一の研究のようです。グループが目標を達成するためにどのように相互作用し、協力するかを本当に理解すれば、心理学や政治におけるいくつかの問題ははるかに明確になるでしょう。

マルチエージェント強化学習の分野の研究者は、アルゴリズムの理論的特性について徹底的に議論するか（多くの場合、良い結果を示します）、ナッシュ均衡の存在を研究する従来のアプローチに従います。後者のアプローチは、この分野の若い研究者にとっては、厳格で非現実的な仮定の下で理論上存在する、価値に疑問のある無限再帰的なソリューションが実際には決して利用されないという証拠のように見えるようです。

6. 進化ゲーム理論

進化ゲーム理論の創造は最近の出来事ではありませんが、人工知能の分野でのその広範な応用が認識されるまでには長い時間がかかりました。これは生物学に端を発し、古典的なゲーム理論の代替として 1973 年にジョン M. スミスとジョージ R. プライスによって提案されました。この変化は非常に大きく、私たちはまったく新しいアプローチを議論していると言えます。

推論の主体はもはや参加者自身ではなく、参加者のグループです。したがって、確率的戦略は、古典的なゲーム理論のようにプレイヤーが行動を選択する確率ではなく、決定を下すプレイヤーの割合として定義されます。戦略が行動パターンへと進化するにつれて、合理的で全知全能のエージェントはもはや必要ではなくなります。進化の過程はダーウィンの理論に似ています。参加者は適者生存とランダムな突然変異の原理に従って繁殖します。このプロセスは、「レプリケータダイナミクス」として知られる一連の微分方程式によって簡潔に説明できます。

下の図では、このシステムの 3 つの重要なコンポーネントを確認できます。群れは、戦略の組み合わせによって特徴付けられるエージェントのチームを表します。ゲームのルールによってグループの利益が決まり、これは進化アルゴリズムの適応度値とも考えられます。最後に、レプリケータルールは、適応度値と進化プロセスの数学的特性に基づいて集団がどのように進化するかを説明します。

画像はWikipediaより: (https://creativecommons.org/licenses/by-sa/3.0)

ナッシュ均衡の概念とその目標は、「進化的に安定した戦略」に置き換えられました。ある戦略が、別の戦略に従うグループの侵入に抵抗できる場合（侵入するグループが小さい場合）、その戦略は「進化的に安定した戦略」の特性を満たします。したがって、チームの行動は、「リアプノフ安定性」などのよく理解されている動的システムの安定性の観点から研究することができます。

平衡状態を達成するには、不均衡なプロセスが必要です。不均衡な状態で合理的に行動するというのはどういう意味でしょうか? 個人は均衡の過程で均衡状態について推論するでしょうか? もしそうなら、不均衡は何らかの形で高次の均衡プロセスとして見ることができるでしょうか?

上記のことから、Arrow はゲームの動的な特徴を見つけるのに苦労しているように見えます。では、進化ゲーム理論は彼に答えを与えることができるのでしょうか?

最近では、「Q学習」などのよく知られた強化学習アルゴリズムもこの新しい手法を参考にして研究され、重要な研究成果を上げています。この新しいツールがどのように使用されるかは、最終的にはアプリケーション シナリオによって異なります。

フィードフォワードアプローチを使用して、学習アルゴリズムの動的モデルを導き出すことができます。あるいは逆に、望ましい動的特性から始めて、それを反映する学習アルゴリズムを設計します。

レプリケータダイナミクスを記述的に使用して、収束プロセスを視覚化できます。または、アルゴリズムを定期的に調整して、最適なソリューションに収束させます。後者は、盲目的なパラメータ調整の必要性を排除することで、現在直面している困難なタスクのためにディープネットワークをトレーニングする際に発生する計算の複雑さを大幅に削減できる可能性があります。

VII. 結論

ゲーム理論と人工知能がいつ、なぜ絡み合うようになったのかをたどることは難しくありません。しかし、古典的なゲーム理論のアプローチに従う場合、人工知能、特にマルチエージェント強化学習が直面する限界を無視することはできません。

進化ゲーム理論は有望に思えますし、実用的な利点を持つ理論的ツールを提供しますが、実際に試してみるまでその秘密はわかりません。戦略の進化は自然に起こるものではなく、研究コミュニティによる戦略を改善するための意識的な努力であると思われます。しかし、それは進化の本質ではないでしょうか?

あなたを前進させてきた精神的な惰性から抜け出すには、多大な努力が必要です。しかし、強化学習が人工知能において広く成功しているにもかかわらず、改善の必要性は依然として切実に残っています。

オリジナルリンク:

https://medium.freecodecamp.org/game-theory-and-ai-where-it-all-started-and-where-it-should-all-stop-82f7bd53a3b4

[この記事は51CTOコラム「Machine Heart」、WeChatパブリックアカウント「Machine Heart（id: Almosthuman2014）」からのオリジナル記事です]

この著者の他の記事を読むにはここをクリックしてください