在本文中，我们研究了众所周知的团队导演问题，其中一批机器人通过访问地点收集奖励。通常，假设奖励是机器人已知的;但是，在环境监测或场景重建的应用中，奖励通常是主观的，并指定它们是具有挑战性的。我们提出了一个框架来通过向它们呈现替代解决方案来学习用户的未知偏好，并且用户在所提出的替代解决方案上提供排名。我们考虑了用户的两种情况：1）确定替代解决方案的最佳排名的确定性用户，以及根据未知概率分布提供最佳排名的噪声用户。对于确定性用户，我们提出了一个框架，以最大限度地减少与最佳解决方案的最大偏差的界限，即后悔。我们适应捕获嘈杂用户的方法，并最大限度地减少预期的遗憾。最后，我们展示了学习用户偏好的重要性以及在广泛的实验结果中使用真实的世界数据集进行环境监测问题的大量实验结果的性能。
translated by 谷歌翻译
多路径定向问题询问机器人团队的路径最大化收集的总奖励，同时满足路径长度上的预算约束。这个问题模拟了许多多机器人路由任务，例如探索未知的环境和环境监控信息。在本文中，我们专注于如何使机器人团队在对抗环境中运行时对故障的强大。我们介绍了强大的多路径定向事问题（RMOP），在那里我们寻求最糟糕的案例保证，反对能够在大多数$ \ Alpha $机器人处攻击的对手。我们考虑两个问题的两个版本：RMOP离线和RMOP在线。在离线版本中，当机器人执行其计划时，没有通信或重新扫描，我们的主要贡献是一种具有界限近似保证的一般近似方案，其取决于$ \ alpha $和单个机器人导向的近似因子。特别是，我们表明该算法在成本函数是模块化时产生（i）恒因子近似; （ii）在成本函数是子模具时，$ \ log $因子近似; （iii）当成本函数是子模块时的恒因子近似，但是允许机器人通过有界金额超过其路径预算。在在线版本中，RMOP被建模为双人顺序游戏，并基于蒙特卡罗树搜索（MCT），以后退地平线方式自适应解决。除了理论分析之外，我们还对海洋监测和隧道信息收集应用进行仿真研究，以证明我们的方法的功效。
translated by 谷歌翻译
本文介绍了相关的弧定向问题（CAOP），其中的任务是找到机器人团队的路线，以最大程度地收集与环境中功能相关的奖励的收集。这些功能可以是一维或环境中的点，并且可以具有空间相关性，即访问环境中的功能可能会提供与相关功能相关的奖励的一部分。机器人在环境环境时会产生成本，并且路线的总成本受到资源限制（例如电池寿命或操作时间）的限制。由于环境通常很大，我们允许多个仓库在机器人必须启动和结束路线的地方。 CAOP概括了相关的定向问题（COP），其中奖励仅与点特征相关联以及ARC定向启动问题（AOP），其中奖励与无空间相关。我们制定了一个混合整数二次程序（MIQP），该程序正式化了问题并提供最佳的解决方案。但是，这个问题是NP-HARD，因此我们开发了一种有效的贪婪的建设性算法。我们用两种不同的应用说明了问题：甲烷气体泄漏检测和道路网络覆盖范围的信息路径计划。
translated by 谷歌翻译
对于许多强化学习（RL）应用程序，指定奖励是困难的。本文考虑了一个RL设置，其中代理仅通过查询可以询问可以的专家来获取有关奖励的信息，例如，评估单个状态或通过轨迹提供二进制偏好。从如此昂贵的反馈中，我们的目标是学习奖励的模型，允许标准RL算法实现高预期的回报，尽可能少的专家查询。为此，我们提出了信息定向奖励学习（IDRL），它使用奖励的贝叶斯模型，然后选择要最大化信息增益的查询，这些查询是有关合理的最佳策略之间的返回差异的差异。与针对特定类型查询设计的先前主动奖励学习方法相比，IDRL自然地适应不同的查询类型。此外，它通过将焦点转移降低奖励近似误差来实现类似或更好的性能，从而降低奖励近似误差，以改善奖励模型引起的策略。我们支持我们的调查结果，在多个环境中进行广泛的评估，并具有不同的查询类型。
translated by 谷歌翻译
真实世界的机器人任务需要复杂的奖励功能。当我们定义机器人需要解决的问题时，我们假装设计人员确切地指定了这种复杂的奖励，并且从那时起，它被设置为石头。然而，在实践中，奖励设计是一个迭代过程：设计师选择奖励，最终遇到奖励激励错误行为的“边缘案例”环境，修改奖励和重复。重新思考机器人问题是什么意思，正式占奖励设计的这种迭代性质？我们建议机器人不采取特定的奖励，而是对其进行不确定性，并占未来设计迭代作为未来的证据。我们贡献了辅助奖励设计方法，通过预测和影响未来的证据来加速设计过程：而不是让设计师最终遇到故障情况并修改奖励，该方法在开发阶段主动地将设计者暴露于这种环境。我们在简化的自主驾驶任务中测试此方法，并发现它通过提出当前奖励的“边缘案例”的环境，更快地提高汽车的行为。
translated by 谷歌翻译
2021-08-16
奖励学习是人机互动中的一个基本问题，使机器人与他们的人类用户想要的对齐方式。已经提出了许多基于偏好的学习算法和主动查询技术作为解决此问题的解决方案。在本文中，我们展示了一种用于基于活跃的偏好的奖励学习算法的库，使研究人员和从业者能够尝试现有技术，并轻松开发自己的各种模块的自己的算法。APREL可在HTTPS://github.com/stanford-iliad/aprel提供。
translated by 谷歌翻译
我们研究了设计AI代理商的问题，该代理可以学习有效地与潜在的次优伴侣有效合作，同时无法访问联合奖励功能。这个问题被建模为合作焦论双代理马尔可夫决策过程。我们假设仅在游戏的Stackelberg制定中的两个代理中的第一个控制，其中第二代理正在作用，以便在鉴于第一代理的政策给出预期的效用。第一个代理人应该如何尽快学习联合奖励功能，因此联合政策尽可能接近最佳？在本文中，我们分析了如何在这一交互式的两个代理方案中获得对奖励函数的知识。我们展示当学习代理的策略对转换函数有显着影响时，可以有效地学习奖励功能。
translated by 谷歌翻译
人类可以利用身体互动来教机器人武器。这种物理互动取决于任务，用户以及机器人到目前为止所学的内容。最先进的方法专注于从单一模态学习，或者假设机器人具有有关人类预期任务的先前信息，从而结合了多个互动类型。相比之下，在本文中，我们介绍了一种算法形式主义，该算法从演示，更正和偏好中学习。我们的方法对人类想要教机器人的任务没有任何假设。取而代之的是，我们通过将人类的输入与附近的替代方案进行比较，从头开始学习奖励模型。我们首先得出损失函数，该功能训练奖励模型的合奏，以匹配人类的示范，更正和偏好。反馈的类型和顺序取决于人类老师：我们使机器人能够被动地或积极地收集此反馈。然后，我们应用受约束的优化将我们学习的奖励转换为所需的机器人轨迹。通过模拟和用户研究，我们证明，与现有基线相比，我们提出的方法更准确地从人体互动中学习了操纵任务，尤其是当机器人面临新的或意外的目标时。我们的用户研究视频可在以下网址获得：https：//youtu.be/fsujstyveku
translated by 谷歌翻译
我们研究了通过中等数量的成对比较查询引发决策者偏好的问题，以使它们成为特定问题的高质量推荐。我们受到高赌场域中的应用程序的推动，例如选择分配稀缺资源的政策以满足基本需求（例如，用于移植或住房的肾脏，因为那些经历无家可归者），其中需要由（部分）提出引出的偏好。我们在基于偏好的偏好中模拟不确定性，并调查两个设置：a）脱机偏出设置，其中所有查询都是一次，b）在线诱因设置，其中按时间顺序选择查询。我们提出了这些问题的强大优化制剂，这些问题集成了偏好诱导和推荐阶段，其目的是最大化最坏情况的效用或最小化最坏情况的后悔，并研究其复杂性。对于离线案例，在活动偏好诱导与决策信息发现的两个半阶段的稳健优化问题的形式中，我们提供了我们通过列解决的混合二进制线性程序的形式提供了等效的重构。 -Constraint生成。对于在线设置，主动偏好学习采用多级强大优化问题的形式与决策依赖的信息发现，我们提出了一种保守的解决方案方法。合成数据的数值研究表明，我们的方法在最坏情况级别，后悔和效用方面从文献中倾斜最先进的方法。我们展示了我们的方法论如何用于协助无家可归的服务机构选择分配不同类型的稀缺住房资源的政策，以遇到无家可归者。
translated by 谷歌翻译
当从人类行为中推断出奖励功能（无论是演示，比较，物理校正或电子停靠点）时，它已证明对人类进行建模作为做出嘈杂的理性选择，并具有“合理性系数”，以捕获多少噪声或熵我们希望看到人类的行为。无论人类反馈的类型或质量如何，许多现有作品都选择修复此系数。但是，在某些情况下，进行演示可能要比回答比较查询要困难得多。在这种情况下，我们应该期望在示范中看到比比较中更多的噪音或次级临时性，并且应该相应地解释反馈。在这项工作中，我们提倡，将每种反馈类型的实际数据中的理性系数扎根，而不是假设默认值，对奖励学习具有重大的积极影响。我们在模拟反馈以及用户研究的实验中测试了这一点。我们发现，从单一反馈类型中学习时，高估人类理性可能会对奖励准确性和遗憾产生可怕的影响。此外，我们发现合理性层面会影响每种反馈类型的信息性：令人惊讶的是，示威并不总是最有用的信息 - 当人类的行为非常卑鄙时，即使在合理性水平相同的情况下，比较实际上就变得更加有用。 。此外，当机器人确定要要求的反馈类型时，它可以通过准确建模每种类型的理性水平来获得很大的优势。最终，我们的结果强调了关注假定理性级别的重要性，不仅是在从单个反馈类型中学习时，尤其是当代理商从多种反馈类型中学习时，尤其是在学习时。
translated by 谷歌翻译
在许多环境监测方案中，采样机器人需要同时探索环境和利用有限时间利用感兴趣的特征。我们介绍了一个名为Pareto Monte Carlo树搜索的多目标信息规划方法，该方法允许机器人处理潜在的竞争目标，例如勘探与剥削。该方法基于环境状态的知识（估计）为机器人产生了优化的决策解决方案，从而更好地适应环境动态。我们在关键树节点选择步骤提供算法分析，并显示选择子最优节点的次数是对数界限的，并且搜索结果以多项式率收敛到最佳选择。
translated by 谷歌翻译
这项工作解决了逆线优化，其中目标是推断线性程序的未知成本向量。具体地，我们考虑数据驱动的设置，其中可用数据是对应于线性程序的不同实例的最佳解决方案的嘈杂的观察。我们介绍了一个问题的新配方，与其他现有方法相比，允许恢复较少的限制性和一般更适当的可允许成本估算。可以表明，该逆优化问题产生有限数量的解决方案，并且我们开发了一个精确的两相算法来确定所有此类解决方案。此外，我们提出了一种有效的分解算法来解决问题的大实例。该算法自然地扩展到在线学习环境，可以用于提供成本估计的快速更新，因为新数据随着时间的推移可用。对于在线设置，我们进一步开发了一种有效的自适应采样策略，指导下一个样本的选择。所提出的方法的功效在涉及两种应用，客户偏好学习和生产计划的成本估算的计算实验中进行了证明。结果表明计算和采样努力的显着减少。
translated by 谷歌翻译
推荐系统在市场中使用时发挥了双重作用：它们可以帮助用户从大型游泳池中选择最需要的物品，并有助于将有限数量的物品分配给最想要它们的用户。尽管在许多现实世界中的推荐设置中，能力限制的流行率普遍存在，但缺乏将它们纳入这些系统设计的原则性方式。在此激励的情况下，我们提出了一个交互式框架，系统提供商可以通过机会主义探索分配来提高向用户的建议质量，从而最大程度地利用用户奖励并使用适当的定价机制尊重容量约束。我们将问题建模为低排名组合的多臂匪徒问题的实例，并在手臂上进行了选择约束。我们采用一种集成方法，使用协作过滤，组合匪徒和最佳资源分配中的技术，以提供一种算法，可证明可以实现次线性遗憾，即$ \ tilde {\ mathcal {\ sqrt {o}}（\ sqrt {\ sqrt {n+m（n+m）{n+m（n+m） ）rt}）$ in $ t $ rounds，用于$ n $用户，$ m $项目和排名$ r $ ney奖励矩阵的问题。关于合成和现实世界数据的实证研究也证明了我们方法的有效性和性能。
translated by 谷歌翻译
在随着时间变化的组合环境中的在线决策激励，我们研究了将离线算法转换为其在线对应物的问题。我们专注于使用贪婪算法对局部错误的贪婪算法进行恒定因子近似的离线组合问题。对于此类问题，我们提供了一个通用框架，该框架可有效地将稳健的贪婪算法转换为使用Blackwell的易近算法。我们证明，在完整信息设置下，由此产生的在线算法具有$ O（\ sqrt {t}）$（近似）遗憾。我们进一步介绍了Blackwell易接近性的强盗扩展，我们称之为Bandit Blackwell的可接近性。我们利用这一概念将贪婪的稳健离线算法转变为匪（t^{2/3}）$（近似）$（近似）的遗憾。展示了我们框架的灵活性，我们将脱机之间的转换应用于收入管理，市场设计和在线优化的几个问题，包括在线平台中的产品排名优化，拍卖中的储备价格优化以及supperular tossodular最大化。 。我们还将还原扩展到连续优化的类似贪婪的一阶方法，例如用于最大化连续强的DR单调下调功能，这些功能受到凸约束的约束。我们表明，当应用于这些应用程序时，我们的转型会导致新的后悔界限或改善当前已知界限。我们通过为我们的两个应用进行数值模拟来补充我们的理论研究，在这两种应用中，我们都观察到，转换的数值性能在实际情况下优于理论保证。
translated by 谷歌翻译
我们研究了基于消费者的决策积极学习非参数选择模型的问题。我们提出一个负面结果，表明这种选择模型可能无法识别。为了克服可识别性问题，我们介绍了选择模型的有向无环图（DAG）表示，从某种意义上说，该模型可以捕获有关选择模型的更多信息，从而可以从理论上识别信息。然后，我们考虑在主动学习环境中学习与此DAG表示的近似的问题。我们设计了一种有效的主动学习算法，以估计非参数选择模型的DAG表示，该模型在多项式时间内运行时，当随机均匀地绘制频繁排名。我们的算法通过主动和反复提供各种项目并观察所选项目来了解最受欢迎的频繁偏好项目的分布。我们表明，与相应的非活动学习估计算法相比，我们的算法可以更好地恢复有关消费者偏好的合成和公开数据集的一组频繁偏好。这证明了我们的算法和主动学习方法的价值。
translated by 谷歌翻译
2022-06-10
我们以已知的奖励和未知的约束来研究顺序决策，这是由约束代表昂贵评估人类偏好（例如安全舒适的驾驶行为）的情况所激发的。我们将互动学习这些约束作为新的线性匪徒问题的挑战正式化，我们称之为约束的线性最佳臂识别。为了解决这个问题，我们提出了自适应约束学习（ACOL）算法。我们为约束线性最佳臂识别提供了一个依赖实例的下限，并表明Acol的样品复杂性与最坏情况下的下限匹配。在平均情况下，ACOL的样品复杂性结合仍然比简单方法的边界更紧密。在合成实验中，ACOL与Oracle溶液相同，并且表现优于一系列基准。作为应用程序，我们考虑学习限制，以代表驾驶模拟中的人类偏好。对于此应用，ACOL比替代方案要高得多。此外，我们发现学习偏好作为约束对驾驶场景的变化比直接编码奖励函数中的偏好更强大。
translated by 谷歌翻译
我们考虑在线学习设置中的顺序稀疏子集选择的问题。假设集合$ [n] $由$ n $不同的元素组成。在$ t^{\ text {th}} $ round上，单调奖励函数$ f_t：2^{[n]} \ to \ m athbb {r} _+，$，为每个子集分配非阴性奖励$ [n]，向学习者透露$。学习者在奖励功能$ f_t $ for $ f_t $之前（k \ leq n）$选择（也许是随机的）子集$ s_t \ subseteq [n] $ of $ k $元素。由于选择的结果，学习者在$ t^{\ text {th}} $ round上获得了$ f_t（s_t）$的奖励。学习者的目标是设计一项在线子集选择策略，以最大程度地提高其在给定时间范围内产生的预期累积奖励。在这方面，我们提出了一种称为Score的在线学习策略（带有Core的子集选择），以解决大量奖励功能的问题。拟议的分数策略基于$ \ alpha $ core的新概念，这是对合作游戏理论文献中核心概念的概括。我们根据一个名为$ \ alpha $的遗憾的新绩效指标为分数政策建立学习保证。在这个新的指标中，与在线政策相比，离线基准的功能适当增强。我们给出了几个说明性示例，以表明可以使用分数策略有效地学习包括子模型在内的广泛奖励功能。我们还概述了如何在半伴奏反馈模型下使用得分策略，并以许多开放问题的总结结束了论文。
translated by 谷歌翻译
嘈杂的传感，不完美的控制和环境变化是许多现实世界机器人任务的定义特征。部分可观察到的马尔可夫决策过程（POMDP）提供了一个原则上的数学框架，用于建模和解决不确定性下的机器人决策和控制任务。在过去的十年中，它看到了许多成功的应用程序，涵盖了本地化和导航，搜索和跟踪，自动驾驶，多机器人系统，操纵和人类机器人交互。这项调查旨在弥合POMDP模型的开发与算法之间的差距，以及针对另一端的不同机器人决策任务的应用。它分析了这些任务的特征，并将它们与POMDP框架的数学和算法属性联系起来，以进行有效的建模和解决方案。对于从业者来说，调查提供了一些关键任务特征，以决定何时以及如何成功地将POMDP应用于机器人任务。对于POMDP算法设计师，该调查为将POMDP应用于机器人系统的独特挑战提供了新的见解，并指出了有希望的新方向进行进一步研究。
translated by 谷歌翻译
Pearl's Do Colculus是一种完整的公理方法，可以从观察数据中学习可识别的因果效应。如果无法识别这种效果，则有必要在系统中执行经常昂贵的干预措施以学习因果效应。在这项工作中，我们考虑了设计干预措施以最低成本来确定所需效果的问题。首先，我们证明了这个问题是NP-HARD，随后提出了一种可以找到最佳解或对数因子近似值的算法。这是通过在我们的问题和最小击球设置问题之间建立联系来完成的。此外，我们提出了几种多项式启发式算法来解决问题的计算复杂性。尽管这些算法可能会偶然发现亚最佳解决方案，但我们的模拟表明它们在随机图上产生了小的遗憾。
translated by 谷歌翻译
在本文中，我们证明了一种用于优化耦合子模块的最大化问题的制定，具有可提供的次优先界限。在机器人应用中，很常见的是优化问题彼此耦合，因此不能独立解决。具体地，如果第一问题的结果影响第二问题的解决方案，我们考虑两个问题耦合的两个问题，该第二问题在更长的时间尺度上运行。例如，在环境监测的激励问题中，我们对多机器人任务分配有可能影响环境动态，从而影响未来监测的质量，在这里建模为多机器人间歇部署问题。通过该激励例证明了解决这种类型耦合问题的一般理论方法。具体地，我们提出了一种求解由Matroid约束模拟的子模具集功能建模的耦合问题的方法。提出了一种解决这类问题的贪婪算法，以及子最优的保证。最后，通过蒙特卡罗模拟示出了实用的最优比率，以证明所提出的算法可以高效率产生近最佳解决方案。
translated by 谷歌翻译