我们研究了一个知情的发件人面临的重复信息设计问题，该问题试图影响自我利益接收者的行为。我们考虑接收器面临顺序决策（SDM）问题的设置。在每回合中，发件人都会观察SDM问题中随机事件的实现。这会面临如何逐步向接收者披露此类信息以说服他们遵循（理想的）行动建议的挑战。我们研究了发件人不知道随机事件概率的情况，因此，他们必须在说服接收器的同时逐渐学习它们。首先，我们提供了发件人说服力信息结构集的非平凡的多面近似。这对于设计有效的学习算法至关重要。接下来，我们证明了一个负面的结果：没有学习算法可以说服力。因此，我们通过关注算法来保证接收者对以下建议的遗憾会增长，从而放松说服力。在全反馈设置（发件人观察所有随机事件实现）中，我们提供了一种算法，其中包括$ \ tilde {o}（\ sqrt {t}）$ sexter和接收者遗憾。取而代之的是，在Bandit反馈设置中 - 发件人仅观察SDM问题中实际发生的随机事件的实现 - 我们设计了一种算法，给定一个$ \ alpha \ in [1/2，1] $作为输入，确保$ \ tilde {o}（{t^\ alpha}）$和$ \ tilde {o}（t^{\ max \ arpha，1- \ frac {\ frac {\ alpha} }）$遗憾，分别为发件人和接收器。该结果补充了下限，表明这种遗憾的权衡本质上是紧张的。

在正常游戏中，简单，未耦合的无regret动态与相关的平衡是多代理系统理论的著名结果。具体而言，已知20多年来，当所有玩家都试图在重复的正常游戏中最大程度地减少其内部遗憾时，游戏的经验频率会收敛于正常形式相关的平衡。广泛的形式（即树形）游戏通过对顺序和同时移动以及私人信息进行建模，从而推广正常形式的游戏。由于游戏中部分信息的顺序性质和存在，因此广泛的形式相关性具有与正常形式的属性明显不同，而正常形式的相关性仍然是开放的研究方向。已经提出了广泛的形式相关平衡（EFCE）作为自然的广泛形式与正常形式相关平衡。但是，目前尚不清楚EFCE是否是由于未耦合的代理动力学而出现的。在本文中，我们给出了第一个未耦合的无regret动态，该动态将$ n $ n $ - 玩家的General-sum大型游戏收敛于EFCE，并带有完美的回忆。首先，我们在广泛的游戏中介绍了触发遗憾的概念，这扩展了正常游戏中的内部遗憾。当每个玩家的触发后悔低时，游戏的经验频率接近EFCE。然后，我们给出有效的无触发式算法。我们的算法在每个决策点在每个决策点上都会从每个决策点构建播放器的全球策略，从而将触发遗憾分解为本地子问题。

在随着时间变化的组合环境中的在线决策激励，我们研究了将离线算法转换为其在线对应物的问题。我们专注于使用贪婪算法对局部错误的贪婪算法进行恒定因子近似的离线组合问题。对于此类问题，我们提供了一个通用框架，该框架可有效地将稳健的贪婪算法转换为使用Blackwell的易近算法。我们证明，在完整信息设置下，由此产生的在线算法具有$ O（\ sqrt {t}）$（近似）遗憾。我们进一步介绍了Blackwell易接近性的强盗扩展，我们称之为Bandit Blackwell的可接近性。我们利用这一概念将贪婪的稳健离线算法转变为匪（t^{2/3}）$（近似）$（近似）的遗憾。展示了我们框架的灵活性，我们将脱机之间的转换应用于收入管理，市场设计和在线优化的几个问题，包括在线平台中的产品排名优化，拍卖中的储备价格优化以及supperular tossodular最大化。 。我们还将还原扩展到连续优化的类似贪婪的一阶方法，例如用于最大化连续强的DR单调下调功能，这些功能受到凸约束的约束。我们表明，当应用于这些应用程序时，我们的转型会导致新的后悔界限或改善当前已知界限。我们通过为我们的两个应用进行数值模拟来补充我们的理论研究，在这两种应用中，我们都观察到，转换的数值性能在实际情况下优于理论保证。

我们研究在线学习问题，决策者必须采取一系列决策，但要受到$ M $长期约束。决策者的目标是最大程度地提高其总奖励，同时达到小累积约束，在$ t $回合中违规。我们介绍了此一般类问题的第一个最佳世界类型算法，在根据未知随机模型选择奖励和约束的情况下，无需保证，在它们的情况下，在他们的情况下选择了奖励和约束。在每个回合中由对手选择。我们的算法是关于满足长期约束的最佳固定策略的第一个在对抗环境中提供保证的算法。特别是，它保证了$ \ rho/（1+ \ rho）$的最佳奖励和额定性遗憾，其中$ \ rho $是与严格可行的解决方案有关的可行性参数。我们的框架采用传统的遗憾最小化器作为黑盒组件。因此，通过使用适当的遗憾最小化器进行实例化，它可以处理全反馈以及强盗反馈设置。此外，它允许决策者通过非凸奖励和约束无缝处理场景。我们展示了如何在重复拍卖的预算管理机制的背景下应用我们的框架，以保证不包装的长期约束（例如，ROI约束）。

Imperfect information games (IIG) are games in which each player only partially observes the current game state. We study how to learn $\epsilon$-optimal strategies in a zero-sum IIG through self-play with trajectory feedback. We give a problem-independent lower bound $\mathcal{O}(H(A_{\mathcal{X}}+B_{\mathcal{Y}})/\epsilon^2)$ on the required number of realizations to learn these strategies with high probability, where $H$ is the length of the game, $A_{\mathcal{X}}$ and $B_{\mathcal{Y}}$ are the total number of actions for the two players. We also propose two Follow the Regularize leader (FTRL) algorithms for this setting: Balanced-FTRL which matches this lower bound, but requires the knowledge of the information set structure beforehand to define the regularization; and Adaptive-FTRL which needs $\mathcal{O}(H^2(A_{\mathcal{X}}+B_{\mathcal{Y}})/\epsilon^2)$ plays without this requirement by progressively adapting the regularization to the observations.

我们考虑激励探索：一种多臂匪徒的版本，其中武器的选择由自私者控制，而算法只能发布建议。该算法控制信息流，信息不对称可以激励代理探索。先前的工作达到了最佳的遗憾率，直到乘法因素，这些因素根据贝叶斯先验而变得很大，并在武器数量上成倍规模扩展。采样每只手臂的一个更基本的问题一旦遇到了类似的因素。我们专注于激励措施的价格：出于激励兼容的目的，绩效的损失，广泛解释为。我们证明，如果用足够多的数据点初始化，则标准的匪徒汤普森采样是激励兼容的。因此，当收集这些数据点时，由于激励措施的绩效损失仅限于初始回合。这个问题主要降低到样本复杂性的问题：需要多少个回合？我们解决了这个问题，提供了匹配的上限和下限，并在各种推论中实例化。通常，最佳样品复杂性在“信念强度”中的武器数量和指数中是多项式。

当他们更喜欢$ \ texit {exploit} $时，您如何激励自我兴趣的代理到$ \ texit {探索} $？我们考虑复杂的探索问题，其中每个代理面临相同（但未知）MDP。与传统的加固学习配方相比，代理商控制了政策的选择，而算法只能发出建议。然而，该算法控制信息流，并且可以通过信息不对称激励代理探索。我们设计一种算法，探讨MDP中的所有可达状态。我们达到了类似于先前研究的静态，无国籍探索问题中激励探索的保证担保。据我们所知，这是第一个考虑在有状态，强化学习环境中设计的工作。

我们考虑带有背包的土匪（从此以后，BWK），这是一种在供应/预算限制下的多臂土匪的通用模型。特别是，强盗算法需要解决一个众所周知的背包问题：找到最佳的物品包装到有限尺寸的背包中。 BWK问题是众多激励示例的普遍概括，范围从动态定价到重复拍卖，再到动态AD分配，再到网络路由和调度。尽管BWK的先前工作集中在随机版本上，但我们开创了可以在对手身上选择结果的另一个极端。与随机版本和“经典”对抗土匪相比，这是一个更加困难的问题，因为遗憾的最小化不再可行。相反，目的是最大程度地减少竞争比率：基准奖励与算法奖励的比率。我们设计了一种具有竞争比O（log t）的算法，相对于动作的最佳固定分布，其中T是时间范围；我们还证明了一个匹配的下限。关键的概念贡献是对问题的随机版本的新观点。我们为随机版本提出了一种新的算法，该算法是基于重复游戏中遗憾最小化的框架，并且与先前的工作相比，它具有更简单的分析。然后，我们为对抗版本分析此算法，并将其用作求解后者的子例程。

我们介绍了一个多臂强盗模型，其中奖励是多个随机变量的总和，每个动作只会改变其中的分布。每次动作之后，代理都会观察所有变量的实现。该模型是由营销活动和推荐系统激励的，在该系统中，变量代表单个客户的结果，例如点击。我们提出了UCB风格的算法，以估计基线上的动作的提升。我们研究了问题的多种变体，包括何时未知基线和受影响的变量，并证明所有这些变量均具有sublrinear后悔界限。我们还提供了较低的界限，以证明我们的建模假设的必要性是合理的。关于合成和现实世界数据集的实验显示了估计不使用这种结构的策略的振奋方法的好处。

我们通过审查反馈重复进行一定的第一价格拍卖来研究在线学习，在每次拍卖结束时，出价者只观察获胜的出价，学会了适应性地出价，以最大程度地提高她的累积回报。为了实现这一目标，投标人面临着一个具有挑战性的困境：如果她赢得了竞标 - 获得正收益的唯一方法 - 然后她无法观察其他竞标者的最高竞标，我们认为我们认为这是从中汲取的。一个未知的分布。尽管这一困境让人联想到上下文强盗中的探索探索折衷权，但现有的UCB或汤普森采样算法无法直接解决。在本文中，通过利用第一价格拍卖的结构属性，我们开发了第一个实现$ o（\ sqrt {t} \ log^{2.5} t）$ hearry bund的第一个学习算法（\ sqrt {t} \ log^{2.5} t），这是最小值的最低$ $ \ log $因素，当投标人的私人价值随机生成时。我们这样做是通过在一系列问题上提供算法，称为部分有序的上下文匪徒，该算法将图形反馈跨动作，跨环境跨上下文进行结合，以及在上下文中的部分顺序。我们通过表现出一个奇怪的分离来确定该框架的优势和劣势，即在随机环境下几乎可以独立于动作/背景规模的遗憾，但是在对抗性环境下是不可能的。尽管这一通用框架有限制，但我们进一步利用了第一价格拍卖的结构，并开发了一种学习算法，该算法在存在对手生成的私有价值的情况下，在存在的情况下可以有效地运行样本（并有效地计算）。我们建立了一个$ o（\ sqrt {t} \ log^3 t）$遗憾，以此为此算法，因此提供了对第一价格拍卖的最佳学习保证的完整表征。

通过在线实验和违规学习中的实践需求激励，我们研究了安全最佳设计的问题，在那里我们开发了一个有效探索的数据记录策略，同时通过基线生产政策实现竞争奖励。我们首先展示，也许令人惊讶的是，尽管安全，但尽管安全，但尽管是安全的，但仍有统一探索的常见做法是最大化信息增益的次优。然后，我们提出了一个安全的最佳日志记录策略，因为没有有关操作的预期奖励的侧面信息。我们通过考虑侧面信息来改进这种设计，并且还通过线性奖励模型扩展到大量动作的方法。我们分析了我们的数据记录策略如何影响禁止策略学习中的错误。最后，我们通过进行广泛的实验，经验验证了我们设计的好处。

我们使用访问离线最小二乘回归甲骨文的访问权限，在最低可及性假设下为随机上下文MDP提供了遗憾的最小化算法。我们分析了三个不同的设置：在该动力学的位置，动力学是未知的，但独立于上下文和最具挑战性的设置，而动力学是未知和上下文依赖性的。对于后者，我们的算法获得$ \ tilde {o} \ left（\ max \ {h，{1}/{p_ {min}}} \} \} t \ log（\ max \ {| \ mathcal {f} |，| \ mathcal {p} | \}/\ delta）} \ right）$ hearse bunder bund bund bund bund bund bund bund bunging bund bunger，probinality $ 1- \ delta $，其中$ \ mathcal { P} $和$ \ Mathcal {f} $是用于分别近似动态和奖励的有限且可实现的函数类，$ p_ {min} $是最小可及性参数，$ s $是一组状态，$ a $ a $一组动作，$ h $ the Horizo​​n和$ t $情节数。据我们所知，我们的方法是使用一般函数近似的上下文MDP的第一种乐观方法（即，在没有其他有关功能类别的知识的情况下，例如线性等）。此外，我们还提供$ \ omega的下限即使在已知的动态情况下，也会产生预期的遗憾。

我们介绍了一种普遍的策略，可实现有效的多目标勘探。它依赖于adagoal，一种基于简单约束优化问题的新的目标选择方案，其自适应地针对目标状态，这既不是太困难也不是根据代理目前的知识达到的。我们展示了Adagoal如何用于解决学习$ \ epsilon $ -optimal的目标条件的政策，以便在$ L $ S_0 $ S_0 $奖励中获得的每一个目标状态，以便在$ S_0 $中获取。免费马尔可夫决策过程。在标准的表格外壳中，我们的算法需要$ \ tilde {o}（l ^ 3 s a \ epsilon ^ { - 2}）$探索步骤，这几乎很少最佳。我们还容易在线性混合Markov决策过程中实例化Adagoal，其产生具有线性函数近似的第一目标导向的PAC保证。除了强大的理论保证之外，迈克纳队以现有方法的高级别算法结构为锚定，为目标条件的深度加固学习。

在本文中，我们建立了高效且取消耦合的学习动力学，因此，当由所有玩家在多人游戏中使用Perfect-Recall Inderfect Interfect Inderfection Formfortation Gartensive Games时，每个玩家的\ emph {触发后悔}会成长为$ o（\ log t t t t t t ）$ $ t $重复播放。这比$ o（t^{1/4}）$的先前最著名的触发regret键呈指数改进，并解决了Bai等人最近的一个开放问题。 （2022）。作为直接的结果，我们保证以$ \ frac {\ log log t} {t} $的接近速率以接近{粗相关的平衡}融合。基于先前的工作，我们的构造核心是关于从\ emph {polyenmial genter}衍生的固定点的更一般的结果，这是我们为\ emph {（粗）触发偏差函数建立的属性}。此外，我们的构造利用了凸壳的精制\ textit {遗憾电路}，与先验保证不同 - 保留了Syrgkanis等人引入的\ emph {rvu属性}。 （NIPS，2015年）；这种观察对基于CFR型遗憾的分解，在学习动态下建立近乎最佳的遗憾具有独立的兴趣。

在古典语境匪徒问题中，在每轮$ t $，学习者观察一些上下文$ c $，选择一些动作$ i $执行，并收到一些奖励$ r_ {i，t}（c）$。我们考虑此问题的变体除了接收奖励$ r_ {i，t}（c）$之外，学习者还要学习其他一些上下文$的$ r_ {i，t}（c'）$的值C'$ in设置$ \ mathcal {o} _i（c）$;即，通过在不同的上下文下执行该行动来实现的奖励\ mathcal {o} _i（c）$。这种变体出现在若干战略设置中，例如学习如何在非真实的重复拍卖中出价，最热衷于随着许多平台转换为运行的第一价格拍卖。我们将此问题称为交叉学习的上下文匪徒问题。古典上下围匪徒问题的最佳算法达到$ \ tilde {o}（\ sqrt {ckt}）$遗憾针对所有固定策略，其中$ c $是上下文的数量，$ k $的行动数量和$ $次数。我们设计并分析了交叉学习的上下文匪徒问题的新算法，并表明他们的遗憾更好地依赖上下文的数量。在选择动作时学习所有上下文的奖励的完整交叉学习下，即设置$ \ mathcal {o} _i（c）$包含所有上下文，我们显示我们的算法实现后悔$ \ tilde {o}（ \ sqrt {kt}）$，删除$ c $的依赖。对于任何其他情况，即在部分交叉学习下，$ | \ mathcal {o} _i（c）| <c $ for $（i，c）$，遗憾界限取决于如何设置$ \ mathcal o_i（c）$影响上下文之间的交叉学习的程度。我们从Ad Exchange运行一流拍卖的广告交换中模拟了我们的真实拍卖数据的算法，并表明了它们优于传统的上下文强盗算法。

我们探索了一个新的强盗实验模型，其中潜在的非组织序列会影响武器的性能。上下文 - 统一算法可能会混淆，而那些执行正确的推理面部信息延迟的算法。我们的主要见解是，我们称之为Deconfounst Thompson采样的算法在适应性和健壮性之间取得了微妙的平衡。它的适应性在易于固定实例中带来了最佳效率，但是在硬性非平稳性方面显示出令人惊讶的弹性，这会导致其他自适应算法失败。

\ emph {ex ante}相关性正在成为\ emph {顺序对抗团队游戏}的主流方法，其中一组球员在零和游戏中面对另一支球队。众所周知，团队成员的不对称信息同时使平衡计算\ textsf {apx} - hard和团队的策略在游戏树上不可直接表示。后一个问题阻止采用成功的2个玩家零和游戏的成功工具，例如，\ emph {e.g。}，抽象，无regret学习和子游戏求解。这项工作表明，我们可以通过弥合顺序对抗团队游戏和2次玩家游戏之间的差距来恢复这种弱点。特别是，我们提出了一种新的，合适的游戏表示形式，我们称之为\ emph {Team-Public-information}，其中团队被代表为单个协调员，他只知道整个团队的共同信息，并向每个成员开出一个行动对于任何可能的私人状态。最终的表示形式是高度\ emph {可解释}，是一棵2播放器树，在设计抽象时，团队的策略具有直接解释和更具表现力的行为，并且具有更高的表现力。此外，我们证明了代表性的回报等效性，并提供了直接从广泛形式开始的技术，从而在没有信息损失的情况下产生了更紧凑的表示形式。最后，我们在应用于标准测试床上的技术时对技术进行了实验评估，并将它们的性能与当前的最新状态进行了比较。

大部分强化学习理论都建立在计算上难以实施的甲板上。专门用于在部分可观察到的马尔可夫决策过程（POMDP）中学习近乎最佳的政策，现有算法要么需要对模型动态（例如确定性过渡）做出强有力的假设，要么假设访问甲骨文作为解决艰难的计划或估算问题的访问子例程。在这项工作中，我们在合理的假设下开发了第一个用于POMDP的无Oracle学习算法。具体而言，我们给出了一种用于在“可观察” pomdps中学习的准化性时间端到端算法，其中可观察性是一个假设，即对国家而言，分离良好的分布诱导了分离良好的分布分布而不是观察。我们的技术规定了在不确定性下使用乐观原则来促进探索的更传统的方法，而是在构建策略涵盖的情况下提供了一种新颖的barycentric跨度应用。

我们考虑随机多武装强盗（MAB）问题，延迟影响了行动。在我们的环境中，过去采取的行动在随后的未来影响了ARM奖励。在现实世界中，行动的这种延迟影响是普遍的。例如，为某个社会群体中的人员偿还贷款的能力可能历史上历史上批准贷款申请的频率频率。如果银行将贷款申请拒绝拒绝弱势群体，则可以创建反馈循环，进一步损害该群体中获取贷款的机会。在本文中，我们制定了在多武装匪徒的背景下的行动延迟和长期影响。由于在学习期间，我们将强盗设置概括为对这种“偏置”的依赖性进行编码。目标是随着时间的推移最大化收集的公用事业，同时考虑到历史行动延迟影响所产生的动态。我们提出了一种算法，实现了$ \ tilde {\ mathcal {o}}的遗憾，并显示$ \ omega（kt ^ {2/3}）$的匹配遗憾下限，其中$ k $是武器数量，$ t $是学习地平线。我们的结果通过添加技术来补充强盗文献，以处理具有长期影响的行动，并对设计公平算法有影响。

我们研究了在随机最短路径（SSP）设置中的学习问题，其中代理试图最小化在达到目标状态之前累积的预期成本。我们设计了一种新型基于模型的算法EB-SSP，仔细地偏离了经验转变，并通过探索奖励来赋予经验成本，以诱导乐观的SSP问题，其相关价值迭代方案被保证收敛。我们证明了EB-SSP实现了Minimax后悔率$ \ tilde {o}（b _ {\ star} \ sqrt {sak}）$，其中$ k $是剧集的数量，$ s $是状态的数量， $ a $是行动的数量，而B _ {\ star} $绑定了从任何状态的最佳策略的预期累积成本，从而缩小了下限的差距。有趣的是，EB-SSP在没有参数的同时获得此结果，即，它不需要任何先前的$ B _ {\ star} $的知识，也不需要$ t _ {\ star} $，它绑定了预期的时间 ​​- 任何州的最佳政策的目标。此外，我们说明了各种情况（例如，当$ t _ {\ star} $的订单准确估计可用时，遗憾地仅包含对$ t _ {\ star} $的对数依赖性，因此产生超出有限范围MDP设置的第一个（几乎）的免地相会遗憾。