Generalizing Beyond Suboptimality: Offline Reinforcement Learning Learns Effective Scheduling through Random Solutions
本論文は、静的で不適切なデータセットから効果的なジョブショップおよびフレキシブル・ジョブショップのスケジューリング方策を学習するオフライン強化学習アルゴリズムであるCDQACを紹介し、高い性能とサンプル効率を実現するためには、軌跡の質よりも広範な状態・行動の被覆率がより重要であることを実証している。
原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。 免責事項の全文を読む
あなたは、多くの機械と山のような仕事が積み上がった、非常に忙しい工場のマネージャーだと想像してください。あなたの目標は、できるだけ早くすべてを終わらせることです。これが**ジョブショップ・スケジューリング問題（Job Shop Scheduling Problem）**です。
従来、これを効率的に行う方法を学ぶには、「ロボットの弟子」（AI）を雇い、さまざまなスケジュールを試したり、失敗したり、その結果から学んだりする練習をさせる必要がありました。これは**オンライン強化学習（Online Reinforcement Learning）**と呼ばれます。しかし、問題があります。弟子が上手になるためには、膨大な回数の練習が必要であり、それには多大な時間とコンピュータの計算能力が必要になるのです。
あるいは、人間の専門家を雇って、彼らが作成した最高のスケジュールを書き留めてもらい、ロボットにそのメモを単に模倣させることもできます。これは**模倣学習（Imitation Learning）**です。しかし、ロボットはメモを書いた人間を超えることはできません。そのレベルに縛られてしまうのです。
大きなアイデア： 「ランダムな」失敗から学ぶ
この論文は、CDQAC（Conservative Discrete Quantile Actor-Critic）と呼ばれる新しい手法を紹介しています。これは**オフライン強化学習（Offline Reinforcement Learning）**を用いたものです。
このように考えてみてください。ロボットに実際の工場で練習させるのではなく（それは遅くてコストがかかります）、あるいは専門家にコピーさせるのではなく（それはポテンシャルを制限します）、研究者たちはロボットに、単純なルールや遺伝的アルゴリズム、あるいは純粋なランダムな偶然によって生成された、古くて、めちゃくちゃで、時にはひどい内容のスケジュールが詰まった膨大なライブラリを与えました。
驚くべき発見がありました。ロボットは「専門家」のデータよりも、ランダムでめちゃくちゃなデータからより多くを学んだのです。
なぜランダムなデータが勝ったのか？（パズルの比喩）
通常、AIのトレーニングでは高品質なデータを求めます。車の運転を教えるなら、プロのドライバーのビデオが欲しいはずであり、壁に衝突している人のビデオは欲しくないはずです。
しかし、著者らは、スケジューリングはこれとは異なると主張しています。彼らは、なぜランダムなデータがこれほど上手くいったのかを説明するために、主に2つの比喩を用いています。
「高密度な報酬（Dense Reward）」信号:
多くのAIゲーム（ビデオゲームなど）では、勝ち負けが決まる最後の一瞬にしか報酬（ポイント）が得られません。その間、自分がうまくやれているのかどうかは分かりません。
スケジューリングでは、一手打つごとに即座にフィードバックが得られます。ある仕事を機械に割り当てると、それが全体の時間をどれだけ増加させたかが即座に分かります。これは、ダンスのルーチンの最後に一度だけスコアをもらうのではなく、ステップごとにスコアをもらっているようなものです。つまり、たとえ「悪い」ランダムな動きであっても、AIに対してそれがどれほど悪かったかを正確に伝えることができるため、あらゆる行動の価値を学ぶことができるのです。「パズルのピース」（カバー範囲 vs 品質）:
巨大なジグソーパズルを解こうとしている場面を想像してください。- 専門家のデータは、絵の左上部分からしか出てこないパズルのピースの箱のようなものです。それらは完璧で高品質ですが、画像のほんの一部しか示していません。残りの部分が欠けているため、パズル全体を解くことはできません。
- ランダムなデータは、パズルのあらゆる場所から集められたピースの袋のようなものです。上下が逆さまだったり、空の部分だったり、草の部分だったり、バラバラです。個々で見れば、それらは乱雑で「間違って」見えるかもしれませんが、集まればパズルの全体像をカバーしています。
この論文のAIは、これらのピースを「縫い合わせる」ことができるほど賢いため、ピースの多様性（カバー範囲）が、単一の場所にある完璧なピースを持っていることよりも重要になります。ランダムなデータは問題のより広い「領域」をカバーしていたため、AIは専門家のデータよりも優れた解決策を見つけ出すことができたのです。
AIはどうやって学ぶのか（「縫い合わせる」比喩）
AIは単に目にしたスケジュールをコピーするのではありません。それは、古い、破れた服の山を見ている熟練の仕立て屋のように振る舞います。
- 赤いシャツの袖が完璧にフィットするのを見つけます。
- 青いシャツのパンツが完璧にフィットするのを見つけます。
- 緑のシャツの襟が完璧にフィットするのを見つけます。
たとえ、その山の中にあるどのシャツも完璧ではなかったとしても、AIは最高のパーツを**縫い合わせる（スティッチング）**ことで、かつて存在しなかった新しい完璧な衣装を作り上げます。AIは、過去の何千もの試行（失敗したものも含めて）を分析することで、特定の「仕事」に対してどの「機械」を選ぶのがベストかを学ぶのです。
結果：速く、安く、そしてより良く
この論文は、この新しい手法（CDQAC）が以下のことを示しています：
- オンライン学習を凌駕する： 何百万回もの練習を必要とした「ロボットの弟子」にさえ、CDQACは勝利しました。しかも、CDQACは一度も実際の工場を見たことがありません。
- 専門家を超える： 学習に使った「専門家」のデータよりも優れたスケジュールを作成します。
- 極めて効率的である： 効果的に学習するために通常必要とされるデータのわずか 1%から5% しか必要としませんでした。これは、1万マイル走行する代わりに、数ページの取扱説明書を読むだけで運転を習得するようなものです。
- 汎用性が高い： 小さな問題で学習し、見たこともないような、より大きく複雑な問題を成功裏に解決しました。
まとめ
この論文は、工場のスケジューリングにおいて、完璧な教師や何百万時間の練習は必要ない、と主張しています。必要なのは、過去の試行（たとえランダムなものであっても）の、大きくてめちゃくちゃなデータの塊です。これらのめちゃくちゃな試行におけるあらゆるステップの「価値」を注意深く分析する特別なアルゴリズムを使用することで、AIは、元の「教師」が作り出せるものよりも速く、より優れた完璧なスケジュールを縫い合わせることができるのです。
自分の分野の論文に埋もれていませんか？
研究キーワードに一致する最新の論文のダイジェストを毎日受け取りましょう——技術要約付き、あなたの言語で。