元,多任务和联合学习可以全部被视为解决类似的任务,从反映任务相似之处的未知分发中汲取类似的任务。在这项工作中,我们提供了所有这些问题的统一视图,因为在分层贝叶斯匪徒中采取行动。我们分析了一种自然的分层汤普森采样算法(HIERTS),可以应用于此类中的任何问题。我们的遗憾界限在此类问题的许多情况下持有,包括当任务顺序或并行解决时;并捕获问题的结构,使得遗憾地随着任务的宽度而减少。我们的证据依赖于新的总方差分解,可以应用于其他图形模型结构。最后,我们的理论是由实验补充的,表明层次结构有助于任务之间的知识共享。这证实了分层贝叶斯匪徒是一种普遍和统计学的工具,用于学习与类似的匪徒任务进行行动。
translated by 谷歌翻译
Many practical applications, such as recommender systems and learning to rank, involve solving multiple similar tasks. One example is learning of recommendation policies for users with similar movie preferences, where the users may still rank the individual movies slightly differently. Such tasks can be organized in a hierarchy, where similar tasks are related through a shared structure. In this work, we formulate this problem as a contextual off-policy optimization in a hierarchical graphical model from logged bandit feedback. To solve the problem, we propose a hierarchical off-policy optimization algorithm (HierOPO), which estimates the parameters of the hierarchical model and then acts pessimistically with respect to them. We instantiate HierOPO in linear Gaussian models, for which we also provide an efficient implementation and analysis. We prove per-task bounds on the suboptimality of the learned policies, which show a clear improvement over not using the hierarchical model. We also evaluate the policies empirically. Our theoretical and empirical results show a clear advantage of using the hierarchy over solving each task independently.
translated by 谷歌翻译
我们研究了随机线性匪徒(LB)中的两个模型选择设置。在我们将其称为特征选择的第一个设置中,LB问题的预期奖励是$ M $特征映射(模型)中至少一个的线性跨度。在第二个设置中,LB问题的奖励参数由$ \ MATHBB r ^ d $中表示(可能)重叠球的$ M $模型任意选择。但是,该代理只能访问错过模型,即球的中心和半径的估计。我们将此设置称为参数选择。对于每个设置,我们开发和分析一种基于从匪徒减少到全信息问题的算法。这允许我们获得遗憾的界限(最多超过$ \ sqrt {\ log m} $ factor)而不是已知真实模型的情况。我们参数选择算法的遗憾也以模型不确定性对数进行缩放。最后,我们经验展现了使用合成和现实世界实验的算法的有效性。
translated by 谷歌翻译
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.
translated by 谷歌翻译
我们考虑激励探索:一种多臂匪徒的版本,其中武器的选择由自私者控制,而算法只能发布建议。该算法控制信息流,信息不对称可以激励代理探索。先前的工作达到了最佳的遗憾率,直到乘法因素,这些因素根据贝叶斯先验而变得很大,并在武器数量上成倍规模扩展。采样每只手臂的一个更基本的问题一旦遇到了类似的因素。我们专注于激励措施的价格:出于激励兼容的目的,绩效的损失,广泛解释为。我们证明,如果用足够多的数据点初始化,则标准的匪徒汤普森采样是激励兼容的。因此,当收集这些数据点时,由于激励措施的绩效损失仅限于初始回合。这个问题主要降低到样本复杂性的问题:需要多少个回合?我们解决了这个问题,提供了匹配的上限和下限,并在各种推论中实例化。通常,最佳样品复杂性在“信念强度”中的武器数量和指数中是多项式。
translated by 谷歌翻译
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.
translated by 谷歌翻译
汤普森抽样(TS)吸引了对强盗区域的兴趣。它在20世纪30年代介绍,但近年来尚未经过理论上证明。其在组合多武装强盗(CMAB)设置中的所有分析都需要精确的Oracle来提供任何输入的最佳解决方案。然而,这种Oracle通常是不可行的,因为许多组合优化问题是NP - 硬,并且只有近似oracles可用。一个例子(王和陈,2018)已经表明TS的失败来学习近似Oracle。但是,此Oracle罕见,仅用于特定问题实例。它仍然是一个开放的问题,无论TS的收敛分析是否可以扩展到CMAB中的精确oracle。在本文中,我们在贪婪的Oracle下研究了这个问题,这是一个常见的(近似)Oracle,具有理论上的保证来解决许多(离线)组合优化问题。我们提供了一个问题依赖性遗憾的遗憾下限为$ \ omega(\ log t / delta ^ 2)$,以量化Ts的硬度来解决贪婪的甲骨文的CMAB问题,其中$ T $是时间范围和$ Delta $是一些奖励差距。我们还提供几乎匹配的遗憾上限。这些是TS解决CMAB与常见近似甲骨文的第一个理论结果,并打破TS无法使用近似神谕的误解。
translated by 谷歌翻译
我们研究汤普森采样(TS)算法的遗憾,指数为家庭土匪,其中奖励分配来自一个一维指数式家庭,该家庭涵盖了许多常见的奖励分布,包括伯努利,高斯,伽玛,伽玛,指数等。我们建议汤普森采样算法,称为expts,它使用新颖的采样分布来避免估计最佳臂。我们为expts提供了严格的遗憾分析,同时产生有限的遗憾和渐近遗憾。特别是,对于带指数级家庭奖励的$ k $臂匪徒,expts of horizo​​n $ t $ sub-ucb(对于有限的时间遗憾的是问题依赖的有限时间标准) $ \ sqrt {\ log k} $,并且对于指数家庭奖励,渐近最佳。此外,我们通过在Expts中使用的采样分配外添加一个贪婪的剥削步骤,提出$^+$,以避免过度估计亚最佳武器。 expts $^+$是随时随地的强盗算法,可用于指数级的家庭奖励分布同时实现最小值和渐近最优性。我们的证明技术在概念上很简单,可以轻松地应用于用特定奖励分布分析标准的汤普森抽样。
translated by 谷歌翻译
在预测功能(假设)中获得可靠的自适应置信度集是顺序决策任务的核心挑战,例如土匪和基于模型的强化学习。这些置信度集合通常依赖于对假设空间的先前假设,例如,繁殖核Hilbert Space(RKHS)的已知核。手动设计此类内核是容易发生的,错误指定可能导致性能差或不安全。在这项工作中,我们建议从离线数据(meta-kel)中进行元学习核。对于未知核是已知碱基核的组合的情况,我们基于结构化的稀疏性开发估计量。在温和的条件下,我们保证我们的估计RKHS会产生有效的置信度集,随着越来越多的离线数据的量,它变得与鉴于真正未知内核的置信度一样紧。我们展示了我们关于内核化强盗问题(又称贝叶斯优化)的方法,我们在其中建立了遗憾的界限,与鉴于真正的内核的人竞争。我们还经验评估方法对贝叶斯优化任务的有效性。
translated by 谷歌翻译
在本说明书中,我们介绍了众所周知的椭圆形潜在的引理的一般版本,这是一种广泛使用的技术在分析顺序学习和决策问题中的算法中。我们考虑一个随机线性匪徒设置,其中决策者在一组给定的行动中顺序选择,观察他们的嘈杂奖励,并旨在通过决策地平线最大化她的累积预期奖励。椭圆潜力引理是一种用于量化奖励功能参数的不确定性的关键工具,但它需要噪声和现有的分布成为高斯。我们的一般椭圆潜力引理放松了这种高斯要求,这是一种非常非琐碎的延伸,原因如上所述;与高斯案例不同,对后部分布的协方差矩阵没有闭合形式解决方案,协方差矩阵不是动作的确定性函数,并且协方差矩阵对于SEMIDEFINITE不等式而不是降低。虽然这一结果具有广泛的兴趣,但我们展示了它的应用,以证明具有在随机线性匪徒中的众所周知的汤普森采样算法的改进的贝叶斯遗憾,其中具有先前和噪声分布的改变动作集。这界限最多是常量的最佳状态。
translated by 谷歌翻译
本文研究了在因果图形模型中设计最佳干预措施序列的问题,以最大程度地减少对事后最佳干预的累积后悔。自然,这是一个因果匪徒问题。重点是线性结构方程模型(SEM)和软干预措施的因果匪徒。假定该图的结构是已知的,并且具有$ n $节点。每个节点都假定使用两种线性机制,一种软干预和一种观察性,产生了$ 2^n $可能的干预措施。现有的因果匪徒算法假设,至少完全指定了奖励节点父母的介入分布。但是,有$ 2^n $这样的分布(一个与每个干预措施相对应),即使在中等尺寸的图中也变得越来越高。本文分配了知道这些分布的假设。提出了两种算法,用于常见者(基于UCB)和贝叶斯(基于汤普森采样)的设置。这些算法的关键思想是避免直接估计$ 2^n $奖励分布,而是估算完全指定SEMS($ n $线性)的参数,并使用它们来计算奖励。在这两种算法中,在噪声和参数空间的有界假设下,累积遗憾的是$ \ tilde {\ cal o}(((2d)^l l \ sqrt {t})$,其中$ d $是图的最高度和$ l $是其最长因果路径的长度。
translated by 谷歌翻译
我们探索了一个新的强盗实验模型,其中潜在的非组织序列会影响武器的性能。上下文 - 统一算法可能会混淆,而那些执行正确的推理面部信息延迟的算法。我们的主要见解是,我们称之为Deconfounst Thompson采样的算法在适应性和健壮性之间取得了微妙的平衡。它的适应性在易于固定实例中带来了最佳效率,但是在硬性非平稳性方面显示出令人惊讶的弹性,这会导致其他自适应算法失败。
translated by 谷歌翻译
信息指导的采样(IDS)最近证明了其作为数据效率增强学习算法的潜力。但是,目前尚不清楚当可用上下文信息时,要优化的信息比的正确形式是什么。我们通过两个上下文强盗问题研究IDS设计:具有图形反馈和稀疏线性上下文匪徒的上下文强盗。我们证明了上下文ID比条件ID的优势,并强调考虑上下文分布的重要性。主要信息是,智能代理人应该在有条件的ID可能是近视的情况下对未来看不见的环境有益的行动进行更多的投资。我们进一步提出了基于Actor-Critic的上下文ID的计算效率版本,并在神经网络上下文的强盗上进行经验评估。
translated by 谷歌翻译
我们介绍了一个多臂强盗模型,其中奖励是多个随机变量的总和,每个动作只会改变其中的分布。每次动作之后,代理都会观察所有变量的实现。该模型是由营销活动和推荐系统激励的,在该系统中,变量代表单个客户的结果,例如点击。我们提出了UCB风格的算法,以估计基线上的动作的提升。我们研究了问题的多种变体,包括何时未知基线和受影响的变量,并证明所有这些变量均具有sublrinear后悔界限。我们还提供了较低的界限,以证明我们的建模假设的必要性是合理的。关于合成和现实世界数据集的实验显示了估计不使用这种结构的策略的振奋方法的好处。
translated by 谷歌翻译
在线学习算法广泛用于网络上的搜索和内容优化,必须平衡探索和开发,可能牺牲当前用户的经验,以获得将来会导致未来更好决策的信息。虽然在最坏的情况下,与贪婪算法相比,显式探索具有许多缺点,其通过选择当前看起来最佳的动作始终“利用”。我们在数据中固有的多样性的情况下提出了明确的探索不必要。我们在最近的一系列工作中进行了线性上下围匪盗模型中贪婪算法的平滑分析。我们提高了先前的结果,表明,只要多样性条件保持,贪婪的方法几乎符合任何其他算法的最佳可能性贝叶斯遗憾率,并且这种遗憾是最多的$ \ tilde o(t ^ {1/ 3})$。
translated by 谷歌翻译
假设发行版是高斯通常促进别侵害的计算。我们考虑一个旨在实现与具有高斯的先前分配和高斯似然函数的强盗环境获得低信息比的代理,但是在应用于伯努利强盗时研究代理的性能。当代理商与Bernoulli强盗互动时,我们建立了贝叶斯遗憾的增加,相对于对高斯匪徒的信息定理束缚。如果高斯的现有分配和似然函数足够弥散,则随着时间的平方根,这种增加的增加,因此每次时间增长都会增加消失。我们的结果正式化了所谓的贝叶斯代理在漫反射错过分布的差异时所谓的贝叶斯代理人仍然有效。
translated by 谷歌翻译
具有低维结构的随机高维匪徒问题可用于不同的应用程序,例如在线广告和药物发现。在这项工作中,我们为此类问题提出了一种简单的统一算法,并为我们算法的遗憾上限提供了一个一般分析框架。我们表明,在一些温和的统一假设下,我们的算法可以应用于不同的高维匪徒问题。我们的框架利用低维结构来指导问题中的参数估计,因此我们的算法在套索匪徒中达到了可比的遗憾界限,以及低级别矩阵匪徒的新颖界限,组稀疏矩阵强盗和IN组中一个新问题:多代理拉索强盗。
translated by 谷歌翻译
我们在存在对抗性腐败的情况下研究线性上下文的强盗问题,在场,每回合的奖励都被对手损坏,腐败级别(即,地平线上的腐败总数)为$ 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 $)实现了近乎最理想的遗憾。
translated by 谷歌翻译
我们为随机线性匪徒问题提出了一种新的基于自举的在线算法。关键的想法是采用残留的自举勘探,在该探索中,代理商通过重新采样平均奖励估算的残差来估算下一步奖励。我们的算法,随机线性匪徒(\ texttt {linreboot})的残留bootstrap探索,从其重新采样分布中估算了线性奖励,并以最高的奖励估计拉动了手臂。特别是,我们为理论框架做出了一个理论框架,以使基于自举的探索机制在随机线性匪徒问题中脱颖而出。关键见解是,Bootstrap探索的强度基于在线学习模型和残差的重新采样分布之间的乐观情绪。这样的观察使我们能够证明所提出的\ texttt {linreboot}确保了高概率$ \ tilde {o}(d \ sqrt {n})$ sub-linear在温和条件下的遗憾。我们的实验支持\ texttt {重新启动}原理在线性匪徒问题的各种公式中的简易概括性,并显示了\ texttt {linreboot}的显着计算效率。
translated by 谷歌翻译
We improve the theoretical analysis and empirical performance of algorithms for the stochastic multi-armed bandit problem and the linear stochastic multi-armed bandit problem. In particular, we show that a simple modification of Auer's UCB algorithm achieves with high probability constant regret. More importantly, we modify and, consequently, improve the analysis of the algorithm for the for linear stochastic bandit problem studied by Auer ( 2002), Dani et al. (2008), Rusmevichientong and Tsitsiklis (2010), Li et al. (2010). Our modification improves the regret bound by a logarithmic factor, though experiments show a vast improvement. In both cases, the improvement stems from the construction of smaller confidence sets. For their construction we use a novel tail inequality for vector-valued martingales.
translated by 谷歌翻译