We study Thompson Sampling-based algorithms for stochastic bandits with
bounded rewards. As the existing problem-dependent regret bound for Thompson
Sampling with Gaussian priors [Agrawal and Goyal, 2017] is vacuous when $T \le
288 e^{64}$, we derive a more practical bound that tightens the coefficient of
the leading term %from $288 e^{64}$ to $1270$. Additionally, motivated by
large-scale real-world applications that require scalability, adaptive
computational resource allocation, and a balance in utility and computation, we
propose two parameterized Thompson Sampling-based algorithms: Thompson Sampling
with Model Aggregation (TS-MA-$\alpha$) and Thompson Sampling with Timestamp
Duelling (TS-TD-$\alpha$), where $\alpha \in [0,1]$ controls the trade-off
between utility and computation. Both algorithms achieve $O
\left(K\ln^{\alpha+1}(T)/\Delta \right)$ regret bound, where $K$ is the number
of arms, $T$ is the finite learning horizon, and $\Delta$ denotes the single
round performance loss when pulling a sub-optimal arm.

我们研究了基于 Thompson Sampling 的有界奖励随机赌博算法。为了解决现有的与高斯先验的 Thompson Sampling 相关的问题相关后悔界限在 T≤288e^64 时是虚无的问题，我们导出了一个更实用的界限，将主要项的系数从 288e^64 缩小到 1270。此外，我们提出了两种参数化的 Thompson Sampling 算法：带有模型聚合的 TS-MA-α 和带有时间战斗的 TS-TD-α，其中 α∈[0,1] 控制效用与计算之间的权衡。这两种算法都可以实现 O (Kln^(α+1)(T)/Δ) 的后悔界限，其中 K 是臂数量，T 是有限学习时段，Δ 表示拉动次优臂时的单轮性能损失。

智能和适应后验采样算法用于二元选择

Efficient and Adaptive Posterior Sampling Algorithms for Bandits

In the field of quantum information, classical optimizers play an important
role. From experimentalists optimizing their physical devices to theorists
exploring variational quantum algorithms, many aspects of quantum information
require the use of a classical optimizer. For this reason, there are many
papers that benchmark the effectiveness of different optimizers for specific
quantum optimization tasks and choices of parameterized algorithms. However,
for researchers exploring new algorithms or physical devices, the insights from
these studies don't necessarily translate. To address this concern, we compare
the performance of classical optimizers across a series of partially-randomized
tasks to more broadly sample the space of quantum optimization problems. We
focus on local zeroth-order optimizers due to their generally favorable
performance and query-efficiency on quantum systems. We discuss insights from
these experiments that can help motivate future works to improve these
optimizers for use on quantum systems.

在量子信息领域，经典优化器起着重要的作用。针对量子最优化任务和参数化算法的不同优化器的有效性进行基准测试对于研究人员来说很重要。然而，对于探索新算法或物理设备的研究人员来说，这些研究所得的见解不能直接应用。为了解决这个问题，我们通过在部分随机化任务上比较经典优化器的性能，更广泛地采样量子最优化问题的空间。我们重点关注局部零阶优化器，因为它们在量子系统上通常表现出良好的性能和查询效率。我们讨论了从这些实验中得出的见解，可以激发未来的研究来改进这些优化器在量子系统上的使用。

用于变分量子系统的局部零阶优化器的随机基准测试

Randomized Benchmarking of Local Zeroth-Order Optimizers for Variational  Quantum Systems

A central problem in parameterized algorithms is to obtain algorithms
with running time $f(k)\cdot n^{O(1)}$ such that $f$ is as slow growing
function of the parameter $k$ as possible. In particular, a large number of
basic parameterized problems admit parameterized algorithms where $f(k)$ is
single-exponential, that is, $c^k$ for some constant $c$, which makes aiming
for such a running time a natural goal for other problems as well. However
there are still plenty of problems where the $f(k)$ appearing in the best known
running time is worse than single-exponential and it remained ``slightly
superexponential'' even after serious attempts to bring it down. A natural
question to ask is whether the $f(k)$ appearing in the running time of the
best-known algorithms is optimal for any of these problems.
In this paper, we examine parameterized problems where $f(k)$ is
$k^{O(k)}=2^{O(k\log k)}$ in the best known running time and for a number of
such problems, we show that the dependence on $k$ in the running time cannot be
improved to single exponential. (See paper for the longer abstract.)

本文检查了参数算法的优化问题，其中 $f (k)=k^{O (k)}$ 为最佳运行时间，针对一些这样的问题，我们证明了运行时间中对 $k$ 的依赖不能优化为单次指数。

轻微超指数参数化问题

Slightly Superexponential Parameterized Problems

We study the recently introduced Connected Feedback Vertex Set (CFVS) problem
from the view-point of parameterized algorithms. CFVS is the connected variant
of the classical Feedback Vertex Set problem and is defined as follows: given a
graph G=(V,E) and an integer k, decide whether there exists a subset F of V, of
size at most k, such that G[V F] is a forest and G[F] is connected. We show
that Connected Feedback Vertex Set can be solved in time $O(2^{O(k)}n^{O(1)})$
on general graphs and in time $O(2^{O(\sqrt{k}\log k)}n^{O(1)})$ on graphs
excluding a fixed graph H as a minor. Our result on general undirected graphs
uses as subroutine, a parameterized algorithm for Group Steiner Tree, a well
studied variant of Steiner Tree. We find the algorithm for Group Steiner Tree
of independent interest and believe that it will be useful for obtaining
parameterized algorithms for other connectivity problems.

研究了连接反馈顶点集（Connected Feedback Vertex Set）问题的参数化算法，论述了该问题在图论领域的应用，证明了在普通图上复杂度为 O (2^O (k) n^O (1))，在不包含固定图 H 的图上复杂度为 O (2^O (√k logk) n^O (1))，此外将 Group Steiner Tree 问题用作子程序，并认为其独立于其他算法，具有重要意义。