我们研究汤普森采样对上下文匪徒的效率。现有的基于汤普森采样的算法需要构建后验分布的拉普拉斯近似（即高斯分布），这是在一般协方差矩阵中的高维应用中效率低下的效率。此外，高斯近似可能不是对一般奖励产生功能的后验分布的良好替代物。我们提出了一种有效的后采样算法，即Langevin Monte Carlo Thompson采样（LMC-TS），该采样（LMC-TS）使用Markov Chain Monte Carlo（MCMC）方法直接从上下文斑块中的后验分布中直接采样。我们的方法在计算上是有效的，因为它只需要执行嘈杂的梯度下降更新而不构建后验分布的拉普拉斯近似。我们证明，所提出的算法实现了相同的sublinear遗憾，作为一种特殊情况的汤普森采样算法，是上下文匪徒的特殊情况，即线性上下文的强盗。我们在不同上下文匪徒模型上对合成数据和现实世界数据集进行实验，这表明直接从后验进行采样既具有计算上有效又具有竞争性能。

汤普森采样（TS）是解决上下文多武装强盗问题最有效的算法之一。在本文中，我们提出了一种新的算法，称为神经汤普森采样，这适应了深度神经网络，用于勘探和剥削。在我们的算法的核心是一种新的奖励的后分布，其平均值是神经网络近似器，并且其方差建立在相应神经网络的神经切线特征上。我们证明，如果底层奖励函数是有界的，则可以保证所提出的算法来实现$ \ mathcal {o}（t ^ {1/2}）$的累积遗憾，它与其他上下文强盗算法的遗憾匹配总轮数量$ t $。各种数据集中其他基准强盗算法的实验比较证实了我们的理论。

We consider the stochastic linear contextual bandit problem with high-dimensional features. We analyze the Thompson sampling (TS) algorithm, using special classes of sparsity-inducing priors (e.g. spike-and-slab) to model the unknown parameter, and provide a nearly optimal upper bound on the expected cumulative regret. To the best of our knowledge, this is the first work that provides theoretical guarantees of Thompson sampling in high dimensional and sparse contextual bandits. For faster computation, we use spike-and-slab prior to model the unknown parameter and variational inference instead of MCMC to approximate the posterior distribution. Extensive simulations demonstrate improved performance of our proposed algorithm over existing ones.

随机上下文的匪徒问题，建造了勘探和开发之间的权衡取舍，具有许多真实的应用，包括推荐系统，在线广告和临床试验。与许多其他机器学习算法一样，上下文匪徒算法通常具有一个或多个超参数。例如，在大多数最佳的随机上下文匪徒算法中，有一个未知的探索参数可以控制勘探和开发之间的权衡。适当的超参数选择对于上下文的匪徒算法表现良好至关重要。但是，由于没有预采用的数据集，因此必须使用离线调谐方法在上下文匪徒环境中选择超参数，并且必须实时做出决策。为了解决这个问题，我们首先提出了一个两层匪徒结构，用于自动调整勘探参数并将其进一步推广到联合匪徒框架，该框架可以在上下文的匪徒环境中动态学习多个超参数。我们得出了我们提议的联合匪徒框架的遗憾界限，并表明它可以避免对要调整的超参数的数量成倍依赖。此外，它在某些情况下达到了最佳的遗憾界限。联合匪徒框架足够通用，可以在许多流行的上下文匪徒算法（例如Linucb，Lints，UCB-GLM等）中处理调整任务。在合成数据集和真实数据集上进行了实验，以验证我们提出的框架的有效性。

我们研究汤普森采样（TS）算法的遗憾，指数为家庭土匪，其中奖励分配来自一个一维指数式家庭，该家庭涵盖了许多常见的奖励分布，包括伯努利，高斯，伽玛，伽玛，指数等。我们建议汤普森采样算法，称为expts，它使用新颖的采样分布来避免估计最佳臂。我们为expts提供了严格的遗憾分析，同时产生有限的遗憾和渐近遗憾。特别是，对于带指数级家庭奖励的$ k $臂匪徒，expts of horizo​​n $ t $ sub-ucb（对于有限的时间遗憾的是问题依赖的有限时间标准） $ \ sqrt {\ log k} $，并且对于指数家庭奖励，渐近最佳。此外，我们通过在Expts中使用的采样分配外添加一个贪婪的剥削步骤，提出$^+$，以避免过度估计亚最佳武器。 expts $^+$是随时随地的强盗算法，可用于指数级的家庭奖励分布同时实现最小值和渐近最优性。我们的证明技术在概念上很简单，可以轻松地应用于用特定奖励分布分析标准的汤普森抽样。

已经研究了几十年的上下文多武装匪，并适应了各种应用，如在线广告和个性化推荐。为了解决匪徒的开发探索权衡，有三种主要技术：epsilon - 贪婪，汤普森采样（TS）和上置信度（UCB）。在最近的文献中，线性上下窗匪徒采用了脊回归来估计奖励功能，并将其与TS或UCB策略结合起来的探索。但是，这行作品明确假设奖励基于ARM向量的线性函数，在现实世界数据集中可能不是真的。为了克服这一挑战，已经提出了一系列神经基的强盗算法，其中分配了神经网络以学习基础奖励功能，并且TS或UCB适于探索。在本文中，我们提出了一种具有新的探索策略的神经基匪徒方法。除了利用神经网络（开发网络）外学习奖励功能之外，与目前估计的奖励相比，EE-Net采用另一个神经网络（勘探网络）来自适应地学习潜在的增益。然后，构建决策者以将输出与剥削和探索网络组合起来。我们证明了EE-Net实现了$ \ mathcal {o}（\ sqrt {t \ log t}）$后悔，它比现有最先进的神经强盗算法更紧密（$ \ mathcal {o}（\基于UCB和TS的SQRT {T} \ log t）$。通过对四世界数据集的广泛实验，我们表明EE-Net优于现有的线性和神经匪徒的方法。

在本文中，我们考虑了在规避风险的标准下线性收益的上下文多臂强盗问题。在每个回合中，每个手臂都会揭示上下文，决策者选择一只手臂拉动并获得相应的奖励。特别是，我们将均值变化视为风险标准，最好的组是具有最大均值奖励的均值。我们将汤普森采样算法应用于脱节模型，并为提出算法的变体提供全面的遗憾分析。对于$ t $ rounds，$ k $ Actions和$ d $ - 维功能向量，我们证明了$ o（（1+ \ rho+\ frac {1} {1} {\ rho}）{\ rho}）d \ ln t \ ln t \ ln的遗憾。 \ frac {k} {\ delta} \ sqrt {d k t^{1+2 \ epsilon} \ ln \ frac {k} {\ delta} \ frac {1} {\ epsilon}} $ 1 - \ \ delta $在带有风险公差$ \ rho $的均值方差标准下，对于任何$ 0 <\ epsilon <\ frac {1} {2} $，$ 0 <\ delta <1 $。我们提出的算法的经验性能通过投资组合选择问题来证明。

我们建议使用$ \ tilde {o}（\ sqrt {\ kappa^{ - 1} \ phi t} \ phi t}）$ hears $ t $ the $ \ phi $ phi $是$ \ phi $是最olutimut，$ \ phi $是$ \ phi $，我们提出了一种用于广义线性奖励的新颖的上下文强盗算法。上下文协方差和$ \ kappa $的特征值是奖励差异的下限。在几种实际情况下，$ \ phi = o（d）$，我们的结果是带有$ \ sqrt {d} $的广义线性模型（GLM）土匪的第一个遗憾，而无需依赖Auer [2002]的方法。我们使用一个称为双重运动估计器的新型估计器（Doubly-bobust（DR）估计器的子类，但误差较紧，我们就实现了这种结合。 Auer [2002]的方法通过丢弃观察到的奖励来实现独立性，而我们的算法则在使用我们的DDR估计器的所有情况下实现了独立性。我们还提供了一个$ o（\ kappa^{ - 1} \ phi \ log（nt）\ log t）$遗憾在概率的边缘条件下以$ n $武器约束。 Bastani和Bayati [2020]和Bastani等人给出了遗憾的界限。 [2021]在环境中，所有臂都是共同的，但系数是特定的。当所有臂的上下文都不同，但系数很常见时，我们的第一个遗憾是在线性模型或GLM的边缘条件下绑定的。我们使用合成数据和真实示例进行实证研究，证明了我们的算法的有效性。

我们在存在对抗性腐败的情况下研究线性上下文的强盗问题，在场，每回合的奖励都被对手损坏，腐败级别（即，地平线上的腐败总数）为$ c \ geq 0 $。在这种情况下，最著名的算法受到限制，因为它们要么在计算效率低下，要么需要对腐败做出强烈的假设，或者他们的遗憾至少比没有腐败的遗憾差的$ C $倍。在本文中，为了克服这些局限性，我们提出了一种基于不确定性的乐观原则的新算法。我们算法的核心是加权山脊回归，每个选择动作的重量都取决于其置信度，直到一定的阈值。 We show that for both known $C$ and unknown $C$ cases, our algorithm with proper choice of hyperparameter achieves a regret that nearly matches the lower bounds.因此，我们的算法几乎是两种情况的对数因素的最佳选择。值得注意的是，我们的算法同时对腐败和未腐败的案件（$ c = 0 $）实现了近乎最理想的遗憾。

Thompson Sampling is one of the oldest heuristics for multi-armed bandit problems. It is a randomized algorithm based on Bayesian ideas, and has recently generated significant interest after several studies demonstrated it to have better empirical performance compared to the stateof-the-art methods. However, many questions regarding its theoretical performance remained open. In this paper, we design and analyze a generalization of Thompson Sampling algorithm for the stochastic contextual multi-armed bandit problem with linear payoff functions, when the contexts are provided by an adaptive adversary. This is among the most important and widely studied version of the contextual bandits problem. We provide the first theoretical guarantees for the contextual version of Thompson Sampling. We prove a high probability regret bound of Õ(d 3/2 √ T ) (or Õ(d T log(N ))), which is the best regret bound achieved by any computationally efficient algorithm for this problem, and is within a factor of √ d (or log(N )) of the information-theoretic lower bound for this problem.

We study bandit model selection in stochastic environments. Our approach relies on a meta-algorithm that selects between candidate base algorithms. We develop a meta-algorithm-base algorithm abstraction that can work with general classes of base algorithms and different type of adversarial meta-algorithms. Our methods rely on a novel and generic smoothing transformation for bandit algorithms that permits us to obtain optimal $O(\sqrt{T})$ model selection guarantees for stochastic contextual bandit problems as long as the optimal base algorithm satisfies a high probability regret guarantee. We show through a lower bound that even when one of the base algorithms has $O(\log T)$ regret, in general it is impossible to get better than $\Omega(\sqrt{T})$ regret in model selection, even asymptotically. Using our techniques, we address model selection in a variety of problems such as misspecified linear contextual bandits, linear bandit with unknown dimension and reinforcement learning with unknown feature maps. Our algorithm requires the knowledge of the optimal base regret to adjust the meta-algorithm learning rate. We show that without such prior knowledge any meta-algorithm can suffer a regret larger than the optimal base regret.

我们在这里采用贝叶斯非参数混合模型，以将多臂匪徒扩展到尤其是汤普森采样，以扩展到存在奖励模型不确定性的场景。在随机的多臂强盗中，播放臂的奖励是由未知分布产生的。奖励不确定性，即缺乏有关奖励生成分布的知识，引起了探索 - 开发权的权衡：强盗代理需要同时了解奖励分布的属性，并顺序决定下一步要采取哪种操作。在这项工作中，我们通过采用贝叶斯非参数高斯混合模型来进行奖励模型不确定性，将汤普森的抽样扩展到场景中，以进行灵活的奖励密度估计。提出的贝叶斯非参数混合物模型汤普森采样依次学习了奖励模型，该模型最能近似于真实但未知的每臂奖励分布，从而实现了成功的遗憾表现。我们基于基于后验分析的新颖的分析得出的，这是一种针对该方法的渐近遗憾。此外，我们从经验上评估了其在多样化和以前难以捉摸的匪徒环境中的性能，例如，在指数级的家族中，奖励不受异常值和不同的每臂奖励分布。我们表明，拟议的贝叶斯非参数汤普森取样优于表现，无论是平均累积的遗憾和遗憾的波动，最先进的替代方案。在存在强盗奖励模型不确定性的情况下，提出的方法很有价值，因为它避免了严格的逐案模型设计选择，但提供了重要的遗憾。

Authors are encouraged to submit new papers to INFORMS journals by means of a style file template, which includes the journal title. However, use of a template does not certify that the paper has been accepted for publication in the named journal. INFORMS journal templates are for the exclusive purpose of submitting to an INFORMS journal and should not be used to distribute the papers in print or online or to submit the papers to another publication.

在决策问题（例如多臂强盗）中，代理商通过优化某些反馈来顺序学习。尽管对平均奖励标准进行了广泛的研究，但其他反映对不利结果的措施，例如均值变化或有条件的危险价值（CVAR），对关键应用程序（医疗保健，农业）可能会引起人们的关注。在没有上下文信息的情况下，已经提出了在强盗反馈下采取此类风险感知措施的算法。在这项工作中，我们研究了上下文匪徒，通过最小化凸丢失，可以将这种风险度量作为上下文的线性函数引起。适合此框架的一个典型示例是预期度量，它作为不对称最小二乘问题的解决方案获得。使用超级马特林加尔的混合物方法，我们得出置信序列以估计此类风险度量。然后，我们提出一种乐观的UCB算法来学习最佳的风险感知动作，后悔的保证与广义线性匪徒相似。这种方法需要在每一轮算法上解决凸问题，我们可以通过仅允许通过在线梯度下降获得的近似解决方案来放松，以稍高的遗憾。我们通过评估数值实验的所得算法来结束。

在本文中，我们在稀疏的随机上下文线性土匪中重新审视了遗憾的最小化问题，其中特征向量可能具有很大的尺寸$ d $，但是奖励功能取决于一些，例如$ s_0 \ ll d $，其中这些功能的这些功能只要。我们提出了阈值拉索匪徒，该算法（i）估算了定义奖励功能及其稀疏支持的向量，即显着特征元素，使用带有阈值的Lasso框架，以及（ii）根据此处选择手臂估计预测其支持。该算法不需要对稀疏索引$ s_0 $的先验知识，并且可以在某些对称假设下不含参数。对于这种简单的算法，我们将非偶然的遗憾上限建立为$ \ mathcal {o}（\ log d + d + \ sqrt {t}）$一般，为$ \ mathcal {o} log t）$在所谓的边缘条件下（手臂奖励分离的概率条件）。以前的算法的遗憾将其缩放为$ \ Mathcal {o}（\ log D + \ \ sqrt {t \ log（d t）}）$和$ \ mathcal {o}（\ log log t \ log t \ log t \ log t \ log d）$设置分别。通过数值实验，我们确认我们的算法优于现有方法。

我们为随机线性匪徒问题提出了一种新的基于自举的在线算法。关键的想法是采用残留的自举勘探，在该探索中，代理商通过重新采样平均奖励估算的残差来估算下一步奖励。我们的算法，随机线性匪徒（\ texttt {linreboot}）的残留bootstrap探索，从其重新采样分布中估算了线性奖励，并以最高的奖励估计拉动了手臂。特别是，我们为理论框架做出了一个理论框架，以使基于自举的探索机制在随机线性匪徒问题中脱颖而出。关键见解是，Bootstrap探索的强度基于在线学习模型和残差的重新采样分布之间的乐观情绪。这样的观察使我们能够证明所提出的\ texttt {linreboot}确保了高概率$ \ tilde {o}（d \ sqrt {n}）$ sub-linear在温和条件下的遗憾。我们的实验支持\ texttt {重新启动}原理在线性匪徒问题的各种公式中的简易概括性，并显示了\ texttt {linreboot}的显着计算效率。

差异化（DP）随机凸优化（SCO）在可信赖的机器学习算法设计中无处不在。本文研究了DP-SCO问题，该问题是从分布中采样并顺序到达的流媒体数据。我们还考虑了连续发布模型，其中与私人信息相关的参数已在每个新数据（通常称为在线算法）上更新和发布。尽管已经开发了许多算法，以实现不同$ \ ell_p $ norm几何的最佳多余风险，但是没有一个现有的算法可以适应流和持续发布设置。为了解决诸如在线凸优化和隐私保护的挑战，我们提出了一种在线弗兰克 - 沃尔夫算法的私人变体，并带有递归梯度，以减少差异，以更新和揭示每个数据上的参数。结合自适应差异隐私分析，我们的在线算法在线性时间中实现了最佳的超额风险，当$ 1 <p \ leq 2 $和最先进的超额风险达到了非私人较低的风险时，当$ 2 <p \ p \ $ 2 <p \ leq \ infty $。我们的算法也可以扩展到$ p = 1 $的情况，以实现几乎与维度无关的多余风险。虽然先前的递归梯度降低结果仅在独立和分布的样本设置中才具有理论保证，但我们在非平稳环境中建立了这样的保证。为了展示我们方法的优点，我们设计了第一个DP算法，用于具有对数遗憾的高维广义线性土匪。使用多种DP-SCO和DP-Bandit算法的比较实验表现出所提出的算法的功效和实用性。

在本文中，我们研究了汤普森采样（TS）方法的应用到随机组合多臂匪徒（CMAB）框架中。当所有基本臂的结果分布都是独立的，并获得$ o（m \ log k _ {\ max} \ log t / \ delta_时，我们首先分析一般CMAB模型的标准TS算法。 {\ min}）$，其中$ m $是基本武器的数量，$ k _ {\ max} $是最大的超级臂的大小，$ t $是时间范围，而$ \ delta _ {\ min} $是最佳解决方案的预期奖励与任何非最佳解决方案之间的最小差距。这种遗憾的上限比$ o（m（\ log k _ {\ max}）^2 \ log t / \ delta _ {\ min}）$更好。此外，我们的新颖分析技术可以帮助收紧其他基于UCB的政策（例如ESC）的遗憾界限，因为我们改善了计算累积遗憾的方法。然后，我们考虑Matroid Bandit设置（CMAB模型的特殊类别），在这里我们可以删除跨武器的独立性假设，并实现与下限匹配的遗憾上限。除了遗憾的上限外，我们还指出，一个人不能直接替换确切的离线甲骨文（将离线问题实例的参数作为输入，并在此实例下输出确切的最佳操作），用TS算法中的近似oracle替换了ts算法的近似值。甚至经典的mAb问题。最后，我们使用一些实验来显示TS遗憾与其他现有算法之间的比较，实验结果表明TS优于现有基准。

在本文中，我们考虑了MNL-Bandit问题的上下文变体。更具体地说，我们考虑了一个动态设置优化问题，决策者为消费者提供了一系列产品（各种产品），并在每回合中观察他们的响应。消费者购买产品以最大化其实用性。我们假设一组属性描述了产品，并且产品的平均效用在这些属性的值中是线性的。我们使用广泛使用的多项式logit（MNL）模型对消费者选择行为进行建模，并考虑动态学习模型参数的决策者问题，同时优化累计收入，超过销售范围$ t $。尽管最近这个问题引起了人们的关注，但许多现有方法通常涉及解决棘手的非凸优化问题。他们的理论绩效保证取决于问题依赖性参数，该参数可能非常大。特别是，此问题的现有算法对$ o（\ sqrt {\ kappa d t}）$界后后悔，其中$ \ kappa $是问题依赖性常数，可以对属性的数量具有指数依赖性。在本文中，我们提出了一种乐观的算法，并表明遗憾是由$ o（\ sqrt {dt} + \ kappa）$界定的，从而大大提高了现有方法的性能。此外，我们提出了对优化步骤的放松，该步骤允许进行可牵引的决策，同时保留有利的遗憾保证。

我们研究上下文多军匪徒设置中的排名问题。学习代理在每个时间步骤中选择一个有序的项目列表，并观察每个位置的随机结果。在在线推荐系统中，显示最有吸引力的项目的有序列表将不是最佳选择，因为位置和项目依赖性都会带来复杂的奖励功能。一个非常天真的例子是，当所有最有吸引力的物品都来自同一类别时，缺乏多样性。我们为此问题在“排序列表”和“设计UCB”和Thompson采样类型算法中对位置和项目依赖性建模。我们证明，遗憾超过$ t $ rounds和$ l $ positions是$ \ tilde {o}（l \ sqrt {d t}）$，它的订单与以前在$ t $和$ t $方面的作品相同仅用$ L $线性增加。我们的工作将现有的研究推广到多个方向，包括位置折扣是特定情况的位置依赖性，并提出了更一般的背景匪徒模型。