使用遗忘采样器在低秩结构的多臂老虎机中进行纯探索

Jun, 2023

使用遗忘采样器在低秩结构的多臂老虎机中进行纯探索

Pure exploration in multi-armed bandits with low rank structure using oblivious sampler

Yaxiong Liu, Atsuyoshi Nakamura, Kohei Hatano, Eiji Takimoto

TL;DR该论文考虑了纯探索问题回报序列的低秩结构，提出了一种分离设置的探索策略，并通过利用奖励向量的核信息，提供了高效算法，同时展示了多臂赌博机问题下纯探索的上下界。

Abstract

In this paper, we consider the low rank structure of the reward sequence of the pure exploration problems. Firstly, we propose the separated setting in pure exploration problem, where the →

low rank structure pure exploration problems exploration strategy regret bound multi-armed bandits

发现论文，激发创造

多臂赌博机中的探索与利用分离

研究了多臂赌博问题中的探索和利用问题，并提出了一种基于非均匀采样策略的算法，用于解决带有分段稳定随机赌博问题的情况，并实现了对于超宽带通道选择的模拟测试。

May, 2012

核和神经赌博中的纯探索

本文研究了一种新的纯探索选择策略，通过自适应地将每个手臂的特征表示嵌入到低维空间中并仔细处理引起的模型错误，成果展示了该方法在核空间或神经表示中实现的有效维度。实验证明了该方法的有效性。

Jun, 2021

探索不再：非随机赌博机的改进高概率遗憾界限

本文提出了基于 Implicit eXploration 的损失估计策略，可以在不需要不必要的探索成分的情况下，实现高概率遗憾界，取得了多臂赌博问题方面的改进结果。

Jun, 2015

线性赌臂机中纯探索的完全自适应算法

本文提出了第一个完全自适应的算法用于求解线性赌博机中的最优选择问题，并且其采样复杂度与已有算法相当。此外，通过模拟实验表明，在合成和真实数据集上均远优于现有的方法。

Oct, 2017

通过解游戏进行非渐近纯探索

本文提出了一种适用于纯探索问题和赌博机结构的不需完全解决优化问题的优化算法，并获得了对指数族的适应性和有限信心保证。

Jun, 2019

非静态奖励多臂老虎机问题中的最优探索利用

本文讨论在不确定性的情况下如何在多臂老虎机问题中进行赌博，提出了一种正式的处理方法，并建立了不同类型的奖励变化和最小化遗憾之间的直接联系。

May, 2014

分布式内核赌博机中使用共享随机采样的最佳订单遗憾

我们提出了第一个算法，它以次线性的通信成本实现了最佳的（以集中式学习定义的）遗憾顺序，通过局部智能的均匀探索和与中央服务器共享随机性这两个关键组成部分与 GP 模型的稀疏近似共同作用，能够以递减的通信速率保持集中设置的学习速率。

Feb, 2024

高斯过程赌博机的最优顺序简单后悔

研究了高斯过程二元组和连续性优化问题之间的联系，建立了稳健分布，使用分步方式获得最终收敛结果并得到了一系列引理。

Aug, 2021

结构化随机赌臂问题中的最小探索

介绍了一类广泛的随机赌博问题，其中将臂与相应的奖励映射的函数具有一些已知的结构特性。推导了这些问题的渐近特定情况下的遗憾下界，并且开发了 OSSB 算法，其遗憾匹配了这个基本极限。通过数值实验展示了 OSSB 的效率，并且证明 OSSB 优于包括汤普森取样在内的现有算法。

Nov, 2017

无限臂老虎机渐进最优纯探索

本文研究了纯探索问题中具有无限多臂的赌博机问题，针对固定置信和固定预算两种情形，提出了两种算法，分别以最小的期望和固定样本复杂度为目标，最终准确选择一个高质量臂，使其平均奖励与前 $η$ 的部分的奖励最大值的差别小于 $ε$，并给出了理论证明。

Jun, 2023