論文の概要: Categorizer Automata for Discounted-Sum Payoffs
- arxiv url: http://arxiv.org/abs/2608.26763v1
- Date: Thu, 27 Aug 2026 07:56:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-28 16:30:58.298023
- Title: Categorizer Automata for Discounted-Sum Payoffs
- Title（参考訳）: ディスカウントサム支払いのための分類器オートマタ
- Abstract要約: 本稿では、無限個の報酬列を読み取って、その割引和を含む有限個のビンのうちどれを識別する決定論的オートマトンであるカソーサ・オートマトンを紹介する。
我々は、マルコフ決定プロセスにカソーマオートマトンを適用し、そこでは、割引済の支払いが期待できる効用を最大化するポリシーを合成することができる。
ピースワイズ・リプシッツのユーティリティ関数の場合、有限個のジャンプの間に有界な傾きを持つ任意のユーティリティを含むクラスは、再び擬多項式時間で実行され、$varepsilon$-optimal Policy が得られる。
- 参考スコア（独自算出の注目度）: 4.8981980337377555
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Categorizing continuous data into discrete bins is a fundamental operation in artificial intelligence. We introduce the categorizer automaton, a deterministic automaton that reads an infinite sequence of rewards and identifies which of finitely many bins contains its discounted sum. Categorizer automata generalize comparator automata, the special case of two bins, which have already proven useful in quantitative synthesis. Our main technical contribution is the construction of a categorizer automaton whose state space is linear in the number of bins, rather than exponential as obtained by a cross-product of comparator automata. We then apply categorizer automata to Markov decision processes, where they allow one to synthesize policies that maximize the expected utility of a discounted-sum payoff for utility functions that may be discontinuous. For piecewise-constant utility functions, the resulting algorithm is exact and runs in pseudo-polynomial time. For piecewise-Lipschitz utility functions, a class that includes any utility with bounded slope between finitely many jumps, it again runs in pseudo-polynomial time and yields an $\varepsilon$-optimal policy. We also show that the synthesis problem considered is PSPACE-hard already for piecewise-constant utilities.
- Abstract（参考訳）: 連続したデータを離散的なビンに分類することは、人工知能の基本的な操作である。
本稿では、無限個の報酬列を読み取って、その割引和を含む有限個のビンのうちどれを識別する決定論的オートマトンであるカソーサ・オートマトンを紹介する。
分類器オートマトンは、2つのビンの特別な場合であるコンパレータオートマトンを一般化する。
我々の主な技術的貢献は、コンパレータオートマトン(英語版)のクロス積から得られる指数関数ではなく、状態空間がビン数で線型なカウンタオートマトンの構築である。
次に、マルコフ決定プロセスにカテスタオートマトンを適用し、不連続なユーティリティ関数に対して割引済の支払いを最大化するためのポリシーを合成する。
ピースワイズ・コンスタントなユーティリティ関数の場合、結果のアルゴリズムは正確であり、擬似多項式時間で実行される。
ピースワイズ・リプシッツのユーティリティ関数の場合、有限個のジャンプの間に有界な傾きを持つ任意のユーティリティを含むクラスは、再び擬多項式時間で実行され、$\varepsilon$-optimal Policy が得られる。
また,PSPACE-hardが一括整合性のためにすでに検討されていることも示している。
関連論文リスト
- SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant [79.24089819400126]
Subsampled TurboQuant (SSTQ) は、オーバーコンプリートな等幅のタイトフレーム、座標サブサンプリング、プライバシ対応量子化を組み合わせたフレームワークである。
SSTQは平均2乗誤差スケーリングを実現し、クライアントあたり$lceil log N il + b$ bitsを使用する。
また、コードブックに依存したMSEスケーリングを$O(4b)$から$O(2b)$に削減する、プライバシを意識したコードブックの目的も導出します。
論文 参考訳（メタデータ） (2026-08-05T17:51:25Z) - AutoLALA: Automatic Loop Algebraic Locality Analysis for AI and HPC Kernels [6.223124502234209]
AutoLALAは、アフィンループプログラムにおけるデータのローカリティを分析するオープンソースツールである。
再利用距離とデータ移動複雑性のための閉形式記号式を生成する。
論文 参考訳（メタデータ） (2026-04-06T18:12:39Z) - On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach [59.589793281734636]
我々は,アルファベットサイズと入力長の両方が状態数である場合に,統計的クエリの硬さを確立することができることを示す。
この結果は、半オートマタの内部状態遷移構造からのみ導かれる。
論文 参考訳（メタデータ） (2025-10-05T09:35:35Z) - Learning Quantitative Automata Modulo Theories [17.33092604696224]
本稿では,学習者が帰納的推論によって有効なオートマトンを推論する,能動的学習アルゴリズムQUINTICを提案する。
本評価では, 累積, 減算, 積, 量的オートマトンを学習するために, 有理理論を利用する。
論文 参考訳（メタデータ） (2024-11-15T21:51:14Z) - Deciding Differential Privacy of Online Algorithms with Multiple Variables [0.41248472494152805]
本稿では,このようなアルゴリズムを記述するために,DiPautomaticaと呼ばれるオートマトンモデルを一般化する。
我々のPSPACEアルゴリズムは、与えられたオートマトンが微分プライベートである場合、$mathfrakD$の値も計算する。
論文 参考訳（メタデータ） (2023-09-12T22:03:01Z) - Automata Learning from Preference and Equivalence Queries [17.33092604696224]
本稿では,能動オートマトン学習問題の新たな変種として,嗜好クエリを用いて有限オートマトンを積極的に学習する手法を提案する。
ReMAPは、クエリの複雑さの最小限の複雑さを、正確な等価クエリの下で正確に推測することが保証されている。
実験により,REMAPを大規模オートマトンにスケールすることは,一貫した教師から正しいオートマトンを学習するのに有効であることが示唆された。
論文 参考訳（メタデータ） (2023-08-18T04:49:45Z) - Unified Functional Hashing in Automatic Machine Learning [58.77232199682271]
高速に統一された関数型ハッシュを用いることで,大きな効率向上が得られることを示す。
私たちのハッシュは"機能的"であり、表現やコードが異なる場合でも同等の候補を識別します。
ニューラルアーキテクチャ検索やアルゴリズム発見など、複数のAutoMLドメインで劇的な改善がなされている。
論文 参考訳（メタデータ） (2023-02-10T18:50:37Z) - Automatically Bounding the Taylor Remainder Series: Tighter Bounds and
New Applications [10.824474741383723]
テイラー剰余級数を自動的に有界化するための新しいアルゴリズムを提案する。
我々のアルゴリズムは機械学習ハードウェアを効率的に利用することができ、JAX.NETのオープンソース実装を提供しています。
コンパニオンペーパーでは、我々の新しい機械を用いて、最初の普遍的偏化最小化最適化アルゴリズムを作成する。
論文 参考訳（メタデータ） (2022-12-22T00:43:06Z) - Faster Privacy Accounting via Evolving Discretization [54.32252900997422]
プライバシランダム変数の数値合成のための新しいアルゴリズムを提案する。
本アルゴリズムは,メカニズムを自己コンパイルするタスクに対して,$mathrmpolylog(k)$の実行時間とメモリ使用量を達成する。
論文 参考訳（メタデータ） (2022-07-10T04:25:37Z) - Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and
Costs [45.87981728307819]
異種空間に居住する関連するデータセットを比較して整列する能力は、機械学習においてますます重要な役割を担っている。
グロモフ・ワッサーシュタイン (Gromov-Wasserstein, GW) 形式主義はこの問題に対処するのに役立つ。
論文 参考訳（メタデータ） (2021-06-02T12:50:56Z) - Induction and Exploitation of Subgoal Automata for Reinforcement
Learning [75.55324974788475]
本稿では,Regressed Learning (RL)タスクにおけるサブゴールの学習と活用のためのISAを提案する。
ISAは、タスクのサブゴールによってエッジがラベル付けされたオートマトンであるサブゴールオートマトンを誘導することで強化学習をインターリーブする。
サブゴールオートマトンはまた、タスクの完了を示す状態と、タスクが成功せずに完了したことを示す状態の2つの特別な状態で構成されている。
論文 参考訳（メタデータ） (2020-09-08T16:42:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。