論文の概要: Alternating Good-for-MDP Automata

• arxiv url: http://arxiv.org/abs/2205.03243v1
• Date: Fri, 6 May 2022 14:01:47 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-09 13:51:13.999944
• Title: Alternating Good-for-MDP Automata
• Title（参考訳）: 交流型mdpオートマトン
• Authors: Ernst Moritz Hahn and Mateo Perez and Sven Schewe and Fabio Somenzi and Ashutosh Trivedi and Dominik Wojtczak
• Abstract要約: 良質MDP(GFM)B"uchiautoaを用いて、悪質MDP(GFM)オートマトンを修復できることを示す。 非決定論的ラビンやB'uchiオートマトンへの翻訳は、ターゲットオートマトンをMDPの良さを必要とせずとも、指数的なコストがかかる。 意外な答えは、MDPプロパティを交代オートマトンに拡張する際には、はるかに少なめに支払わなければならないということです。
• 参考スコア（独自算出の注目度）: 4.429642479975602
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: When omega-regular objectives were first proposed in model-free reinforcement learning (RL) for controlling MDPs, deterministic Rabin automata were used in an attempt to provide a direct translation from their transitions to scalar values. While these translations failed, it has turned out that it is possible to repair them by using good-for-MDPs (GFM) B\"uchi automata instead. These are nondeterministic B\"uchi automata with a restricted type of nondeterminism, albeit not as restricted as in good-for-games automata. Indeed, deterministic Rabin automata have a pretty straightforward translation to such GFM automata, which is bi-linear in the number of states and pairs. Interestingly, the same cannot be said for deterministic Streett automata: a translation to nondeterministic Rabin or B\"uchi automata comes at an exponential cost, even without requiring the target automaton to be good-for-MDPs. Do we have to pay more than that to obtain a good-for-MDP automaton? The surprising answer is that we have to pay significantly less when we instead expand the good-for-MDP property to alternating automata: like the nondeterministic GFM automata obtained from deterministic Rabin automata, the alternating good-for-MDP automata we produce from deterministic Streett automata are bi-linear in the the size of the deterministic automaton and its index, and can therefore be exponentially more succinct than minimal nondeterministic B\"uchi automata.
• Abstract（参考訳）: MDPを制御するためのモデルフリー強化学習(RL)において、オメガ正則目的が最初に提案されたとき、決定論的ラビンオートマトンを用いて、それらのスカラー値への遷移を直接翻訳した。 これらの翻訳は失敗したが、代わりにグッド・フォー・MDP(GFM)B\"uchi Automaticaを使用することで修復可能であることが判明した。 これらは非決定論的B\「うちオートマタ」であり、非決定論的に制限されるが、ゲーム用オートマタほど制限されない。 実際、決定論的ラビンオートマトンは、状態とペアの数で双線型であるようなGFMオートマトンにかなり簡単に変換できる。 非決定論的ラビン (non deterministic rabin) や b\"uchi automata への翻訳は、目標のオートマトンをmdpsとして必要とせずとも指数関数的にコストがかかる。 優れたMDPオートマトンを得るためには、それ以上の費用を払わなければなりませんか? 決定論的ラビンオートマトンから得られる非決定論的GFMオートマトンや、決定論的Streetオートマトンから得られる交代的グッド・フォー・MDPオートマトンは、決定論的オートマトンとそのインデックスのサイズにおいて二直線であり、したがって最小の非決定論的B\"uchiオートマトンよりも指数関数的に簡潔である。

関連論文リスト

• Learning Quantitative Automata Modulo Theories [17.33092604696224]
  本稿では,学習者が帰納的推論によって有効なオートマトンを推論する,能動的学習アルゴリズムQUINTICを提案する。 本評価では, 累積, 減算, 積, 量的オートマトンを学習するために, 有理理論を利用する。
  論文  参考訳（メタデータ） (2024-11-15T21:51:14Z)
• AutoMix: Automatically Mixing Language Models [62.51238143437967]
  大規模言語モデル(LLM)は、さまざまなサイズと構成のクラウドAPIプロバイダから利用可能になった。 より小さなLMからの出力の近似精度に基づいて,クエリを大規模LMに戦略的にルーティングする手法であるAutomixを提案する。
  論文  参考訳（メタデータ） (2023-10-19T17:57:39Z)
• Deciding Differential Privacy of Online Algorithms with Multiple Variables [0.41248472494152805]
  本稿では,このようなアルゴリズムを記述するために,DiPautomaticaと呼ばれるオートマトンモデルを一般化する。 我々のPSPACEアルゴリズムは、与えられたオートマトンが微分プライベートである場合、$mathfrakD$の値も計算する。
  論文  参考訳（メタデータ） (2023-09-12T22:03:01Z)
• Neuro-Symbolic Language Modeling with Automaton-augmented Retrieval [129.25914272977542]
  RetoMatonはデータストア上に構築された重み付き有限オートマトンである。 LM推論と並行して、このオートマトンを推論時にトラバースすることは、その複雑さを減少させる。
  論文  参考訳（メタデータ） (2022-01-28T21:38:56Z)
• Symbolic Register Automata for Complex Event Recognition and Forecasting [70.7321040534471]
  シンボリックレジスタオートマタ(シンボリックレジスタオートマタ、英: Symbolic Register Automata、SRA)は、シンボリックレジスタとレジスタオートマタの組み合わせである。 本稿では、イベントストリーム上のパターンを検出するために、複合イベント認識においてSRAがどのように使用できるかを示す。 また、イベントのストリームを消費するSRAの挙動を確率論的に説明できることを示す。
  論文  参考訳（メタデータ） (2021-10-08T11:04:51Z)
• On (co-lex) Ordering Automata [2.800608984818919]
  言語Lを受け入れる正準、最小幅、部分的に順序付けられたオートマトンを提示できることを示す。 Hを用いて、言語を認識する最小限のオートマトンから、言語幅を効果的に計算できることを証明する。
  論文  参考訳（メタデータ） (2021-06-04T07:41:58Z)
• Induction and Exploitation of Subgoal Automata for Reinforcement Learning [75.55324974788475]
  本稿では,Regressed Learning (RL)タスクにおけるサブゴールの学習と活用のためのISAを提案する。 ISAは、タスクのサブゴールによってエッジがラベル付けされたオートマトンであるサブゴールオートマトンを誘導することで強化学習をインターリーブする。 サブゴールオートマトンはまた、タスクの完了を示す状態と、タスクが成功せずに完了したことを示す状態の2つの特別な状態で構成されている。
  論文  参考訳（メタデータ） (2020-09-08T16:42:55Z)
• AutoFIS: Automatic Feature Interaction Selection in Factorization Models for Click-Through Rate Prediction [75.16836697734995]
  自動特徴相互作用選択(AutoFIS)と呼ばれる2段階のアルゴリズムを提案する。 AutoFISは、目標モデルを収束させるためにトレーニングするのと同等の計算コストで、因子化モデルに対する重要な特徴的相互作用を自動的に識別することができる。 AutoFISはHuawei App Storeレコメンデーションサービスのトレーニングプラットフォームにデプロイされている。
  論文  参考訳（メタデータ） (2020-03-25T06:53:54Z)
• Learning Autoencoders with Relational Regularization [89.53065887608088]
  データ分散のオートエンコーダを学習するための新しいフレームワークを提案する。 エンフレレーショナル正規化によるモデルと対象分布の差を最小限にする 我々はこのフレームワークを2つのスケーラブルアルゴリズムで実装し、確率的および決定論的オートエンコーダの両方に適用する。
  論文  参考訳（メタデータ） (2020-02-07T17:27:30Z)
• Reward Shaping for Reinforcement Learning with Omega-Regular Objectives [0.0]
  我々は、モデルフリー強化学習に優れたMDPオートマトンを利用する。 この翻訳の欠点は、報酬が平均的に非常に遅いことである。 この問題を克服する新たな報酬形成アプローチを考案する。
  論文  参考訳（メタデータ） (2020-01-16T18:22:50Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。