The 22nd Annual Conference of the Japanese Society for Artificial Intelligence, 2008 3A2-1 Profit Sharing 期待値 基 合理性 Rationality of Profit Sharing Based on Expected Value 松井 藤五郎 大和田 勇人 Tohgoroh Matsui Hayato Ohwada 東京理科大学 理工学部 経営工学科 Department of Industrial Administration, Faculty of Science and Technology, Tokyo University of Science This paper describes the rationality of profit sharing based on expected value. Miyazaki et al. proved the rationality, we call this the complete rationality, of profit sharing by analysing the worst case in all possible situations. However, the strong condition based on the complete rationality reduces the effectiveness of profit sharing. In this paper, we analyse the average case to show the expected rationality of profit sharing. s ∈ S, a ∈ A 1. P(s, a) ← C （C Profit sharing [Grefenstette 88] ， 行動 優先 度 割 当 強化学習法 ．Profit sharing ， ・ [Holland 86] 信用割当 技法 提案 ， 後 多 強化学習 影響 与 ．Grefenstette 手法 遺伝的 併 用 ，宮崎 profit sharing 一般的 強化 学習 枠組 扱 示 [宮崎 94]． Profit sharing ，環境 報酬 獲得 ，報酬獲得 至 状態行動系列中 状態行動対 信用割当関数 基 優先度 増加 ．Profit sharing ，Q 学習 行動 価値 推定 手法 比 (1) 学習 速 ，(2) 学 習中 振 舞 優 大 利点 持 ． 宮崎 ，[宮崎 94] ，profit sharing 報酬 獲得 政策 収束 条件 示 ．本論文 ， 宮崎 完全合理性条件 呼 ． 後， 基 profit sharing 環境，非定常環境， 部分観測環境 profit sharing 適用 研究 数多 行 ． Profit sharing 信用割当関数 等比減少関数 用 ． ，等比減少信用割当関数 用 宮崎 完全合理性条件 従 ，学習 遅 ，profit sharing 用 際 大 問題 ． ，本論文 ，MDP 等比減少信用割当関数 用 profit sharing 対 期待値 観点 基 profit sharing 合理性 割引率 条件 述 ． 2. Profit Sharing 2.1 対象 本論文 MDPs 各 繰 中 定数） ： 対 繰 行動選択確率 分布 状態 s 行動 a s 返 正 各 導 s← ： 小 初期化 P 行動 a 取 返 ： 従 ， 選択 ，報酬 r 次状態 s′ 観測 s′ 終端状態 繰 返 含 終了 状態行動対 対 ： P(st , at ) ← P(st , at ) + f (t, rT , T) 図 1: Profit sharing 分解 分系列 2.2 ． 環境 相互作用 終端状態 部分系列 扱 ． 初期状態 終端状態 部 呼 ． Profit Sharing Profit sharing [Holland 86, Grefenstette 88, 宮崎 94] ，代 表的 行動優先度学習型 強化学習 ， 状態 行動 優先度 学習 ．状態 s 行 動 a 優先度 P(s, a) 表 ， 優先度 P(s, a) 基 行動 選択 ． Profit sharing 図 1 示 ．Profit sharing ， s0 , a0 , r1 , . . . , sT−1 , aT−1 , rT 含 各状態行 動対 st , at 対 優先度 終了後 一括 次 強化 ． 完全合理性 問題 ，標準的 決定過程（MDPs） 型 対象 ． 関 記号 ，[Sutton 98] 倣 ． 環境 相互作用 P(st , at ) ← P(st , at ) + f (t, rT , T) ， f 信用割当関数 呼 一 状態行動対 s, a 信用割当関数 値 合計 ，∆P(s, a) 表 ． ， s0 , a0 , r1 , s1 , a1 , r2 , . . . , sT−1 , aT−1 , rT , sT 行動 対 状態 s 対 任意 状態 s ∈ S（S 状態 集合），行動 a ∈ A（A 集合），報酬 r ∈ ℜ（ℜ 実数 集合） 列 表 ， 2.3 Profit Sharing 状態行動対 現在 常 迂回経路上 出現 ．状態行動対 無効 連絡先: 松井藤五郎, 東京理科大学 理工学部 経営工学科, [email protected], http:// .jp 1 関数 ， s, a 対 学習 ， ． 最 困難 出現 強化値 状態 状態行動対 無効 ，有効 ． The 22nd Annual Conference of the Japanese Society for Artificial Intelligence, 2008 宮崎 a(1) 完全合理性条件 従 ，取 得 行動 数 大 信用割当 非常 小 ，学習 進行 遅 ． ，宮崎 完全合理性条件 実用的 ． a(0) a(2) s(0) ... 3. Profit Sharing 期待合理性 a(L) 宮崎 完全合理性定理 完全合理性条件 ，profit sharing 直面 可能性 最悪 場合 解析 ，無効 ，合理性 保 行動 抑制 ． ，実際 ， 非常 稀 図 2: Profit sharing 学習 最 困難 状態 [宮崎 94]． ． ，profit sharing 自然 制限 加 ，profit sharing 学習 最 困難 状 宮崎 ，[宮崎 94] 中 ，profit sharing 学習 態 [宮崎 94] profit sharing 直面 平均的 場合 最 困難 状態 示 ． ，期待値 観点 基 profit sharing ¶ ³ 合理性 示 ． 補題 1 (学習 最 困難 状態) 図 2 示 ， 3.1 非決定的単調増加行動選択法 以上 有効 行動 唯一 回帰的 無効 行動 期待値 観点 基 profit sharing 合理性 示 競合 状態 ，profit sharing 学習 最 困難 状態 ． ，本論文 ，行動選択法 次 定義 非決定的 µ ´ 単調増加行動選択法 限定 ． ¶ ³ ，有効 行動 実行 遷移先 状態 終端状態 目標状態 ，正 報酬 与 ． 定義 1 (非決定的行動選択法) 非決定的行動選択法 ，任 a(i) ，Rs(0) > 0（i = 1, 2, . . . , L） ． ，Rsa 状態 s 意 状態行動対 s, a 対 ，行動選択確率 次 式 満 行動 a 行 得 報酬 期待値 表 ，L 有 効 行動 数 表 ．Profit sharing 途中 報 酬 0 ，唯一存在 回帰的 無効 行 a(0) ，Rs(0) =0 ． 動 a(0) 対 報酬 0 ¶ 定理 1 (Profit sharing 用割当関数 f ， ，profit sharing 強化値 分析 条件 示 ． 完全合理性) Profit sharing f (t, rT , T) > L t−1 ∑ ´ ³ 定義 2 (単調増加行動選択法) 単調増加行動選択法 ，優 先度 P(s, a) < P(s, a′ ) 任意 状態行動対 s, a s, a′ 対 ，行動選択確率 次 式 満 ． 学習 ，無 ³ 信 µ Pr(at = a | st = s) ≤ Pr(at = a′ | st = s) ´ 強化学習 ，一般的 ，非決定的単調増加行動選択法 用 ． ，Boltzmann 分布 用 選択，ϵ選択，一様選択 ， 非決定的単 調増加行動選択法 ． 選択 ，profit sharing 非決定的単調増加行動選択法 ． ，強化学習 行動選択法 非決定的単調増 加行動選択法 限定 厳 制約 ． f (i, rT , T) i=0 満 動 Pr(at = a | st = s) < 1 µ ¶ 2.4 宮崎 合理性定理 合理性条件 宮崎 ，[宮崎 94] 最 困難 状態 効 行動 抑制 ． ，任意 状態 ，任意 無効 行 抑制 ． ，L ，同一 入力状態 存在 有効 行動 最大個数 ． 3.2 期待強化値 ， 得 µ ´ Profit sharing 強化値 ， 出現 状態行動対 最後 得 ，本論文 ，宮崎 完全合理性定理 呼 （証明 報酬 確率的 決 ． ， profit sharing [宮崎 94] 参照）． 強化値 ，確率変数 表 ． Profit sharing 信用割当関数 f ，等比減少関数 行動選択法 非決定的 限定 ，profit sharing f (t, rT , T) = γT−t−1 rT (0 ≤ γ ≤ 1) ， 以上 有効 行 学習 最 困難 動 a(i)（i = 1, 2, . . . ） 唯一 回帰的 無効 行動 a(0) 競合 用 ． ，γ 割引率 ． 状態 s(0) ，profit sharing n 回目 等比減少関数 用 ，優先度 P(st , at ) 増分 時間 得 有効 行動 a(i) 対 強化値 ∆Pn (s(0) , a(i) ) 期待 減 ． ，前 使 状態行動 a(i) 値 ，行動選択確率 pn(0) , pn(i) 期待報酬 Rs(0) 表 対 ， 優先度 増分 小 ．等比減少信用割当関 ． ，pn(i) ，n 回目 状 数 ，割引率 態 s(0) 行動 a(i) 選択確率 pn(i) = Prn (at = a(i) | st = s(0) ) 1 γ≤ 表 ． L 宮崎 完全合理性定理 満 ，宮崎 完全合理性条件 呼 ． ． 条件 ， 2 The 22nd Annual Conference of the Japanese Society for Artificial Intelligence, 2008 ¶ ³ [ ] [ pn(i) a E ∆Pn (s(0) , a(i) ) = E R (i) 1 − pn(0) s(0) 割引率 γ 制限 γ 条件 制限 ，期待合理性定理 補題 2 (有効 行動 期待強化値) 以上 有効 行 動 a(i) （i = 1, 2, . . . ） 唯一 回帰的 無効 行動 a(0) 競合 状態 s(0) ，profit sharing 非決定的 行動選択法 従 行動 選択 ，profit sharing n 回目 得 有効 行動 a(i) 対 強化値 ∆Pn (s(0) , a(i) ) 期待値 ， ． 0≤γ≤1 ．本論文 ] 4. ， 期待合理性条件 呼 ． 考察 宮崎 完全合理性定理 最 学習 困難 状態 最 分析 対 ，本論文 示 期待合理性定 ． 同状態 平均的 分析 ． µ ´ 期待合理性定理 ，profit sharing ，等比減少信用割当関 証明 紙面 都合 省略 ． 数 用 ，非決定的単調増加行動選択法 従 独立 行動 ，信用割当関数 等比減少関数 限定 ，同様 選択 ，有効 行動 存在 状態 ，唯一 回帰的 無効 行動 a(0) 対 強化値 ∆Pn (s(0) , a(0) ) ，選択確率 期待値 最大 有効 行動 存在 a(i) 期待値 行動選択確率 pn(i) 期待報酬 Rs(0) （i = 0, . . . , L） 示 ． 表 ． 期待合理性条件 ，上 条件 満 profit sharing ¶ ³ 用 ，平均的 ，割引率 γ 上限 1 範囲 内 大 示 ． ， 補題 3 (唯一 回帰的 無効 行動 期待強化値) L 個 取 得 行動 数 関係 割引率 設定 有効 行動 a(i)（i = 1, . . . , L） 唯一 回帰的 無効 行 動 a(0) 競合 状態 s(0) ，割引率 γ 等 点 ，宮崎 完全合理性条件 優 ． 比減少信用割当関数 用 profit sharing 非決定的行 動選択法 従 行動 選択 ，n 回目 5. 得 唯一 回帰的 無効 行動 a(0) 対 強化値 ∆Pn (s(0) , a(0) ) 期待値 ， 本論文 ，期待値 観点 基 profit sharing 合理性 述 ． L ∑ [ ] 本論文 示 期待合理性定理 ，profit sharing (1) 等 γpn(0) a(i) )( ) E ∆Pn (s(0) , a(0) ) = E ( pn(i) Rs(0) 1−p 比減少信用割当関数 用 ，(2) 非決定的単調増加行動選択法 1 − γp n(0) n(0) i=1 従 ，(3) 独立 行動 選択 ，有効 行動 選択 確率 期待値 最大 示 ． ，割引 ． 条件 0 ≤ γ ≤ 1 満 µ ´ 率 γ ，等比減少関数 ． 期待合理性条件 ，(1) 速 学習 ， 証明 紙面 都合 省略 ． (2) 取 得 行動 数 依存 点 宮崎 完全合理 3.3 期待合理性定理 性条件 優 ． Profit sharing ，確率的 行動選択法 用 ， 紙面 都合 省略 証明 ，近 人工 行動選択確率 Pr(at = a | st = s) ， 経験 状態行 知能学会論文誌 発表 ． 動対 獲得 報酬 確率的 決 確率変数 表 ． ， 確率変数 期待値 考 ． 参考文献 補題 2 補題 3 ，profit sharing 学習 最 困 難 状態 s(0) ，profit sharing 等比減少信用割当関 [Grefenstette 88] Grefenstette, J. J.: Credit assignment in 数 用 ，非決定的単調増加行動選択法 従 独立 行動 rule discovery systems based on genetic algorithms, Ma選択 有効 行動 対 強化値 期待値 無効 行 chine Learning, Vol. 3, pp. 225–245 (1988) 動 対 強化値 期待値 大小関係 調 ，補題 1 合 [Holland 86] Holland, J. H.: Escaping Brittleness: The Possi一般的 状態 拡張 次 定理 導 bilities of General-Purpose Learning Algorithms Applied ． ¶ ³ to Parallel Rule-Based Systems, in Michalski, R. S., Carbonell, J. G., and Mitchell, T. M. eds., Machine Learning: An 定理 2 (Profit sharing 期待合理性) Profit sharing ， Artificial Intelligence Approach, Vol. 2, Morgan Kaufmann 等比減少信用割当関数 用 ， ，非決定的単調増加 Publishers (1986) 行動選択法 従 独立 行動 選択 ，有効 悪 理 状態 対 存在 任意 状態 s ，任意 行動 a [宮崎 94] 宮崎 和光, 山村 雅幸, 小林 重信：強化学習 報酬割当 理論的考察, 人工知能学会誌, Vol. 9, No. 4, pp. 580–587 (1994) E [Pr(at = a′ | st = s)] ≥ E [Pr(at = a | st = s)] 満 µ 有効 行動 a′ 存在 ． 証明 紙面 都合 省略 ．本論文 ， profit sharing 期待合理性定理 呼 ． 定理 ，信用割当関数 ，関数 等比減少 [Sutton 98] Sutton, R. S. and Barto, A. G.: Reinforcement Learning: An Introduction, The MIT Press (1998), 三上貞 ´ 芳, 皆川雅章 共訳. 強化学習. 森北出版, 2000 3
© Copyright 2024 ExpyDoc
