The multi-armed bandit(MAB) problem is a simple yet powerful framework that
has been extensively studied in the context of decision-making under
uncertainty. In many real-world applications, such as robotic applications,
selecting an arm corresponds to a physical action that constrains the choices
of the next available arms (actions). Motivated by this, we study an extension
of MAB called the graph bandit, where an agent travels over a graph to maximize
the reward collected from different nodes. The graph defines the agent's
freedom in selecting the next available nodes at each step. We assume the graph
structure is fully available, but the reward distributions are unknown. Built
upon an offline graph-based planning algorithm and the principle of optimism,
we design a learning algorithm, G-UCB, that balances long-term
exploration-exploitation using the principle of optimism. We show that our
proposed algorithm achieves $O(\sqrt{|S|T\log(T)}+D|S|\log T)$ learning regret,
where $|S|$ is the number of nodes and $D$ is the diameter of the graph, which
matches the theoretical lower bound $\Omega(\sqrt{|S|T})$ up to logarithmic
factors. To our knowledge, this result is among the first tight regret bounds
in non-episodic, un-discounted learning problems with known deterministic
transitions. Numerical experiments confirm that our algorithm outperforms
several benchmarks.

本论文研究了一种称为图赌博机的多臂赌博机扩展问题，提出了一种能够利用乐观原则平衡长期探索与开发的学习算法 G-UCB，并证明其能够达到理论最优的遗憾界，数值实验结果表明该算法优于其他基准算法。