We study the problem of learning a Bayesian network (BN) of a set of
variables when structural side information about the system is available. It is
well known that learning the structure of a general BN is both computationally
and statistically challenging. However, often in many applications, side
information about the underlying structure can potentially reduce the learning
complexity. In this paper, we develop a recursive constraint-based algorithm
that efficiently incorporates such knowledge (i.e., side information) into the
learning process. In particular, we study two types of structural side
information about the underlying BN: (I) an upper bound on its clique number is
known, or (II) it is diamond-free. We provide theoretical guarantees for the
learning algorithms, including the worst-case number of tests required in each
scenario. As a consequence of our work, we show that bounded treewidth BNs can
be learned with polynomial complexity. Furthermore, we evaluate the performance
and the scalability of our algorithms in both synthetic and real-world
structures and show that they outperform the state-of-the-art structure
learning algorithms.

本研究开发了一种递归约束算法，能够高效地将结构性边缘信息引入学习贝叶斯网络 (BN) 的过程，并提供了该算法的理论保证，进一步表明有界树宽 BN 可以在不增加复杂度的情况下学习。

存在结构侧信息条件下的贝叶斯网络学习

Learning Bayesian Networks in the Presence of Structural Side  Information

In this paper we present a model for the hidden Markovian bandit problem with
linear rewards. As opposed to current work on Markovian bandits, we do not
assume that the state is known to the decision maker before making the
decision. Furthermore, we assume structural side information where the decision
maker knows in advance that there are two types of hidden states; one is common
to all arms and evolves according to a Markovian distribution, and the other is
unique to each arm and is distributed according to an i.i.d. process that is
unique to each arm. We present an algorithm and regret analysis to this
problem. Surprisingly, we can recover the hidden states and maintain
logarithmic regret in the case of a convex polytope action set. Furthermore, we
show that the structural side information leads to expected regret that does
not depend on the number of extreme points in the action space. Therefore, we
obtain practical solutions even in high dimensional problems.

本论文提出了一种针对具有线性奖励的隐藏马尔可夫赌博问题的模型，基于结构性侧面信息，能在凸多面体动作集的情况下恢复隐藏状态并保持对数遗憾。