論文の概要: Turning Mathematics Problems into Games: Reinforcement Learning and
Gr\"obner bases together solve Integer Feasibility Problems
- arxiv url: http://arxiv.org/abs/2208.12191v1
- Date: Thu, 25 Aug 2022 16:24:34 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-26 14:06:04.996743
- Title: Turning Mathematics Problems into Games: Reinforcement Learning and
Gr\"obner bases together solve Integer Feasibility Problems
- Title（参考訳）: 数学問題をゲームに変換する:強化学習と「オブナーベース」を合わせて整数実現可能性問題を解く
- Authors: Yue Wu, Jes\'us A. De Loera
- Abstract要約: 我々は、線形方程式と不等式の系が整数値の解を持つかどうかを判定する問題である整数実現可能性問題を考察する。
本稿では,エージェントが整数実現可能性問題と同等のゲームをすることができる,新しい代数的強化学習フレームワークについて述べる。
概念実証として、エージェントが2方向テーブルの最も単純なバージョンをうまくプレイできることを実験で実証する。
- 参考スコア（独自算出の注目度）: 4.746723775952672
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Can agents be trained to answer difficult mathematical questions by playing a
game? We consider the integer feasibility problem, a challenge of deciding
whether a system of linear equations and inequalities has a solution with
integer values. This is a famous NP-complete problem with applications in many
areas of Mathematics and Computer Science. Our paper describes a novel
algebraic reinforcement learning framework that allows an agent to play a game
equivalent to the integer feasibility problem. We explain how to transform the
integer feasibility problem into a game over a set of arrays with fixed margin
sums. The game starts with an initial state (an array), and by applying a legal
move that leaves the margins unchanged, we aim to eventually reach a winning
state with zeros in specific positions. To win the game the player must find a
path between the initial state and a final terminal winning state if one
exists. Finding such a winning state is equivalent to solving the integer
feasibility problem. The key algebraic ingredient is a Gr\"obner basis of the
toric ideal for the underlying axial transportation polyhedron. The Gr\"obner
basis can be seen as a set of connecting moves (actions) of the game. We then
propose a novel RL approach that trains an agent to predict moves in continuous
space to cope with the large size of action space. The continuous move is then
projected onto the set of legal moves so that the path always leads to valid
states. As a proof of concept we demonstrate in experiments that our agent can
play well the simplest version of our game for 2-way tables. Our work
highlights the potential to train agents to solve non-trivial mathematical
queries through contemporary machine learning methods used to train agents to
play games.
- Abstract（参考訳）: エージェントはゲームで難しい数学の質問に答えるように訓練できるのか?
線形方程式系と不等式系が整数値を持つ解を持つかどうかを判定する課題である整数実現可能性問題を考える。
これは数学と計算機科学の分野で応用された有名なNP完全問題である。
本稿では,整数実現可能性問題に相当するゲームをエージェントがプレイできる,代数的強化学習フレームワークについて述べる。
本稿では,固定マージン和を持つ配列の集合上での整数実現可能性問題をゲームに変換する方法について述べる。
ゲームは初期状態(配列)から始まり、マージンを変更せずに法的な動きを適用することで、最終的に特定の位置にゼロの勝利状態に到達することを目指している。
ゲームに勝つには、プレイヤーは初期状態と最終終了状態との間のパスを見つけなければならない。
そのような勝利状態を見つけることは、整数実現可能性問題の解法と等価である。
鍵となる代数的成分は、基礎となる軸輸送多面体に対するトーリックイデアルのgr\"obner基底である。
Gr\"オブナー基底はゲームの接続動作(アクション)の集合と見なすことができる。
次に, エージェントに連続空間における動きを予測させ, アクション空間の大規模化に対処する新しいRL手法を提案する。
連続移動は、その経路が常に有効な状態につながるように、一連の法的移動に投影される。
概念実証として,我々は実験で,エージェントが2方向テーブルの最も単純なバージョンをプレイできることを実証する。
本研究は,エージェントを訓練し,非自明な数学的問合せを解決するための,現代的機械学習手法の可能性を浮き彫りにする。
関連論文リスト
- Imperfect-Recall Games: Equilibrium Concepts and Their Complexity [74.01381499760288]
エージェントが以前保持していた情報を忘れたとき、不完全なリコールの下で最適な意思決定を行う。
不完全なリコールを伴う広範囲形式のゲームフレームワークにおいて、マルチプレイヤー設定における平衡を求める際の計算複雑性を解析する。
論文 参考訳（メタデータ） (2024-06-23T00:27:28Z) - Neural Population Learning beyond Symmetric Zero-sum Games [52.20454809055356]
我々はNuPL-JPSROという,スキルの伝達学習の恩恵を受けるニューラル集団学習アルゴリズムを導入し,ゲームの粗相関(CCE)に収束する。
本研究は, 均衡収束型集団学習を大規模かつ汎用的に実施可能であることを示す。
論文 参考訳（メタデータ） (2024-01-10T12:56:24Z) - Game Solving with Online Fine-Tuning [17.614045403579244]
本稿では,探索中のオンラインファインチューニングの適用について検討し,ゲーム問題解決のための最適設計計算を学習するための2つの方法を提案する。
実験の結果,オンラインファインチューニングを用いることで,ベースラインに比べて23.54%の時間しか利用できない7x7 Killall-Goの課題が解決できることがわかった。
論文 参考訳（メタデータ） (2023-11-13T09:09:52Z) - On Grid Graph Reachability and Puzzle Games [0.0]
Sokobanのようなパズルゲームの多くは、迷路にエージェントを移動させる。
ゲームの難しさは主に、プッシュ(到達可能な)ボックスのようなオブジェクトに対するアクションの実行に関連している。
本稿では,このような問題を解決するためのCPとSATのアプローチについて検討する。
論文 参考訳（メタデータ） (2023-10-02T17:41:35Z) - Hardness of Independent Learning and Sparse Equilibrium Computation in
Markov Games [70.19141208203227]
マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。
我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。
我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
論文 参考訳（メタデータ） (2023-03-22T03:28:12Z) - Global Nash Equilibrium in Non-convex Multi-player Game: Theory and
Algorithms [66.8634598612777]
ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。
また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
論文 参考訳（メタデータ） (2023-01-19T11:36:50Z) - An AlphaZero-Inspired Approach to Solving Search Problems [63.24965775030674]
探索問題を解くためにAlphaZeroで使用される手法と手法を適応する。
本稿では,簡単な解法と自己還元という観点から表現できる可能性について述べる。
また,探索問題に適応したモンテカルロ木探索法についても述べる。
論文 参考訳（メタデータ） (2022-07-02T23:39:45Z) - JiuZhang: A Chinese Pre-trained Language Model for Mathematical Problem
Understanding [74.12405417718054]
本稿では,中国初の数学的事前学習言語モデル(PLM)を提示することにより,機械の数学的知性向上を目指す。
他の標準のNLPタスクとは異なり、数学的テキストは問題文に数学的用語、記号、公式を含むため理解が難しい。
基礎課程と上級課程の両方からなる数学PLMの学習を改善するための新しいカリキュラム事前学習手法を設計する。
論文 参考訳（メタデータ） (2022-06-13T17:03:52Z) - Public Information Representation for Adversarial Team Games [31.29335755664997]
対戦チームゲームは、プレイ中にチームメンバーが利用可能な非対称情報の中にあります。
本アルゴリズムは,対戦相手を持つ逐次チームゲームから古典的な2プレイヤーゼロサムゲームに変換する。
この問題のNPハード性のため、結果のパブリックチームゲームは元のゲームよりも指数関数的に大きいかもしれない。
論文 参考訳（メタデータ） (2022-01-25T15:07:12Z) - Noncommutative Nullstellens\"atze and Perfect Games [0.0]
古典的代数幾何学と実代数幾何学の基礎は、ヌルサッツとポシティフサッツである。
本稿では,非ローカルゲームにおける通信事業者戦略について述べる。
結果は異なる文献にまたがるので、簡潔であるよりむしろ、我々のスタイルはかなり実証的だ。
論文 参考訳（メタデータ） (2021-11-29T20:05:33Z) - Algorithm for Computing Approximate Nash Equilibrium in Continuous Games
with Application to Continuous Blotto [1.7132914341329848]
連続ゲームにおけるナッシュ均衡戦略を近似する新しいアルゴリズムを提案する。
また,2プレイヤーゼロサムゲームに加えて,マルチプレイヤーゲームや不完全な情報を持つゲームにも適用できる。
論文 参考訳（メタデータ） (2020-06-12T19:53:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。