Co-training for Policy Learning

Jialin Song 1 Ravi Lanka 2 Yisong Yue 1 Masahiro Ono 2

Abstract
We study the problem of learning sequential
decision-making policies in settings with multiple state-action representations. Such settings
naturally arise in many domains, such as planning (e.g., multiple integer programming formulations) and various combinatorial optimization
problems (e.g., those with both integer programming and graph-based formulations). Inspired by
the classical co-training framework for classification, we study the problem of co-training for policy learning. We present sufficient conditions under which learning from two views can improveupon learning from a single view alone. Motivated by these theoretical insights, we present
an algorithm for co-training for sequential decision making. Our framework is compatible withboth reinforcement learning and imitation learning. We validate the effectiveness of our approach on a challenging class of combinatorial
optimization problems: minimum vertex cover.

1. Introduction
A common wisdom in problem solving is that there is morethan one way to look at a problem. For sequential decision making problems, such as those in reinforcement
learning and imitation learning, one can often utilize multiple different state-action representations to characterize thesame problem. A canonical application example is learning
solvers for hard optimization problems such as combinatorial optimization (1; 2; 3; 4; 5; 6). It is well-known in theoperations research community that many combinatorial
optimization problems have multiple formulations. Prominent examples include the maximum cut problem where
one can describe with a quadratic integer problem as well
as a linear integer program (7; 8). Another example isthe travelling salesperson problem, which admits multiple
integer programming formulations (9; 10). One can also1

California Institute of Technology 2 Jet Propulsion Laboratory. Correspondence to: Jialin Song <jssong@caltech.edu>.
Real-world Sequential Decision Making workshop at ICML 2019.
Copyright 2019 by the author(s).

formulate many problems using a graph-based representation (see Figure 1). Beyond learning combinatorial optimization solvers, other examples with multiple state-action
representations include robotic applications with multiple
sensing modalities such as third-person view demonstrations (11) and multilingual machine translation (12).
In the context of policy learning, one natural questionis how different state-action formulations impact learning
and, more importantly, how learning can take advantage
of multiple formulations. The multiple formulation scenario is related to the co-training problem (13; 14), where
different feature representations of the same problem enable more effective learning compared with using only asingle representation (15; 16). While co-training has received much attention in classical tasks such as classification, little effort has been made on applying it to sequential
decision making problems. One immediate consequence
considering the sequential case is that some settings havecompletely separate state-action representations while others can share the action space.
In this paper, we propose CoPiEr (co-training for policy
learning), a framework for policy co-training that can incorporate both reinforcement learning and imitation learning as subroutines. Our approach is based on a novel theoretical result that integrates and extends results from general policy learning with demonstrations (17). To the bestof our knowledge, we are the first to formally extend theco-training framework to policy learning.
Our contributions can be summarized as:• We present a formal theoretical framework for policy
co-training. We provide a general theoretical characterization of policy improvement. This theoreticalcharacterization sheds light on a rigorous algorithm
design for policy learning that can appropriately exploit multiple state-action representations.
• We present CoPiEr (co-training for policy learning),
an algorithm for policy co-training that is based on thetheoretical analysis.
• We empirically evaluate on a challenging combinatorial optimization problems: minimum vertex cover.
We showcase the practicality of our approach bydemonstrating superior performance compared to a

Co-training for Policy Learning

1

max −

5
X

xi ,

i=1

subject to:25

x1 + x2 ≥ 1,x2 + x3 ≥ 1,x3 + x4 ≥ 1,x3 + x5 ≥ 1,

3

4

x4 + x5 ≥ 1,xi ∈ {0, 1}, ∀i ∈ {1, · · · , 5}

Figure 1. Two ways to encode minimum vertex cover (MVC)
problems. Left: policies learn to operate directly on the graphview to find the minimal cover set (18). Right: we express MVC
as an integer linear program, then polices learn to traverse theresulting combinatorial search space, i.e., learn to branch-andbound (1; 5).

wide range of strong learning-based benchmarks aswell as commercial solvers such as Gurobi.

2. Related Work
Co-training Our work is inspired by the classical cotraining framework for classification (13), which utilizes
two different feature representations, or views, to effectively use unlabeled data to improve the classification accuracy. Subsequent extensions of co-training includes coEM (19) and co-regularization (20). Co-training has been
widely used in natural language processing (15; 21), clustering (16; 22), domain adaptation (23) and game playing(24). For policy learning, some related ideas have been
explored where multiple estimators of the value or critic
function are trained together (25; 26).
Policy Learning for Sequential Decision Making Sequential decision making pertains to tasks where the policy performs a series of actions in a stateful environment.
A popular framework to characterize the interaction between the agent and the environment is a Markov Decision
Process (MDP). There are two main approaches for policy learning in MDPs. The first is reinforcement learning,which uses the observed environmental rewards to perform
policy optimization. Recent work include Q-Learning approaches such as deep Q-Networks (27), as well as policy
gradient approaches such as DDPG (28), TRPO (29) andPPO (30). Despite its successful applications to a wide variety of tasks including playing games (27; 31), robotics(32; 33) and combinatorial optimization (2; 4; 3), high sample complexity and unstable learning pose significant challenges in practice (34).

The second approach, imitation learning, uses demonstrations (from an expert) as the primary learning signal. One popular class of algorithms is reduction-based(35; 36; 37; 38; 39), which generates cost-sensitive supervised examples from demonstrations. Other approaches include estimating the expert’s cost-to go (40), inverse reinforcement learning (41; 42; 43), and behavioral cloning(44). Recent works have also explored on how to combine
these two types of learning (45; 17; 46; 47). One major
limitation of imitation learning is the reliance on demonstrations for reliable learning. For both imitation learningand reinforcement learning, we show that co-training on
two views can provide surrogate demonstrations in the former and improved exploration in the latter, in both cases
leading to superior performance.

3. Background & Preliminaries
Markov Decision Process with Two State Representations. A Markov decision process (MDP) is defined by
a tuple (S, A, P, r, γ, ST ). Let S denote the state space,
A the action space, P(s0 |s, a) the (probabilistic) state dynamics, r(s, a) the reward function, γ the discount factorand (optional) ST a set of terminal states where the decision process ends. We consider both stochastic and deterministic MDPs. An MDP with two views can be written as MA = (S A , AA , P A , rA , γ A , STA ) and MB =(S B , AB , P B , rB , γ B , STB ). To connect the two views, we
make the following assumption about the ability to translate trajectories between the two views.
Assumption 1. For a (complete) trajectory in MA , τ A =
A A A
A
(sA
0 , a0 , s1 , a1 , · · · , sn ), there is a function fA→B such
A
B
B B
B
B
that fA→B (τ ) = τ = (sB
0 , a0 , s1 , a1 , · · · , sm ) is aB(complete) trajectory in M . And rewards for τ A andτ B are the same under their respective reward functions,n−1
m−1
P A A AP B B Bi.e.,r (si , ai ) =r (sj , aj ). Similarly, there
i=0

j=0

is also a function fB→A that maps trajectories in MB to
MA which preserves the total rewards. Moreover, fA→B
and fB→A are the inverse maps of each other.
Combinatorial Optimization Example. Minimum vertex cover (MVC) is a classical combinatorial optimization
defined over a graph G = (V, E). A cover set is defined asa subset U ⊂ V such that every edge e ∈ E is incident to atleast one v ∈ U . The objective is to find a U with minimal
cardinality. For the graph in Figure 1, a minimal cover set
is {2, 3, 4}.
There are two natural ways to represent an MVC problem
as an MDP. The first is graph-based (4), and sets the action
space as V , and the state space as sequences of vertices
in V representing partial solutions. The deterministic transition function is the obvious choice of adding vertices toCo-training for Policy Learning

the current partial solution. The rewards are -1 for eachselected vertex. A terminal state is reached if the selectedvertices form a cover.
The second way is to formulate an integer linear program(ILP) that encodes MVC problem:
X
max −
xv ,
v∈V

Based on the equivalence between a policy and its occupancy measure (50), we can rewrite the final term in(1) with the occupancy measure, ρπ (s, a) = P(π(s) =∞P
γ i P(si = s|π).
a)i=0With slight notation abuse, define ρπ (s) =xu + xv ≥ 1, ∀e = (u, v) ∈ E,
xv ∈ {0, 1}, ∀v ∈ V.

E

τ ∼π 0We use branch-and-bound (48) to solve this ILP. Branchand-bound represents the optimization problem as a searchtree, and explores different areas of a search tree through asequence of branching operations. The MDP states represent current search tree, and the actions correspond towhich node to explore next. The deterministic transition
function is the obvious choice of adding a new node into
the search tree. The rewards are zero during intermediate
steps and the agent receives reward equal to the best objective value found in the end. A terminal state is a search tree
which contains an optimal solution.
The relationship between solutions in the two formulations
are clear. For a graph G = (V, E), a feasible solution to
the ILP corresponds to a vertex cover by selecting all thevertices v ∈ V with xv = 1 in the solution.
Note that, despite the deterministic dynamics, solving
MVC other combinatorial optimization problems can be
extremely challenging due to the very large state space. Indeed, policy learning for combinatorial optimization is a
topic of active research (18; 1; 5; 3; 6).
Policy Learning. We consider policy learning over a distribution of MDPs. For instance, there can be a distribution of MVC problems. Formally, we have a distribution D of MDPs that we can sample from (i.e.,M ∼ D). For a policy π, we define the following terms: J(π) = EM∼D [η(π, M)], η(π, M) =n−1
P iγ r(si , ai )], Aπ (s, a) = Qπ (s, a) − Vπ (s),Eτ ∼π [
i=0
n−1
P

γ i r(si , ai )|s0 = s, a0 = a],

i=0
n−1
P

Vπ (s) = Eτ ∼π [γ i r(si , ai )|s0 = s] with J being thei=0

overall objective, η the expected cumulative reward of anindividual MDP M, A the advantage function, Q the Q
function, and V the value function. The performanceof two policies can be related via the advantage function(29; 49):η(π 0 , M) = η(π, M) + Eτ ∼π0 [γ i P(si =i=0s|π) to be the state visitation distribution. In policy iteration, we aim to maximize:subject to :Qπ (s, a) = Eτ ∼π [

∞
P

n−1
X
i=0

γ i Aπ (si , ai )]

(1)

[

n−1
X

γ i Aπ (si , ai )]

i=0

=

n−1
X

Esi ∼ρπ0 (s) [Eai ∼π0 (si ) [γ i Aπ (si , ai )]],

i=0

≈

n−1
X

Esi ∼ρπ (s) [Eai ∼π0 (si ) [γ i Aπ (si , ai )]].

i=0This is done instead of taking an expectation over
ρπ0 (s) which has a complicated dependency on a yet
unknown policy π 0 .
Policy gradient methods tend
to use the approximation by using ρπ which depends on the current policy.
We define the approximate objective as ηπ (π 0 , M) = η(π, M) +n−1
PEsi ∼ρπ (s) [Eai ∼π0 (si ) [γ i Aπ (si , ai )]], and its associated
i=0

expectation over D as Jπ (π 0 ) = EM∼D [ηπ (π 0 , M].

4. A Theory of Policy Co-training
In this section, we provide a theoretical characterizationof policy co-training, which motivates the design of our
CoPiEr algorithm presented in Section 5. Our theoretical analysis quantifies the policy improvement in termsof policy advantages and differences, and caters to policy
gradient approaches. Due to space constraint, we defer all
proofs to the appendix.
For an MDP M ∼ D, consider the rewards of two policies with different views η A (π A , MA ) and η B (π B , MB ).
If η A (π A , MA ) > η B (π B , MB ), then on this instance π A
performs better than π B , and thus we could use the translated trajectory of π A as a demonstration for π B . Even
when J(π A ) > J(π B ), because J is computed in expectation over D, π B can still perform better than π A on some
MDPs. Thus it is possible for the exchange of demonstrations to go in both directions.
Formally, we can decompose the distribution D into twoparts D1 and D2 such that the support of D, supp(D) =supp(D1 )∪supp(D2 ) and supp(D1 )∩supp(D2 ) = ∅, where
for an MDP M ∈ supp(D1 ), η(π A , MA ) ≥ η(π B , MB )and for an MDP M ∈ supp(D2 ), η(π B , MB ) >η(π A , MA ). By construction, we can quantify the perfor-

Co-training for Policy Learning

mance gap as:

Algorithm 1 CoPiEr (Co-training for Policy Learning)

Definition 1.

1: Input:δ1 = EM∼D1 [η(π A , MA ) − η(π B , MB )] ≥ 0
δ2 = EM∼D2 [η(π B , MB ) − η(π A , MA )] > 0
We can now state our first result on policy improvement.
Theorem 1. (Extension of Theorem 1 in (17)) Define:A
αD= EM∼D [max DKL (π A (s)kπ 0A (s))],s

A distribution D of MDPs, two policies
π A , π B , mapping functions fA→B , fB→A
2: repeat3:
Sample M ∼ D, form MA , MB
4:Run π A on MA to generate trajectories {τiA }m
i=15:Run π B on MB to generate trajectories {τjB }nj=16:{τi0 A }, {τj0 B } ← EXCHANGE({τiA }, {τjB })7:
π A ← UPDATE(π A , {τiA }, {τj0 A })8:
π B ← UPDATE(π B , {τiB }, {τj0 B })9: until Convergence

B
βD= EM∼D2 [max DJS (π B (s)kπ A (s))],
2
s

B
αD
= EM∼D [max DKL (π B (s)kπ 0B (s))],s

A
βD= EM∼D1 [max DJS (π A (s)kπ B (s))],
1
s

B
D2 =
A
D =

M∈supp(D2 ) s,amax

max |AπA (s, a)|,M∈supp(D) s,a

A
D1 =
B
D =

max |AπB (s, a)|,max

max |AπA (s, a)|,max

M∈supp(D1 ) s,amax

max |AπB (s, a)|.

M∈supp(D) s,a

Here DKL & DJS denote the Kullback-Leibler andJensen-Shannon divergence respectively. Then we have:J(π 0A ) ≥ JπA (π 0A ) −

B B
A A
D )
2γ A (4βD + αD
2 D2
+ δ2
A
2
(1 − γ )J(π 0B ) ≥ JπB (π 0B ) −

B B
A A
D )
 + αD2γ B (4βD
1 D1+ δ1(1 − γ B )2

Compared to conventional analyses on policy improvement, the new key terms that determine how much the policy improves are the β’s and δ’s. The β’s, which quantify
the maximal divergence between π A and π B , hinders improvement, while the δ’s contribute positively. If the net
contribution is positive, then the policy improvement boundis larger than that of conventional single view policy gradient. This insight motivates co-training algorithms that explicitly aim to minimize the β’s.

Algorithm 2 EXCHANGE
B n
1: Input: Trajectories {τiA }m
i=1 and {τj }j=1
1
2: Compute estimate η̂(π A , MA ) = m

3: Compute estimate η̂(π B , MB ) = n1

m
P
i=1
n
P
j=1

r(τiA )r(τjB )

4: if η̂(π A , MA ) > η̂(π B , MB ) then5:
{τiA→B } ← {fA→B (τiA )}m
i=1
6:{τjB→A } ← ∅7: else8:{τiA→B } ← ∅9:{τjB→A } ← {fB→A (τjB )}nj=1
10: end if
11: return {τiA→B }, {τjB→A }This mirrors the theoretical insight presented in Section 4,
where based on which sub-distribution an MDP is sampled
from, the relative quality of the two policies is different.
For UPDATE, we can form a loss function that is derived from either imitation learning or reinformcent learning. Recall that we aim to optimize the β terms in Theorem
1, however it is not feasible to directly optimize that. So
we consider a surrogate loss C (line 2 of Algorithm 3) thatmeasures the policy difference. In practice, we use typically behavior cloning loss as the surrogate.

6. Experiments on Minimum Vertex Cover
5. The CoPiEr Algorithm
We now present practical algorithms motivated by the theoretical insights from Section 4. We start with an algorithm named CoPiEr (Algorithm 1), whose important subroutines are EXCHANGE and UPDATE.
Algorithm 2 covers exchanging trajectories generated by
the two policies. First we estimate the relative quality ofthe two policies with their sampled trajectories (Line 2-3 in
Algorithm 2). Then we use the trajectories from the better
policy as demonstrations for the worse policy on this MDP.

We now present empirical results on minimum vertex coverby applying a combination of policy co-training: reinforcement learning on one view and imitation learning on theother.
Setup. We consider the challenging combinatorial optimization problem of minimum vertex cover (MVC). We
use 150 randomly generated Erdős-Rényi (51) graph instances for each scale, with scales ranging {100-200, 200300, 300-500, 400-500} vertices. For training, we use 75
instances, which we partition into 15 labeled and 60 unla-Co-training for Policy Learning

Algorithm 3 UPDATE
1: Input: Current policy π, sampled trajectories from π,0 n{τi }mi=1 and demonstrations {τj }j=1
2: Form
loss
function
L(π)
=
 m a
− P r(τ ) + λC(π, {τ 0 }n ), RL with IL loss
i

i=1

j j=1

λC(π, {τj0 }nj=1 ), IL loss only
3: Update π ← π − α∇L(π)


Figure 2. Comparison of CoPiEr with other learning-based baselines and a commercial solver, Gurobi. The y-axis measure
relative gaps of various methods compared with CoPiEr Final.
CoPiEr Final outperforms all the baselines. Notably, the gaps are
significant because getting optimizing over large graphs is very
challenging.

beled instances. We use the best solution found by Gurobi
within 1 hour as the expert solution for the labeled set tobootstrap imitation learning. For each scale, we use 30
held-out graph instances for validation, and we report theperformance on 45 test graph instances.
Views and Features. The two views are the graphs themselves and integer linear programs constructed from thegraphs. For the graph view, we use DQN-based reinforcement learning (4) to learn a sequential vertex selection policy. We use structure2vec (52) to compute graph embeddings to use as state representations. For the ILP, we
use imitation learning (1) to learn node selection policy forbranch-and-bound search. A node selection policy determines which node to explore next in the current branchand-bound search tree. We use node-specific features (e.g.,
LP relaxation lower bound and objective value) and treespecific faetures (e.g., integrality gap, and global lower andupper bounds) as our state representations.
Policy Class. For the graph view, our policy class is similar to (4). In order to perform end-to-end learning of theparameters with labeled data exchanged between the twoviews, we use DQN (27) with supervised losses (53) tolearn to imitate the better demonstrations from ILP view.
For all our experiments, we determined the regularizer forthe supervised losses and other parameters through crossvalidation on the smallest scale (100-200 vertices). The
graph view models are pre-trained with the labeled set using behavior cloning. We use the same number of training
iterations for all the methods.
For the ILP view, our policy class consists of a node ranking model that prioritizes which node to consider next. We
use RankNet (54) as the ranking model, instantiated using a
2-layer neural network with ReLU as activation functions.
We implement our approach for the ILP view within the
SCIP (55) integer programming framework.
Methods Compared. At test time, when a new graph isgiven, we can run both policies and return the better solution. We term this practical version “CoPiEr Final” andmeasure other policies’ performance against it. We compare with single view learning baselines. For the graphview, we compare with RL-based policy learning overgraphs (4), labelled as “Graph (RL)”. And for the ILP view,
we compare with imitation learning method (1) “ILP (DAgger)”, retrospective imitation method (5) “ILP (Retrospective Imitation)” and a commercial solver Gurobi (56). We
also show the performance of the two policies in CoPiEr
as standalone policies instead of combining them, labelled“Graph (CoPiEr)” and “ILP (CoPiEr)”. ILP methods
are limited by the same node budget in branch-and-boundtrees.
Results. Figure 2 shows the results. We see that CoPiEr
Final outperforms all baselines as well as Gurobi. Interestingly, it also performs much better than either standalone
CoPiEr policies, which suggests that Graph (CoPiEr) is
better for some instances while ILP (CoPiEr) is better onothers. This finding validates combining the two views to
maximize the benefits from both.

7. Conclusion & Future Work
We have presented CoPiEr (Co-training for Policy Learning), a general framework for policy learning for sequential
decision making tasks with two representations. Our approach is compatible with both reinforcement learning andimitation learning as subroutines. We evaluated on a challenging combinatorial optimization problem which shows
significant improvements over numerous baselines.
There are many interesting directions for future work. On
the theory front, directions include extending to more than
two views. On the application front, algorithms such as
CoPiEr can potentially improve performance in a wide
range of robotic and other autonomous systems that utilize
different sensors and image data.

Co-training for Policy Learning

References[1] He He, Hal Daume III, and Jason M Eisner. Learning to search in branch and bound algorithms. In
Advances in neural information processing systems,
pages 3293–3301, 2014.
[2] Irwan Bello, Hieu Pham, Quoc V Le, Mohammad
Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv
preprint arXiv:1611.09940, 2016.
[3] Azalia Mirhoseini, Hieu Pham, Quoc V Le, Benoit
Steiner, Rasmus Larsen, Yuefeng Zhou, Naveen Kumar, Mohammad Norouzi, Samy Bengio, and Jeff
Dean. Device placement optimization with reinforcement learning. In International Conference on Machine Learning (ICML), 2017.
[4] Hanjun Dai, Elias B Khalil, Yuyu Zhang, Bistra
Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. arXiv preprint
arXiv:1704.01665, 2017.
[5] Jialin Song, Ravi Lanka, Albert Zhao, Yisong Yue,and Masahiro Ono. Learning to search via retrospective imitation. arXiv, 2018.
[6] Mislav Balunovic, Pavol Bielik, and Martin Vechev.
Learning to solve smt formulas. In Advances in Neural Information Processing Systems, pages 10338–
10349, 2018.
[7] Endre Boros and Peter L Hammer. The max-cut problem and quadratic 0–1 optimization; polyhedral aspects, relaxations and bounds. Annals of Operations
Research, 33(3):151–180, 1991.
[8] Wenceslas Fernandez de la Vega and Claire KenyonMathieu. Linear programming relaxations of maxcut.
In Proceedings of the eighteenth annual ACM-SIAM
symposium on Discrete algorithms, pages 53–61. Society for Industrial and Applied Mathematics, 2007.
[9] AJ Orman and HP Williams. A survey of different
integer programming formulations of the travelling
salesman problem. In Optimisation, econometric andfinancial analysis, pages 91–104. Springer, 2007.
[10] Temel Öncan, İ Kuban Altınel, and Gilbert Laporte.
A comparative analysis of several asymmetric traveling salesman problem formulations. Computers &Operations Research, 36(3):637–654, 2009.
[11] Bradly C Stadie, Pieter Abbeel, and Ilya Sutskever.
Third-person imitation learning.
arXiv preprint
arXiv:1703.01703, 2017.

[12] Melvin Johnson, Mike Schuster, Quoc V Le, Maxim
Krikun, Yonghui Wu, Zhifeng Chen, Nikhil Thorat,
Fernanda Viégas, Martin Wattenberg, Greg Corrado,
et al. Googles multilingual neural machine translation system: Enabling zero-shot translation. Transactions of the Association for Computational Linguistics, 5:339–351, 2017.
[13] Avrim Blum and Tom Mitchell. Combining labeled
and unlabeled data with co-training. In Conference
on Learning Theory (COLT), 1998.
[14] Chang Xu, Dacheng Tao, and Chao Xu. A survey on
multi-view learning. arXiv preprint arXiv:1304.5634,
2013.
[15] Xiaojun Wan. Co-training for cross-lingual sentimentclassification. In Proceedings of the Joint Conferenceof the 47th Annual Meeting of the ACL and the 4thInternational Joint Conference on Natural Language
Processing of the AFNLP: Volume 1-volume 1, pages
235–243. Association for Computational Linguistics,
2009.
[16] Abhishek Kumar and Hal Daumé. A co-training approach for multi-view spectral clustering. In International Conference on Machine Learning (ICML),
2011.
[17] Bingyi Kang, Zequn Jie, and Jiashi Feng. Policy
optimization with demonstrations. In International
Conference on Machine Learning, pages 2474–2483,
2018.
[18] Elias Boutros Khalil, Pierre Le Bodic, Le Song,
George L Nemhauser, and Bistra N Dilkina. Learning
to branch in mixed integer programming. In AAAI,
pages 724–731, 2016.
[19] Kamal Nigam and Rayid Ghani. Analyzing the effectiveness and applicability of co-training. In ACM
Conference on Information and knowledge Management (CIKM), 2000.
[20] Vikas Sindhwani, Partha Niyogi, and Mikhail Belkin.
A co-regularization approach to semi-supervised
learning with multiple views. In Proceedings of ICML
workshop on learning with multiple views, volume
2005, pages 74–79. Citeseer, 2005.
[21] Svetlana Kiritchenko and Stan Matwin. Email classification with co-training. In Proceedings of the 2011
Conference of the Center for Advanced Studies on
Collaborative Research, pages 301–312. IBM Corp.,
2011.

Co-training for Policy Learning[22] Jialu Liu, Chi Wang, Jing Gao, and Jiawei Han.
Multi-view clustering via joint nonnegative matrix
factorization. In Proceedings of the 2013 SIAM International Conference on Data Mining, pages 252–260.
SIAM, 2013.
[23] Minmin Chen, Kilian Q Weinberger, and John Blitzer.
Co-training for domain adaptation. In Advances inneural information processing systems, pages 2456–
2464, 2011.
[24] Guillaume Lample and Devendra Singh Chaplot.
Playing fps games with deep reinforcement learning.
In Thirty-First AAAI Conference on Artificial Intelligence, 2017.
[25] Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Hasselt, Marc Lanctot, and Nando Freitas. Dueling network architectures for deep reinforcement learning.
In International Conference on Machine Learning,
pages 1995–2003, 2016.

[32] Sergey Levine, Chelsea Finn, Trevor Darrell, andPieter Abbeel. End-to-end training of deep visuomotor policies. The Journal of Machine Learning Research, 17(1):1334–1373, 2016.
[33] Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 32(11):1238–
1274, 2013.
[34] Peter Henderson, Riashat Islam, Philip Bachman,
Joelle Pineau, Doina Precup, and David Meger. Deep
reinforcement learning that matters. In AAAI Conference on Artificial Intelligence, 2018.
[35] Hal Daumé, John Langford, and Daniel Marcu.
Search-based structured prediction. Machine learning, 75(3):297–325, 2009.
[36] Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In International Conference on Artificial Intelligence and Statistics, 2010.

[26] Hado Van Hasselt, Arthur Guez, and David Silver.
Deep reinforcement learning with double q-learning.
In Thirtieth AAAI Conference on Artificial Intelligence, 2016.

[37] Stéphane Ross, Geoffrey Gordon, and Drew Bagnell.
A reduction of imitation learning and structured prediction to no-regret online learning. In International
Conference on Artificial Intelligence and Statistics,
2011.

[27] Volodymyr Mnih, Koray Kavukcuoglu, David Silver,
Alex Graves, Ioannis Antonoglou, Daan Wierstra,and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602,
2013.

[38] Stephane Ross and J Andrew Bagnell. Reinforcement
and imitation learning via interactive no-regret learning. arXiv preprint arXiv:1406.5979, 2014.

[28] Timothy P Lillicrap, Jonathan J Hunt, AlexanderPritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David
Silver, and Daan Wierstra.
Continuous control
with deep reinforcement learning. arXiv preprint
arXiv:1509.02971, 2015.
[29] John Schulman, Sergey Levine, Philipp Moritz,
Michael Jordan, and Pieter Abbeel. Trust region policy optimization. In International Conference on Machine Learning, 2015.
[30] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec
Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347,
2017.
[31] David Silver, Aja Huang, Chris J Maddison, Arthur
Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the gameof go with deep neural networks and tree search. nature, 529(7587):484, 2016.

[39] Kai-Wei Chang, Akshay Krishnamurthy, Alekh Agarwal, Hal Daume, and John Langford. Learning tosearch better than your teacher. In International
Conference on Machine Learning, pages 2058–2066,
2015.
[40] Wen Sun, Arun Venkatraman, Geoffrey J Gordon,
Byron Boots, and J Andrew Bagnell. Deeply aggrevated: Differentiable imitation learning for sequential
prediction. In International Conference on Machine
Learning, 2017.
[41] Pieter Abbeel and Andrew Y Ng. Apprenticeshiplearning via inverse reinforcement learning. In International Conference on Machine Learning (ICML),
2004.
[42] Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. In Advances in Neural Information Processing Systems, pages 4565–4573, 2016.
[43] Brian D Ziebart, Andrew Maas, J Andrew Bagnell,and Anind K Dey. Maximum entropy inverse reinforcement learning. In AAAI Conference on Artificial
Intelligence, 2008.

Co-training for Policy Learning[44] Umar Syed and Robert E Schapire. A game-theoretic
approach to apprenticeship learning. In Advances inneural information processing systems, pages 1449–
1456, 2008.
[45] Hoang Le, Nan Jiang, Alekh Agarwal, Miroslav
Dudik, Yisong Yue, and Hal Daumé. Hierarchical imitation and reinforcement learning. In International
Conference on Machine Learning, pages 2923–2932,
2018.
[46] Ching-An Cheng, Xinyan Yan, Nolan Wagener, andByron Boots. Fast policy learning through imitation
and reinforcement. arXiv preprint arXiv:1805.10413,
2018.
[47] Ashvin Nair, Bob McGrew, Marcin Andrychowicz,
Wojciech Zaremba, and Pieter Abbeel. Overcoming
exploration in reinforcement learning with demonstrations. In 2IEEE International Conference on
Robotics and Automation (ICRA), 2018.
[48] Ailsa H Land and Alison G Doig. An automatic
method for solving discrete programming problems.
In 50 Years of Integer Programming 1958-2008,
pages 105–132. Springer, 2010.
[49] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference
on Machine Learning, pages 267–274. Morgan Kaufmann Publishers Inc., 2002.
[50] Umar Syed, Michael Bowling, and Robert E
Schapire. Apprenticeship learning using linear programming. In International Conference on Machine
Learning, 2008.
[51] Paul Erdős and Alfréd Rényi. On the evolution of
random graphs. Publ. Math. Inst. Hung. Acad. Sci,
5(1):17–60, 1960.
[52] Hanjun Dai, Bo Dai, and Le Song. Discriminative
Embeddings of Latent Variable Models for Structured
Data. In International Conference on Machine Learning (ICML), pages 1–23, 2016.
[53] Todd Hester, Olivier Pietquin, Marc Lanctot, Tom
Schaul, Dan Horgan, John Quan, Andrew Sendonaris,
Ian Osband, Gabriel Dulac-arnold, John Agapiou, andJoel Z Leibo. Deep Q-Learning from Demonstrations.
In AAAI Conference on Artificial Intelligence, 2018.
[54] Chris Burges, Erin Renshaw, and Matt Deeds. Learning to rank using gradient descent. In International
conference on Machine learning, 1998.

[55] Tobias Achterberg. SCIP : solving constraint integer
programs. Mathematical Programming Computation,
2009.
[56] LLC Gurobi Optimization. Gurobi optimizer reference manual, 2018.

Co-training for Policy Learning

8. Appendix

η(π A , MA ).

8.1. Proofs

J(π 0A )To prove Theorem 1, we need to use a policy improvement
result for a single MDP (a modified version of Theorem 1
in (17)).

= EM∼D [η(π 0A , MA )]= EM∼D1 [η(π 0A , MA )] + EM∼D2 [η(π 0A , MA )]≥ EM∼D1 [η(π 0A , MA )]+Theorem 2. Assume for an MDP M, an expert policy πEhave a higer advantage of over a policy π with a margin,i.e., η(πE , M) − η(π, M) ≥ δ Define

2γ A (4βπB + απA )+ δM ](1 − γ A )22γ A απA≥ EM∼D1 [ηπA ( (π 0A , MA ) −]+(1 − γ A )22γ A (4βπB + απA )EM∼D2 [ηπA (π 0A , MA ) −+ δM ](1 − γ A )22γ A απA= EM∼D [ηπA (π 0A , MA )] − EM∼D []−(1 − γ A )22γ A · 4βπB
EM∼D2 [
] + EM∼D2 [δM ](1 − γ A )2B B
A A
2γ A (4βD + αD
D )
2 D2
+ δ2
≥ JπA (π 0A ) −A
2(1 − γ )EM∼D2 [ηπA (π 0A , MA ) −α = max DKL (π 0 (s)kπ(s))
sβ = max DJS (π 0 (s)kπE (s))
sπE = max |AπE (s, a)|s,aπ = max |Aπ (s, a)|s,athen η(π 0 , M) ≥ ηπ (π 0 , M) −2γ(4βπE +απ )+δ(1−γ)2

Proof. The only difference from the original theorem isthat the original assumes EaE ∼πE (s),a∼π(s) [Aπ (s, aE ) −Aπ (s, a)] ≥ δ 0 > 0 for every state s. It is a stronger
assumption which is not needed in their analysis. Notice that the advantage of a policy over itself is zero, i.e.,Ea∼π(s) [Aπ (s, a)] = 0 for every s, so the margin assumption simplifies to EaE ∼πE (s) [Aπ (s, aE )] ≥ δ 0 .

The derivation for J(π 0B ) is the same.

By the policy advantage formula,η(πE , M) − η(π, M) = Eτ ∼πE [∞X

γ i Aπ (si , ai )]i=0∞X= Esi ∼ρπE Eai ∼πE (si ) [γ i Aπ (si , ai )]i=0≥ Esi ∼ρπE [δ 0

∞
X

γi]

i=0

δ0
=
1−γ
So an assumption on per-state advantage translates to aoverall advantage. Thus we can make this weaker assumption which is also more intuitive and the original statement
still holds with a different δ term.

Proof of Theorem 1:

Proof. Theorem 1 is a distributional extension to the theorem above. For M ∼ D2 , let δM = η(π B , MB ) −