  This work establishes a novel link between the problem of PAC-learning
high-dimensional graphical models and the task of (efficient) counting and
sampling of graph structures, using an online learning framework.
  We observe that if we apply the exponentially weighted average (EWA) or
randomized weighted majority (RWM) forecasters on a sequence of samples from a
distribution P using the log loss function, the average regret incurred by the
forecaster's predictions can be used to bound the expected KL divergence
between P and the predictions. Known regret bounds for EWA and RWM then yield
new sample complexity bounds for learning Bayes nets. Moreover, these
algorithms can be made computationally efficient for several interesting
classes of Bayes nets. Specifically, we give a new sample-optimal and
polynomial time learning algorithm with respect to trees of unknown structure
and the first polynomial sample and time algorithm for learning with respect to
Bayes nets over a given chordal skeleton.
