| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2025-09-19 10:20 未知のグラフに対するグラフバンディット問題とその解法に関する一検討 ○中村 遼（福岡大）  CQ2025-58 |
|
| 抄録 | （和） | 多腕バンディット問題は強化学習における代表的な課題として研究されている。近年、Zhang らによって、多腕バンディット問題をグラフに展開した「グラフバンディット問題」が提唱されている。グラフバンディット問題とは、エージェントがノードを訪問すると、そのノードに付随する分布にもとづくランダムな報酬を受け取る、という設定のもとで、その報酬を最大化するようにエージェントの訪問系列を決定することである。グラフバンディット問題に対して、Zhang らは、ノードの報酬分布は未知であるもののグラフは既知である、という前提のもとで、G-UCB~(Graph-UCB) アルゴリズムを提案している。本稿では、報酬分布もグラフも未知である「未知のグラフに対するグラフバンディット問題」を検討する。本問題に対する一解法として、ランダムウォークによってノードの報酬分布およびパラメータの事後分布を推定する、という RWEst~(Random Walk with online Estimation) を提案する。RWEst の主要なアイデアは、ランダムウォークに従ってエージェントがノードを訪問し、報酬分布を逐次的に更新することで、期待報酬の高いノードを特定する、というものである。実験を通して、RWEst の有効性を検証したところ、(i) RWEst は、単純なランダムウォークより、十分に良好な性能を発揮できること、および (ii) 1,000 ノードのグラフでは、RWEst の G-UCB アルゴリズムに対する性能差は 10% に抑えられる、ということがわかった。 |
| （英） | The multi-armed bandit (MAB) problem is a representative topic in reinforcement learning and has been extensively studied. Zhang et al. proposed the graph bandit problem, which extends the multi-armed bandit problem to a graph. In the graph bandit problem, when an agent visits a node, it receives a random reward drawn from the distribution associated with that node; under this scenario, the objective is to determine a visitation sequence of the agent that maximizes the cumulative reward. For the graph bandit problem, under the assumption that the reward distributions of nodes are unknown but the graph is known, Zhang et al. proposed the G-UCB (Graph-UCB) algorithm. In this paper, we study the graph bandit problem on unknown graphs}, where both the reward distributions and the graph are unknown. As a solution to this problem, we propose RWEst~(Random Walk with online Estimation), which estimates each node's reward distribution and the posterior distribution of its parameters via a random walk. The main idea of RWEst is that the agent follows a random walk and, by vising a node and updating the reward distributions in an online manner, identifies the node with high expected reward. Through experiments, we demonstrate the effectiveness of RWEst; specifically (i) RWEst achieves sufficiently better performance than a simple random walk, and (ii) on a graph with 1,000 nodes, the performance gap of RWEst relative to the G-UCB algorithm is kept within 10%. | |
| キーワード | （和） | 強化学習 / 多腕バンディット問題 / グラフバンディット問題 / ランダムウォーク / / / / |
| （英） | Reinforcement Learning / Multi-Armed Bandit Problem / Graph Bandit Problem / Random Walk / / / / | |
| 文献情報 | 信学技報, vol. 125, no. 182, CQ2025-58, pp. 71-75, 2025年9月. | |
| 資料番号 | CQ2025-58 | |
| 発行日 | 2025-09-10 (CQ) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | CQ2025-58 |
|
| 研究会情報 | |
| 研究会 | CQ MIKA |
| 開催期間 | 2025-09-17 - 2025-09-19 |
| 開催地（和） | 天童温泉 ほほえみの宿 滝の湯 |
| 開催地（英） | |
| テーマ（和） | 無線通信品質、6G、IoT、CPS、無線リソース最適化制御、一般 |
| テーマ（英） | TBDWireless Communication Quality, 6G, IoT, CPS, Wireless Resource Optimization, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | CQ |
| 会議コード | 2025-09-CQ-MIKA |
| 本文の言語 | 日本語 |
| タイトル（和） | 未知のグラフに対するグラフバンディット問題とその解法に関する一検討 |
| サブタイトル（和） | |
| タイトル（英） | A Study on the Graph Bandit Problem on Unknown Graphs and its Solution |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 強化学習 / Reinforcement Learning |
| キーワード(2)（和/英） | 多腕バンディット問題 / Multi-Armed Bandit Problem |
| キーワード(3)（和/英） | グラフバンディット問題 / Graph Bandit Problem |
| キーワード(4)（和/英） | ランダムウォーク / Random Walk |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 中村 遼 / Ryo Nakamura / ナカムラ リョウ |
| 第1著者 所属（和/英） | 福岡大学 (略称： 福岡大) Fukuoka University (略称： Fukuoka Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2025-09-19 10:20:00 |
| 発表時間 | 25分 |
| 申込先研究会 | CQ |
| 資料番号 | CQ2025-58 |
| 巻番号（vol） | vol.125 |
| 号番号（no） | no.182 |
| ページ範囲 | pp.71-75 |
| ページ数 | 5 |
| 発行日 | 2025-09-10 (CQ) |
[研究会発表申込システムのトップページに戻る]