在因果强盗问题中，动作集包括关于因果图的变量的干预。最近几位研究人员研究了这种强盗问题并指出了他们的实际应用。然而，所有现有的作品都依赖于限制性和不切实际的假设，即学习者将全面了解因果图结构前期。在本文中，我们在不知道因果图的情况下开发新的因果强盗算法。我们的算法适用于因果树，因果林和一般的因果图。我们的算法的遗憾保证大大提高了温和条件下标准多臂强盗（MAB）算法的遗传。最后，我们证明了我们的温和条件是必要的：如果没有它们，不能比标准MAB算法更好。

本文研究了在因果图形模型中设计最佳干预措施序列的问题，以最大程度地减少对事后最佳干预的累积后悔。自然，这是一个因果匪徒问题。重点是线性结构方程模型（SEM）和软干预措施的因果匪徒。假定该图的结构是已知的，并且具有$ n $节点。每个节点都假定使用两种线性机制，一种软干预和一种观察性，产生了$ 2^n $可能的干预措施。现有的因果匪徒算法假设，至少完全指定了奖励节点父母的介入分布。但是，有$ 2^n $这样的分布（一个与每个干预措施相对应），即使在中等尺寸的图中也变得越来越高。本文分配了知道这些分布的假设。提出了两种算法，用于常见者（基于UCB）和贝叶斯（基于汤普森采样）的设置。这些算法的关键思想是避免直接估计$ 2^n $奖励分布，而是估算完全指定SEMS（$ n $线性）的参数，并使用它们来计算奖励。在这两种算法中，在噪声和参数空间的有界假设下，累积遗憾的是$ \ tilde {\ cal o}（（（2d）^l l \ sqrt {t}）$，其中$ d $是图的最高度和$ l $是其最长因果路径的长度。

因果匪徒问题将因果推断与多军匪徒集成在一起。因果匪徒的纯粹探索是以下在线学习任务：给定一个因果关系分布未知的因果图，在每一轮中，我们可以选择干预一个变量或不进行干预，并观察所有随机变量的随机结果，并与所有随机变量进行观察使用尽可能少的回合的目标，我们可以输出一种干预措施，该干预措施在奖励变量$ y $上具有至少$ 1- \ delta $，其中$ \ delta $是一个最佳（或几乎是最好的）预期结果给定信心水平。我们在三种类型的因果模型，包括平行图，具有少量后门父母的常规图和二进制通用线性模型的三种类型的因果模型上提供了第一个完全依赖GAP的完全自适应纯探索算法。我们的算法改善了先前的因果匪徒算法，这些算法并非自适应奖励差距，也没有先前的自适应纯探索算法，它们不利用因果匪徒的特殊特征。

我们研究了与从介入数据中恢复因果图有关的两个问题：（i）$ \ textIt {verification} $，其中的任务是检查声称的因果图是否正确，并且（ii）$ \ textit {search} $，任务是恢复正确的因果图。对于这两者，我们都希望最大程度地减少执行的干预措施的数量。对于第一个问题，我们给出了一组最小尺寸的原子干预措施的表征，这些干预措施是必要且足以检查所要求的因果图的正确性。我们的表征使用$ \ textit {coving edges} $的概念，这使我们能够获得简单的证据，并且很容易理解早期结果。我们还将结果推广到有限尺寸干预措施和节点依赖性干预成本的设置。对于上述所有设置，我们提供了第一种已知的可验证算法，用于有效地计算（接近）一般图上的最佳验证集。对于第二个问题，我们给出了一种基于图形分离器的简单自适应算法，该算法会产生一个原子干预集，该集合在使用$ \ MATHCAL {O}（\ log n）$ times $ times所需的$所需干预措施时，该算法完全围绕任何必需图表。 \ textIt {verify} $（验证大小）$ n $顶点上的基础dag。相对于验证大小而言，此近似值是紧密的，因为$ \ textit {any} $搜索算法的最差情况是$ \ omega（\ log n）$的最差情况。使用有限的大小干预措施，每个大小$ \ leq k $，我们的算法给出了$ \ mathcal {o}（\ log n \ cdot \ log \ log \ log k）$ factor actialation。我们的结果是第一种已知的算法，该算法对一般未加权图和有界尺寸干预的验证尺寸提供了非平凡的近似保证。

在组合因果土匪（CCB）中，学习代理在每轮中最多选择$ k $变量进行干预，从观察到的变量中收集反馈，目的是最大程度地减少对目标变量$ y $的预期遗憾。与所有有关因果匪徒的研究不同，CCB需要处理指数较大的动作空间。我们在因果模型的简洁参数表示的二元广义线性模型（BGLM）的背景下进行研究。我们根据最大似然估计方法提出了Markovian BGLMS（即没有隐藏变量）的算法BGLM-OFU，并证明它可以实现$ O（\ sqrt {t} \ log t）$遗憾，其中$ t $是$ t $时间范围。对于具有隐藏变量的线性模型的特殊情况，我们应用因果推理技术，例如DO-Calculus将原始模型转换为马尔可夫模型，然后证明我们的BGLM OFFU U算法和另一种基于线性回归的算法都用隐藏变量求解此类线性模型。我们的新颖性包括（a）考虑组合干预行动空间，（b）考虑一般因果模型，包括具有隐藏变量的因果模型，（c）整合和适应来自多种研究的技术，例如广义线性匪徒和在线影响最大化，以及（d）不依赖不现实的假设，例如在某些先前研究中使用的所有干预措施中了解父母的共同分配。

我们研究马尔可夫决策过程（MDP），其中状态对应于随机生成奖励的因果图。在这个设置中，学习者的目标是通过在每个州的变量上介绍，识别导致高奖励的原子干预措施。概括最近的因果强盗框架，目前的工作开发（简单）后悔最小化对两级因果MDP的保证，每个状态下并行因果图。我们提出了一种算法，实现了一个依赖于困境的实例。我们算法的一个关键特征是它利用凸优化来解决探索问题。我们识别我们遗憾保证基本紧张的课程，实验验证我们的理论结果。

因果结构学习是许多领域的关键问题。通过对感兴趣系统进行实验来学习因果结构。我们解决了设计一批实验的主要原因，每个实验中同时干预多个变量。虽然可能比常用的单变干预措施更具信息丰富，但选择这种干预措施是更具挑战性的，这是由于复合干预措施的双指数组合搜索空间。在本文中，我们开发有效的算法，以优化量化预算限制批次实验的信息性的不同目标函数。通过建立这些目标的新型子模具性质，我们为我们的算法提供近似保证。我们的算法经验上优于随机干预和算法，只能选择单变化干预。

We study experiment design for unique identification of the causal graph of a system where the graph may contain cycles. The presence of cycles in the structure introduces major challenges for experiment design as, unlike acyclic graphs, learning the skeleton of causal graphs with cycles may not be possible from merely the observational distribution. Furthermore, intervening on a variable in such graphs does not necessarily lead to orienting all the edges incident to it. In this paper, we propose an experiment design approach that can learn both cyclic and acyclic graphs and hence, unifies the task of experiment design for both types of graphs. We provide a lower bound on the number of experiments required to guarantee the unique identification of the causal graph in the worst case, showing that the proposed approach is order-optimal in terms of the number of experiments up to an additive logarithmic term. Moreover, we extend our result to the setting where the size of each experiment is bounded by a constant. For this case, we show that our approach is optimal in terms of the size of the largest experiment required for uniquely identifying the causal graph in the worst case.

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

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

因果匪是经典匪徒问题的变体，在该问题中，代理必须在顺序决策过程中识别最佳动作，其中动作的奖励分布显示由因果模型控制的非平凡依赖性结构。到目前为止，文献中针对此问题提出的方法取决于完整因果图的精确知识。我们制定了不再依赖先前因果知识的新因果匪徒。相反，他们利用基于分离集的估计量，我们可以使用简单的条件独立性测试或因果发现方法找到。我们证明，给定一个真正的分离集，用于离散的I.I.D.数据，该估计量是公正的，并且具有差异，该方差受样本平均值的上限。我们分别基于Thompson采样和UCB开发算法，分别用于离散和高斯模型，并显示了模拟数据以及来自现实世界中蛋白质信号数据的强盗图上的性能提高。

在原因指导的非循环图（DAG）的结构学习问题中出现的良好研究挑战是，使用观测数据，一个人只能将图形到“马尔可夫等价类”（MEC）。剩余的无向边缘必须使用干预率定向，这可以在应用中执行昂贵。因此，最小化了全面定向MEC所需的干预次数的问题已经得到了很多最近的关注，并且也是这项工作的重点。我们证明了两个主要结果。第一个是一种新的通用下限，在任何算法（无论是主动或被动）需要执行的原子干预次数，以便定向给定的MEC。我们的第二个结果表明，这一界限实际上是可以定位MEC的最小原子干预措施的两个大小的因素。我们的下限比以前已知的下限更好。我们的下限证明是基于CBSP订购的新概念，这是没有V-Surructure的DAG的拓扑排序，并满足某些特殊属性。此外，在综合图上使用模拟，并通过赋予特殊图家庭的示例，我们表明我们的界限往往明显更好。

Pearl's Do Colculus是一种完整的公理方法，可以从观察数据中学习可识别的因果效应。如果无法识别这种效果，则有必要在系统中执行经常昂贵的干预措施以学习因果效应。在这项工作中，我们考虑了设计干预措施以最低成本来确定所需效果的问题。首先，我们证明了这个问题是NP-HARD，随后提出了一种可以找到最佳解或对数因子近似值的算法。这是通过在我们的问题和最小击球设置问题之间建立联系来完成的。此外，我们提出了几种多项式启发式算法来解决问题的计算复杂性。尽管这些算法可能会偶然发现亚最佳解决方案，但我们的模拟表明它们在随机图上产生了小的遗憾。

In this review, we discuss approaches for learning causal structure from data, also called causal discovery. In particular, we focus on approaches for learning directed acyclic graphs (DAGs) and various generalizations which allow for some variables to be unobserved in the available data. We devote special attention to two fundamental combinatorial aspects of causal structure learning. First, we discuss the structure of the search space over causal graphs. Second, we discuss the structure of equivalence classes over causal graphs, i.e., sets of graphs which represent what can be learned from observational data alone, and how these equivalence classes can be refined by adding interventional data.

我们研究了因果结构学习的问题，没有关于功能关系和噪声的假设。我们开发DAG-Foci，这是一种基于\ Cite {Azadkia2019Simple}的焦点变量选择算法的计算快速算法。DAG-Foci不需要调整参数并输出父母和Markov边界的响应变量的响应变量。当底层图形是多料时，我们提供了我们程序的高维保证。此外，我们展示了DAG-Foci在计算生物学\ Cite {Sachs2005Causal}的真实数据上的适用性，并说明了我们对侵犯假设的方法的稳健性。

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

我们分析了在没有特定分布假设的常规设置中从观察数据的学习中学循环图形模型的复杂性。我们的方法是信息定理，并使用本地马尔可夫边界搜索程序，以便在基础图形模型中递归地构建祖先集。也许令人惊讶的是，我们表明，对于某些图形集合，一个简单的前向贪婪搜索算法（即没有向后修剪阶段）足以学习每个节点的马尔可夫边界。这显着提高了我们在节点的数量中显示的样本复杂性。然后应用这一点以在从文献中概括存在现有条件的新型标识性条件下学习整个图。作为独立利益的问题，我们建立了有限样本的保障，以解决从数据中恢复马尔可夫边界的问题。此外，我们将我们的结果应用于特殊情况的Polytrees，其中假设简化，并提供了多项识别的明确条件，并且在多项式时间中可以识别和可知。我们进一步说明了算法在仿真研究中易于实现的算法的性能。我们的方法是普遍的，用于无需分布假设的离散或连续分布，并且由于这种棚灯对有效地学习来自数据的定向图形模型结构所需的最小假设。

我们考虑代表代理模型的问题，该模型使用我们称之为CSTREES的阶段树模型的适当子类对离散数据编码离散数据的原因模型。我们表明，可以通过集合表达CSTREE编码的上下文专用信息。由于并非所有阶段树模型都承认此属性，CSTREES是一个子类，可提供特定于上下文的因果信息的透明，直观和紧凑的表示。我们证明了CSTREEES承认全球性马尔可夫属性，它产生了模型等价的图形标准，概括了Verma和珍珠的DAG模型。这些结果延伸到一般介入模型设置，使CSTREES第一族的上下文专用模型允许介入模型等价的特征。我们还为CSTREE的最大似然估计器提供了一种封闭式公式，并使用它来表示贝叶斯信息标准是该模型类的本地一致的分数函数。在模拟和实际数据上分析了CSTHEELE的性能，在那里我们看到与CSTREELE而不是一般上演树的建模不会导致预测精度的显着损失，同时提供了特定于上下文的因果信息的DAG表示。

在观察性研究中，经常遇到有关存在或缺乏因果边缘和路径的因果背景知识。由于背景知识而导致的马尔可夫等效dag的子类共享的指向边缘和链接可以由因果关系最大部分定向的无循环图（MPDAG）表示。在本文中，我们首先提供了因果MPDAG的声音和完整的图形表征，并提供了因果MPDAG的最小表示。然后，我们介绍了一种名为Direct Causal子句（DCC）的新颖表示，以统一形式表示所有类型的因果背景知识。使用DCC，我们研究因果背景知识的一致性和等效性，并表明任何因果背景知识集都可以等效地分解为因果MPDAG，以及最小的残留DCC。还提供了多项式时间算法，以检查一致性，等效性并找到分解的MPDAG和残留DCC。最后，有了因果背景知识，我们证明了一个足够且必要的条件来识别因果关系，并且出人意料地发现因果效应的可识别性仅取决于分解的MPDAG。我们还开发了局部IDA型算法，以估计无法识别效应的可能值。模拟表明因果背景知识可以显着提高因果影响的识别性。

在本文中，我们研究了组合半伴侣（CMAB），并专注于减少遗憾的批量$ k $的依赖性，其中$ k $是可以拉动或触发的武器总数每个回合。首先，对于用概率触发的臂（CMAB-T）设置CMAB，我们发现了一个新颖的（定向）触发概率和方差调制（TPVM）条件，可以替代各种应用程序的先前使用的平滑度条件，例如级联bandsistits bandits bandits。 ，在线网络探索和在线影响最大化。在这种新条件下，我们提出了一种具有方差感知置信区间的BCUCB-T算法，并进行遗憾分析，将$ O（k）$ actival降低到$ o（\ log k）$或$ o（\ log^2 k） ）$在遗憾中，大大改善了上述申请的后悔界限。其次，为了设置具有独立武器的非触发CMAB，我们提出了一种SESCB算法，该算法利用TPVM条件的非触发版本，并完全消除了对$ k $的依赖，以备受遗憾。作为有价值的副产品，本文使用的遗憾分析可以将几个现有结果提高到$ O（\ log K）$的一倍。最后，实验评估表明，与不同应用中的基准算法相比，我们的表现出色。