我们研究在线动态定价的问题，具有两种类型的公平限制：“程序公平性”，要求拟议的价格在不同群体之间的预期等同于期望，而“实质性公平”要求公认的价格要求公认的价格在预期中保持平等在不同的群体中。同时进行程序和实质性公平的政策称为“双重公平”。我们表明，双重公平的政策必须是随机的，才能获得比将相同价格分配给不同群体的最佳琐碎政策更高的收入。在两组设置中，我们为达到$ \ tilde {o}（\ sqrt {t}）$遗憾的两组定价问题提供了在线学习算法，零过程不公平和$ \ tilde {o}（\ sqrt {t}）$对$ t $回合学习的实质性不公平。我们还证明了两个下限，表明这些结果是遗憾和不公平性的，这两者在理论上都是最佳的，直到迭代的对数因素。据我们所知，这是第一个学会定价的动态定价算法，同时满足了两个公平的约束。

价格歧视，这是指为不同客户群体的不同价格进行规定的策略，已广泛用于在线零售。虽然它有助于提高在线零售商的收入，但它可能会对公平产生严重关切，甚至违反了监管和法律。本文研究了公平限制下动态歧视性定价的问题。特别是，我们考虑一个有限的销售长度$ T $的单一产品，为一组客户提供两组客户。每组客户都有其未知的需求功能，需要学习。对于每个销售期间，卖方确定每组的价格并观察其购买行为。虽然现有文学主要侧重于最大化收入，但在动态定价文学中确保不同客户的公平尚未完全探索。在这项工作中，我们采用了（Cohen等人）的公平概念。对于价格公平性，我们在遗憾方面提出了最佳的动态定价政策，从而强制执行严格的价格公平制约。与标准$ \ sqrt {t} $ - 在线学习中的遗憾遗憾，我们表明我们案例中的最佳遗憾是$ \ tilde {\ theta}（t ^ {4/5}）$。我们进一步将算法扩展到更普遍的公平概念，包括作为一个特例的需求公平。为了处理这一普通类，我们提出了一个柔和的公平约束，并开发了实现$ \ tilde {o}（t ^ {4/5}）$后悔的动态定价政策。

我们考虑具有未知实用程序参数的多项式logit模型（MNL）下的动态分类优化问题。本文研究的主要问题是$ \ varepsilon $ - 污染模型下的模型错误指定，该模型是强大统计和机器学习中的基本模型。特别是，在整个长度$ t $的销售范围内，我们假设客户根据$（1- \ varepsilon）$ - 时间段的$（1- \ varepsilon）的基础多项式logit选择模型进行购买，并进行任意购买取而代之的是在剩余的$ \ varepsilon $ - 分数中的决策。在此模型中，我们通过主动淘汰策略制定了新的强大在线分类优化政策。我们对遗憾建立上限和下界，并表明当分类能力恒定时，我们的政策是$ t $的最佳对数因素。分类能力具有恒定的上限。我们进一步制定了一种完全自适应策略，该政策不需要任何先验知识，即污染参数$ \ varepsilon $。如果存在最佳和亚最佳产品之间存在的亚临时差距，我们还建立了依赖差距的对数遗憾上限和已知的 - $ \ VAREPSILON $和UNKNOWER-$ \ \ VAREPSILON $案例。我们的仿真研究表明，我们的政策表现优于基于上置信度范围（UCB）和汤普森采样的现有政策。

在线学习通常需要探索以最大程度地提高长期奖励，但这是以短期“遗憾”为代价的。我们研究如何在多个小组之间分担这种探索成本。例如，在临床试验环境中，分配了亚最佳治疗的患者有效地产生了勘探成本。当患者根据种族或年龄与自然群体相关联时，自然要问任何单一群体所承担的探索成本是否“公平”。如此有动力，我们介绍了“分组”的强盗模型。我们利用公理讨价还价的理论，尤其是纳什议价解决方案，以形式化可能构成跨群体勘探成本的公平分裂的方式。一方面，我们表明，任何遗憾的政策都引起了最不公平的结果：此类政策将在可能的情况下传递最“处于弱势”的群体。更具建设性的方式，我们得出了最佳公平且同时享受“公平价格”的政策。我们通过对华法林剂量的上下文匪徒进行案例研究来说明我们的算法框架的相对优点，我们关注多个种族和年龄段的探索成本。

在古典语境匪徒问题中，在每轮$ 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运行一流拍卖的广告交换中模拟了我们的真实拍卖数据的算法，并表明了它们优于传统的上下文强盗算法。

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

本文在动态定价的背景下调查预先存在的离线数据对在线学习的影响。我们在$ t $期间的销售地平线上研究单一产品动态定价问题。每个时段的需求由产品价格根据具有未知参数的线性需求模型确定。我们假设在销售地平线开始之前，卖方已经有一些预先存在的离线数据。离线数据集包含$ N $示例，其中每个标准是由历史价格和相关的需求观察组成的输入输出对。卖方希望利用预先存在的离线数据和顺序在线数据来最大限度地减少在线学习过程的遗憾。我们的特征在于在线学习过程的最佳遗憾的脱机数据的大小，位置和分散的联合效果。具体而言，离线数据的大小，位置和色散由历史样本数量为$ n $，平均历史价格与最佳价格$ \ delta $之间的距离以及历史价格的标准差价Sigma $分别。我们表明最佳遗憾是$ \ widetilde \ theta \ left（\ sqrt {t} \ wedge \ frac {t} {（n \ wedge t）\ delta ^ 2 + n \ sigma ^ 2} \右）$，基于“面对不确定性”原则的“乐观主义”的学习算法，其遗憾是最佳的对数因子。我们的结果揭示了对脱机数据的大小的最佳遗憾率的惊人变换，我们称之为阶段转型。此外，我们的结果表明，离线数据的位置和分散也对最佳遗憾具有内在效果，我们通过逆平面法量化了这种效果。

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

我们研究了批量线性上下文匪徒的最佳批量遗憾权衡。对于任何批次数$ M $，操作次数$ k $，时间范围$ t $和维度$ d $，我们提供了一种算法，并证明了其遗憾的保证，这是由于技术原因，具有两阶段表达作为时间的时间$ t $ grose。我们还证明了一个令人奇迹的定理，令人惊讶地显示了在问题参数的“问题参数”中的两相遗憾（最高〜对数因子）的最优性，因此建立了确切的批量后悔权衡。与最近的工作\ citep {ruan2020linear}相比，这表明$ m = o（\ log \ log t）$批次实现无需批处理限制的渐近最佳遗憾的渐近最佳遗憾，我们的算法更简单，更易于实际实现。此外，我们的算法实现了所有$ t \ geq d $的最佳遗憾，而\ citep {ruan2020linear}要求$ t $大于$ d $的不切实际的大多项式。沿着我们的分析，我们还证明了一种新的矩阵集中不平等，依赖于他们的动态上限，这是我们的知识，这是其文学中的第一个和独立兴趣。

以下序列出售了许多产品：首先显示焦点产品，如果购买客户，则显示一种或多种辅助产品以供购买。一个突出的例子是出售航空票，首先显示航班，并在选择时出售了许多辅助机构，例如机舱或袋装选项，座位选择，保险等。该公司必须决定销售格式 - 是按串联捆绑或作为捆绑销售的形式出售 - 以及如何分别或捆绑产品为焦点和辅助产品定价。由于仅在购买焦点产品后才考虑辅助性，因此公司选择的销售策略会在产品之间创建信息和学习依赖性：例如，仅提供一套捆绑包将排除学习客户对焦点的估值和辅助产品。在本文中，我们在以下情况下研究了这种焦点和辅助项目组合的学习策略：（a）纯捆绑向所有客户捆绑，（b）个性化机制，在其中，根据客户的某些观察到的功能，这两种产品都会呈现并以捆绑包或顺序定价，（c）最初（适用于所有客户），并在地平线期间永久切换（如果更有利可图）。我们为所有三种情况设计定价和决策算法，遗憾的是由$ o（d \ sqrt {t} \ log t）$限制，以及第三种情况的最佳切换时间。

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.

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

在社会背景下的算法决策，例如零售定价，贷款管理，在线平台上的建议等，通常涉及为了学习而进行决策的实验，这导致受这些决策影响的人们的不公平感知。因此，有必要在此类决策过程中嵌入适当的公平概念。本文的目的是通过一种新颖的元观念来强调公平的时间概念与在线决策之间的丰富界面，以确保在决策时确保公平。考虑到静态决策的一些任意比较公平概念（例如，学生最多应支付一般成人价格的90％），如果满足上述公平概念，则相应的在线决策算法在决策时满足公平性对于任何与过去的决定相比，收到决定的任何实体。我们表明，这一基本要求引入了在线决策中的新方法论挑战。我们说明了在随机凸优化的背景下，在比较公平的约束下，在随机凸优化的背景下解决这些挑战所必需的新方法，该方法取决于实体所收到的决策，这取决于过去每个人都收到的决策。该论文展示了由于时间公平的关注而引起的在线决策中的新研究机会。

在本文中，我们研究了汤普森采样（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优于现有基准。

节流是当今在线广告市场中最受欢迎的预算控制方法之一。当一个受预算受限的广告商雇用节流功能时，她可以在广告平台建议出价后选择是否参加拍卖。本文重点介绍了从理论观点重复的第二价格拍卖中的动态预算节流过程。潜在问题的一个重要特征是，广告商不知道进入市场时竞争最高的出价。为了模拟消除这种不确定性的困难，我们考虑了两种不同的信息结构。广告商可以通过全信息反馈获得每轮竞争最高的投标。同时，通过部分信息反馈，广告商只能在她参加的拍卖中获得最高竞争的出价。我们提出了OGD-CB算法，该算法涉及在线广告查询面临的同时分配学习和收入优化。在这两种情况下，我们都证明该算法保证了$ O（\ sqrt {t \ log t}）$遗憾，概率$ 1- o（1/t）$相对于流体自适应节流基准。通过证明$ \ omega（\ sqrt {t}）$的下限在最小的后悔中，即使是最佳的最佳选择，我们就建立了算法的近乎最佳性。最后，我们将节流的最佳流体最佳与起搏相提并论，这是另一种广泛采用的预算控制方法。这些基准的数值关系使我们对不同的在线算法进行预算管理的比较有了进一步的见解。

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

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

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

我们在$ gi/gi/1 $队列中研究动态定价和容量大小问题，服务提供商的目标是获得最佳服务费$ p $ $ p $和服务能力$ \ mu $，以最大程度地提高累积预期利润（服务收入减去人员配备成本和延迟罚款）。由于排队动力学的复杂性质，这种问题没有分析解决方案，因此以前的研究经常诉诸于交通重型分析，在这种分析中，到达率和服务率都发送到无穷大。在这项工作中，我们提出了一个旨在解决此问题的在线学习框架，该框架不需要系统的规模增加。我们的框架在队列（GOLIQ）中被称为基于梯度的在线学习。 Goliq将时间范围组织为连续的操作周期，并开出了有效的程序，以使用先前的周期中收集的数据在每个周期中获得改进的定价和人员配备策略。此处的数据包括客户到达的数量，等待时间和服务器的繁忙时间。这种方法的创造力在于其在线性质，这使服务提供商可以通过与环境进行互动来更好。 GOLIQ的有效性得到了（i）理论结果的证实，包括算法收敛和遗憾分析（对数遗憾的束缚），以及（ii）通过模拟实验进行工程确认，以了解各种代表性$ GI/GI/GI/1 $ $ $ $ $。

我们研究了一个决策者的问题，即当面对参与决策（随机）取决于他们获得的激励措施的代理商时，发现最佳的货币激励计划。我们的重点是限制的政策，以实现两种公平性能，这些公平性能排除了不同的代理人平均经历不同治疗的结果。我们将问题提出为高维的随机优化问题，并通过使用紧密相关的确定性变体进行研究。我们表明，该确定性变体的最佳静态解决方案对于在公平性约束下的动态问题均非最佳。尽管解决最佳静态解决方案会引起非凸优化问题，但我们发现了一个结构性属性，该属性使我们能够设计一种可拖延，快速的启发式策略。利益相关者保留的传统计划忽略公平限制；确实，这些目的是利用差异化激励与系统的反复互动。我们的工作（i）表明，即使没有明确的歧视，动态政策也可能通过改变系统的类型组成而无意间歧视不同类型的药物，并且（ii）提出了渐近的最佳政策，以避免这种歧视性局势。