Expected flow networks in stochastic environments and two-player zero-sum games
Authors: Marco Jiralerspong
Bilun Sun
Danilo Vucetic
Tianyu Zhang
Yoshua Bengio
Gauthier Gidel
Nikolay Malkin
Venue: ICLR 2024 poster (2024)
Keywords: generative flow networks
GFlowNets
protein design
game theory
self-play
adversarial learning
stochastic environments
quantal response equilibrium
Luce agents
sequential decision making
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: We generalize GFlowNets to stochastic and adversarial environments, achieving near-perfect play in simple two-player games.

Abstract: Generative flow networks (GFlowNets) are sequential sampling models trained to match a given distribution. GFlowNets have been successfully applied to various structured object generation tasks, sampling a diverse set of high-reward objects quickly. We propose expected flow networks (EFlowNets), which extend GFlowNets to stochastic environments. We show that EFlowNets outperform other GFlowNet formulations in stochastic tasks such as protein design. We then extend the concept of EFlowNets to adversarial environments, proposing adversarial flow networks (AFlowNets) for two-player zero-sum games. We show that AFlowNets learn to find above 80% of optimal moves in Connect-4 via self-play and outperform AlphaZero in tournaments. 
Code: https://github.com/GFNOrg/AdversarialFlowNetworks.

Published as a conference paper at ICLR 2024
EXPECTED FLOW NETWORKS IN STOCHASTIC ENVIRONMENTS AND TWO-PLAYER ZERO-SUM GAMES
Marco Jiralerspong' * Bilun Sun", Danilo Vucetic", Tianyu Zhang, Yoshua Bengio", Gauthier Gidel', Nikolay Malkin
Mila Québec Al Institute, Université de Montréal marco. iir.aerspong bi Lnn. sun, danilo Lo. vucetic, iannu.zhang, @mi 1a quebec yoshua bengio, gidel gau, n gau,,
nikayay. ma malkin
ABSTRACT
Generative flow networks (etss are sequential sampling models trained to match a given distribution. GFlowNets have been successfully applied to vari- ous structured object generation tasks, sampling diverse set of high-reward ob- jects quickly. We propose expected flow networks (EFlowNets), which extend GFlowNets to stochastic environments. We show that EFlowNets outperform other GFlowNet formulations in stochastic tasks such as protein design. We then extend the concept of EFlowNets to adversarial environments, proposing adver- sarial flow networks (AtlowNets) for two-player zero-sum games. We show that AetowNets learn to find above 80% of optimal moves in Connect-4 via self-play and outperform AlphaZero in tournaments, Code: Inttps://gil
INTRODUCTION
Lahlou et al. 2023 are a unifying algorithmic framework for training stochastic policies Markov decision processes (MDPs; Sutton & Barto 2018) to sample from given distribution over terminal states. GFlowNet have been used as an efficient alternative to Monte Carlo methods for amortized sampling in applications that require finding diverse high-reward samples (Jain et al. 2022 Zhang et al. 2022 2023a Li et al. 2023 $5) This paper revisits and extends the view of GFlowNets as diversity- secking learners in MDPs, enabling the training of robust agents in stochastic environments and two-player adversarial games.
Generative flow networks (GFlowNets; Bengio et al. 2021
2023
The main application of GFlow Nets to date has been generation of structured objects x E X where X is the set of terminal states of episodic MDP given a reward function R X - R50 interpreted as an unnormalized density. The generation of follows a trajectory so - 81 - ... - 8n x, representing iterative construction or refinement (e.g.. building graph by adding one edge at time). These settings assume that applying an action to a partially constructed object deterministically yields the object 5/41. It is natural attempt generalize the GFlowNet framework stochastic environments, in which a given sequence of actions does not always produce the same final state.
However, the common notions of GFlowNets must be modified to recover useful stochastic gen- eralization. An existing attempt (Pan et al. 2023) proposes to treat stochastic transitions in the en- viromment as actions of the GFlowNet drawn from a fixed policy. One of the starting points for this paper is that this previous formulation sacrifices several desirable theoretical properties, inducing poor sampling performance in many practical settings. We propose an alternative notion of expected flow networks (EFlowNets), which provably do not suffer from the previous limitations (Fig. la).
As EFlowNets can perform inference via stochastic control in a fixed environment, they can be used to learn robust strategies against a stochastic opponent in two-player game. We further define an adversarial flow network (AFlowNet) as a collection of EFlowNet players, each with its own reward function, taking actions in shared environment. We show the existence and uniqueness of a joint optimum of the players' respective objectives. This stable point can be characterized via a probabilistic notion of game-theoretic equilibrium. We perform additional theoretical analysis and develop efficient training objectives for two-player zero-sum games.
* Equual contribution. *CIAAR Senior Fellow. CIFAR AT Chair.

---

Published as a conference paper at ICLR 2024
EFloWNet
Stoch-GFlowNet (TB constraints)
P1's turn: F1(5.)
(E over env. transitions)
agent's tum
Ri
Ra
p =
Pa wins
Ra
3
p- 0.5
Draw
p) -
Ra
1.3
0.1
0,1
(1 - p)- 0.1
2
environment's turn
75:13 0.66
Not satisfible!
Pl's turn: Fi(s) =
(a) Left: stochastic MDP with four terminal states. The first (black) transition is chosen by the agent from a lcarnable policy with parameter p, and the second (red) action is sampled from the environment's 's fixed transition distribution. Middle: Our proposed EFlowNets ($3. inte- grate over the uncertainty
(b) Optimizing two EFlowNets that play against cach other yiclds ro- bust game-playing agents. Here, branch-adjusted AFlowNet ($3.3) for two-player zero-sum game shown: each player receives re- ward of ex for a win, 1 for draw, and e-d for loss, adjusted appro- priately by branching factors.
derive expected detailed balance training objectives to amortize this integra- tion. Right: A prior approach to GFlowNets in stochastic environ- ments (Pan al. 2023 proposes to train the agent sample from the reward distribution by treating the environment transitions as actions sampled from an immutahle policy, leading to unsatisfiable constraints.
environment's 's transitions.
Figure 1: We extend GFlowNets stochastic environments (a) and games (h).
The contributions of this work are as follows:
(1) We propose expected flow networks (EFlowNets, $.11) a class of sequential sampling models and learning objectives generalizing GFlowNets on tree- rree-structured state spaces. We demonstrate theoretically and experimentally the advantages of the EFlowNet formulation over past attempts
to generalize GelowNets to stochastic environments ($3.1 14.1
(2) We define adversarial flow nelworks (AFlowNets, $3.2) for two-player games and prove the existence and uniqueness of equilibrium solutions. Proposition we exploit the zero-sum
structure of two-player games to get a novel trajectory balance (TB) loss for AFlowNets. We believe this new loss is a major algorithmic novelty. We conduct extensive experiments on two-player games showing that AFlowNets are able learn robust policies via self-play ($4.2).
(3) We connect Gelsw EelowNets, and AFlowNets to models of imperfect agents in psychol- ogy and behavioral economics A$
2 BACKGROUND
2.1
GELOWWERS IN TRER-SHAPED ENVIRONMENTS
We review GelowNets in deterministic environments, mainly following the conventions from Malkin et al. 2022). (Notably, assume that terminating states have no children and rewards are strictly positive.) In keeping with past work, we use the language of directed acyelic graphs (DAGs), rather than the equívalent language of deterministic MDPs. We state all results only for tree-structured state spaces, but note that they are special cases of results for general DAGs.
Setting. Let = (S be a directed tree, with finite sets of vertices (states) S and edges (ac- tions) A C S x S, oriented away from the root (initial state) So S. Denote by Ch(s) the set of children state y and by Pa(s) the parent of s, which exists unless s = sg- The set of childless (5n
(terminal) states is denoted X. A complete trajectory is sequence where Sn E X and each s - 5/+1 is an action. The set of complete trajectories is denoted T.
-
sn),
A (forward) policy is collection of distributions Pr | s) over Ch(s) for every policy induces a distribution over T, with Py - 31 .... in turn induces terminating distribution PE over X, defined as the marginal distribution over the final state of a trajectory T ~ (r))). One can sample x (x) by running a chain starting at so and transitioning according to Pr until a terminal state is reached.
S.X. A ... - sn) = 117-1 PF(s; 31-1). This
A reward function is a function R X - Rs0- A policy Pr is said to sample proportionally to the reward R if (x) x R(x), i.e., PT F R(x)/Z for all X, where Z. = =xxex R(x). Given
2

---

Published as a conference paper at ICLR 2024
reward function R. GFlowNet algorithms aim to produce a policy Py that samples proportionally to R. This is, in essence, generative modeling problem, but the setting is close to maximum maximum-entroopy reinforcement learning (RL; Haamooj et al., 2017): one is not given samples from the target density, as in typical generative modeling settings, but must rather explore the reward landscape through sequential sampling-
FM and DB objectives. We review the two GFlowNet objectives of flow matching (FM; Bengio al. 2021 and detailed balance (DB: Bengio et al. 2023) in tree-structured state spaces,
The FM objective optimizes a function F S + Rso, called the state flow. The objective enforces pair of constraints, which in tree-structured DAGS are
F(s) E F(s') VsES and F(x) = R(x) VxEX. x'ECh(x)
Any edge flow induces a policy Pr. defined by Pr(s' s) F(x) for all (s, E A. If the flow satisfies the FM constraints ① then it holds that Pr samples proportionally to the reward R.
F(s)
The DB objective avoids the explicit summation and the policy Pp. replacing the first constraint by
children in ( and jointly optimizes both F
F(s)Pr(s' (s) = F(*) v(s,s') E A.
(2)
This constraint implies the first constraint of [ as Pr sums to over s' E &Chss..
The function F is typically parametrized as neural network Fe with parameters 6, and (if using the DB objective) the policy PF as network producing logits of (s's s; given s as input. The parameters 0 are optimized minimize some discrepancy between the left and right sides of (T) or 2.. A typical choice is the squared log-ratio; for example, the FM objective at a state s is
(FM(S) = (10g Fo()) - log
E Fo(st)
(3)
x'ECh(s)
The choice of states at which this objective is evaluated and optimized is made by a training policy л. For example, could select the states seen in trajectories sampled from PF (on-policy training), but could also use off- off-policy exploration techniques, such as tempering, replay buffers, or Thompson sampling Exector-Brooke et al., 2023). Because the objective can be simultaneously minimized to zero at all y for a sufficiently expressive Fe, the global optimum of the objective is independent of the choice of training policy æ, long π has full support. This capacity for off-policy training without differentiating through the sampling procedure is a key advantage GFlowNets over on- policy RL algorithms and over other hierarchical variational methods (Malkin al. 2023)
Connections with RL. In the case of tree-structured state spaces, Gets are closely con- nected to entropy-regularin log-flow function with a value function, the FM/DB objectives are analogous to temporal difference learning (Sutton & Barto 20188) and TB, along with its variant SubTB (Madan al. (002)), to path consistency learning (Nachum et al., (017). As a diversity-secking agent, a GFlowNet can also be understood as way to train a quantal response agent; see $A for more discussion.
RL methods (soft Q-learning; |Haamoja et al.. 2017): identifying the
How restrictive is the tree structure? Any environment that has non-tree DAG structure i.e., where multiple trajectories may lead the same state can be converted to a tree-structured environment by augmenting each state with the history (the trajectory followed to reach the state). This implicitly multiplies the reward of each terminal state by the number of trajectories that lead to it (while keeping the optimal policy independent of the history). This alternative way to reward the state may be desired in some applications (e.g., zero-sum games) for which the path to the solution matters as much as the outcome.
2.2
PAST APPROACHESS TO GFLOWNETS IN STOCHASTIC ENVIRONMENTS
Pan et al. 2023 propose a generalization of GFlowNets to stochastic environments (i.e., where the state and choice of action nondeterministially yield the subsequent state), following an approach described in Bengio et al. (2023). We now review their formulation, which we refer to as 'stochastic GFlowNets', restating it in suitable language motivate method.
3

---

Published as a conference paper at ICLR 2024
In stochastic environments, every state is associated with set of possible actions Ag, and the environment provides a stochastic transition function - a distribution Pear (s' s, s.a), understood as the likelihood of arriving in state s' when taking action at state In stochastic GFlowNets, the state space S is augmented with a collection of hypothetical states (s, a) for s E S \X and a A,-
The augmented DAG G contains two kinds of edges:
Edges s - (s, a) for each s E S and a E As, which we call agent edges;
Edges (s, a) s' for each hypothetical s' in the support of Penv( s. s. a e As and s' e Ch(s), which we call environment edges.
Stochastic GFlowNets directly apply the training algorithms applicable to deterministic Gets (e.g.. DB) to the augmented DAG G, with the only modification being that the forward policy PF free to be learned only on agent edges, while on environment edges it is fixed to the transition function. Formally, for all E S \ X and E Ay, one learns Pr((s, a) (denoted Pp (a s) for short), while Pr (s) is fixed to Pen (s' s. s.a).
The environment policy Penv. which appears in the loss, may be assumed to be known, but may also be approximated using a neural network trained by a maximum-likellhon objective on observed environment transitions, jointly with the agent policy.
Violated desiderata in stochastic GFlowNets. By construction, if stochastic GelowNet satisfies the DB constraints, then the policy PF samples proportionalyy to the reward R. In this way, stochas- tic GFlowNets are a minimal modification of GFlowNets that can function stochastic environ- ments. However, there exist stochastic environments and reward functions for which no stochastic GFlowNet policy Py (a s) can satisfy the constraints (Fig. la]. Two consequences of this are the impossibility of minimizing the loss to zero for all transitions, model, and the resulting dependence
for perfectly expressive policy
the global optimum on the choice of training policy æ. Thus stochastic GelowNets satisfy DO, but not D1 (as noted by |Bengio al. (2023) and D2 below.
The generalization of GFlowNet constraints and objectives to stochastic environments that we pro- pose satisfies the following desiderata:
DO. If the environment's transition function Peny is deterministic, one should recover deterministic GelowNet constraints and objectives.
DI. Satisfiability: A perfectly expressive model should be able to minimize the generalized FM/DB losses to 0 for all states/actions in the DAG simultaneously. Consequently, the set of global optima of the loss should not depend on the choice of full-support training policy.
D2. Uniqueness: If G is a tree, then the global optimum of the loss should be unique.
D3. Equilibrium: In game where two GFlowNet agents alternate actions, there should be unique pair of policies for the two players such that each policy is optimal for its respective loss.
As noted in 2 deterministic GFlowNets satisfy DI and D2. DO is common-sense property. as deterministic environments are special cases of stochastic environments. D1 (satisfiability) is essential for off-policy training, while D2 (uniqueness) is desirable in game-playing agents. The meaning of D3 will be detailed in $3.2
METHOD: EXPECTED AND ADVERSARIAL FLOW NETWORKS
3.1 EXPECTED FLOW NETWORKS
In this section, define expected flow networks (EFlowNets) tree-structured spaces, which encompasses the problems we study, in particular, two-player games with memory. We then show that EFlowNets satisfy the desiderata DO-D2 above.
Expected flow networks (EFlowNets) assume the following are given:
A tree G (S,A), with initial state so and set of terminal states X, and reward function X X -
A partition of the nonterminal states into two disjoint sets, S \XX Sagent L Senvs called the agent states and environment states, respectively.
A distribution (- (- s) over the children of every environment state s Senv.
Observe that if Senv = 0, then the input data for an EFlowNet is the same as the input data for a
GFlowNet on a tree-structured space. This setting also generalizes that of stochastic GFlowNets
4

---

Published as a conference paper at ICLR 2024
in $2.2 where all transitions link agent states environment states (s,a) called 'hypothetical states by Pan et al. (2023 or vice versa.
An agent policy is collection of distributions Pagend-- | s) over the children of every agent state s E Sagent. Together, P Pagent and Penv determine a forward policy on G. We define the expected detailed balance (EDB) constraints relating l' l'agents Peay, and state flow function F S Roo:
F(s) agent (s'
s) = F(s')
Vs E Sagent s' E &Ch(s),
(4)
F(s) = P3 (s'1s) F(s)
Vs E Senv.
(5)
F(x)= = R(x)
E
(6)
These constraints satisfy the desiderata DO-D2, as summarized in the following proposition.
Proposition 1. There exists a unique pair of state flow function F and agent policy P Pagent satisfying
constraints and (6). Senv 0, then this pair satisfies the detailed balance constraints (2).
NetowNets marginalize over the uncertainty of the environment's transitions: they aim to sample each action in proportion to the expected total reward available if the action is taken (see Prop. connection between EFlowNets and Luce quantal response agents is made in S
Training EFlowNets: From constraints to losses. Just in deterministic environments, when training EFlowNets, we parametrize the state flow and agent policy as neural networks Fe and Pagen(( (- 0)) The EDB constraints can be turned into squared log-ratio losses in the same manner that the FM constraint
[ is converted into the loss and optimized by gradient descent.
In problems where the number of environment transitions is large and computing the expectation on the right side of (5) is costly, it may be replaced by an alternative constraint by introducing a distribution Q(s' s) (sn(ss) This quantity sums to 1 over the s' if and only if (5) is
F(x) satisfied. Thus (5) is equivalent to the following constraint on Q:
F(s)@(s' () = F(s') s).
Enforcing this constraint requires learning additional distribution @(s' 0), but does not require summation over children. The conversion from (5) to resembles that from FM ①I to DB (2).
Just like deterministic GFlowNets, the globally optimal agent policy in EFlowNet is unique and does not depend on the distribution of states at which the objectives are optimized, as long as it has full support. However, the choice of training policy can be important hyperparameter that can affect the rate of convergence and the local minimum reached in a function approximation setting. We describe the choices we make in the experiment sections below.
Just like in stochastic GFlowNets ($2.2), the environment policy Penv can be either assumed to be known or learned, jointly with the policy, from observations of the environment's transitions.
3.2 ADVERSARIAL FLOW NETWORKS
We now consider the application of EFlowNets to multiagent settings. Although our experiments are in the domain of two-player games, we define adversarial flow networks (AFlowNets) in their full generality, with agents. AFlowNets with agents, or players, depend on the following information:
tree = A). with initial state so and set of terminal states X, and collection of reward functions RI...., Rn X - Rso.
partition of the nonterminal states into disjoint sets, S S
This data defines fully observed sequential game, where E S; means that player i is to play at s. An agent policy for player is collection of distributions P: s) over Ch(s) for every E S,.
The input data for an AFlowNet also defines a collection of EFlowNets, one for each player i. The EelowNet & for player/ has the same underlying graph G, with Sagent = S; and Senv = Lزززا S = S S. (X U S,), and reward function R, That is, each player is viewed agent in NelowNet whose "environment' is given by the other players' policies. (We also remark that the case recovers regular (deterministic) GFlowNet.)
The policy P, of player/ can be optimized using the EFlowNet training objective given fixed values of the other players' policies P. (j # i), and by Proposition I there is unique global optimum for P,. However, remarkably, there exists a unique collection of policies PI....,P .....,P, P,, such that each P
that jointly satisfy the EelowNet constraints for each player.
5

---

Published as a conference paper at ICLR 2024
Proposition 2. There exist unique agent policies PI,...,Pr, and state flow functions Fi..... Fn. + Rx0 such that Pi and F; satisfy the EDB constraints with respect to the EFlowNer & for all
We also have a characterization of the joint optimum in the case of two-agent AFlowNets:
Proposition 3. Suppose that in 2-player AFlowNet, the agent policies Pt. P2 and state flow func- tions F1, F2 are jointly optimal in the sense of Prop. 2 Then the function F(s) = (2()) is a flow on G, i.e,, satisfies the FM constraint
[ with respect to the reward R(x) = (x))
3.3 BRANCH-ADIUSTED AFLOWNETS FOR TWO-PLAYER ZERO-SUM GAMES.
An important application of AFlowNets two-player zero-sum games. We will now describe way to turn the game outcomes into rewards that allows simpler and more efficient training objective.
complete-informatiin game with tree-shaped state space G, Specifically, we consider two-player, in which player 1 moves first (i.e., So E Si) and the players alternate moves, i.e., every complete trajectory 8o - 81 -
Sn = x has s Si if and only if even. We assume that the game ends in win for player 1, win for player 2, or draw. A na've way to define the rewards for players and 2 is the following. which ensures the log-rewards sum to zero every terminal state:
ed
player wins, if the game ends in a draw,
(x)
(8)
e if player loses.
However, we find that AFlowNets trained with this reward often exhibit suboptimal behaviour in complex games: the agent may avoid move that leads directly winning terminal state (high reward) in favour of a move with a large downstream subtree. We therefore define an alternative reward function that favours shorter winning trajectories. so Sj - Sn = is the trajectory leading to x, then the branch-adjusee reward for player is defined as
(x)
B2(x) = 11 (Ch(s.))
(x) = (x
kisg k:
That is, (x) is the product of the branching factors (numbers of children) of the states on the trajectory at which player is move! Besides delivering higher reward for less selective trajectories and being empirically essential for good game-playing performance, this correction is necessary to derive the simplified objective below, which critically uses
A 'trajectory balance' for branch-adjusted AFlowNets. A limitation of objectives such as FM, DB, and their EFlowNet and AFlowNet generalizations are their slow credit assignment (propaga- tion of a reward signal) over long trajectories, which results from these losses being local to state or transition. This limitation motivated the trajectory balance (TB) loss for GFlowNets (Malkin et al.) 2022). which delivers gradient update all policy probabilities along complete trajectory.
While the GFlowNet TB objective does not appear to generalize to expected flow networks, we derive objective of TB-like flavour for branch-adjusted AFlowNets.
Proposition 4. 2 2-player AFlowNet with alternating moves satisfying (x(x)
(a) Suppose that the agent policies Pı, P2 and state flow functions Fi. F2 are jointly optimal in the sense of Prop. 2 Then there exists a scalar Z,, independent of x, such that for every complete trajectory
81
Sn
Z
Pi st) (2()
I EayES,
P2(si01 st).
(10)
E
(b) Conversely, the constraint (10) holds for some constant Z and policies P1 and P2, then and P2 are the jointly optimal AFlowNet policies.
The constraint 100) can be converted into training objective LTB the squared log-ratio between the left and right sides and optimized with respect to the policy parameters and the scalar Z (parametrized through log for stability) for complete trajectories (game simulations) sampled from a training policy. Prop.2jas and Prop. 4() guarantee that the constraints are satisfiable, while Prop. (b) guarantees that the policies satisfying the constraints are unique.
While the branching factor appears large, it is counteracted by the fact that, an AFlowNet agent's tum, its child flows are summed, e.g., (s) EveCt()) (i') if S

---

Published as a conference paper at ICLR 2024
Training AFlowNets. AFlowNets are trained by optimizing the EFlowNet objectives of each agent independently. The states at which the objectives are optimized are chosen by a training policy, which may either sample the agents' policies to produce training trajectories (on-policy self- play) or use off-policy exploration. The joint global optimum, where all agents optimize their losses to 0, is unique and independent of the training policy due to Prop. 2 See Alg. 1
A significant benefit of AFlowNets over methods like Silver et al. (2018) is that they do not require expensive rollout procedures (i.e., MCTS) generate games. MCTS performs a number of simula- tions- - each of which requires a forward pass - for every state in a game. AllowNets, on the other hand, only require single forward pass per state. Consequently, AFlowNets can be trained on more games given a similar computational budget.
EXPERIMENTS
We conduct experiments to investigate whether EFlowNets can effectively learn in stochastic en- vironments compared to related methods ($4.1) and whether AFlowNets are effective learners of adversarial gameplay, as measured by their performance against contemporary approaches ($4.2
4.1 GENERATIVE MODELING IN STOCHASTIC ENVIRONMENTS
We evaluate NetowNets in protein design task from Jain et al. 2022). The GFlowNet policy
8
0 10
8 - 30
1.00
Mean top 100 reward
2.65
autoregressively generates an 8-symbol DNA sequence x and receives a reward of R(x) = fx)),, where f(x) is a proxy model estimat- ing binding affinity to a target protein and B is hyperparameter controlling the reward distribu- tion's 's entropy. In Pan et al. (2023), the problem was made stochastic by letting the environment replace the symbol appended by the policy to the right of a partial sequence with a uniformly random symbol with probability a. Thus gives a deterministic environment and a = fully stochastic environment, where the pol- icy's 's actions have no effect.
0.50
0.83
0.80
30-
25
Modts
30-
0.1
0.3
0.5
0.7
0.9
0.1
033
0.5
0.7
5.9
0.1
0.3
05
0.7 0.
Stochasticity
Stachasticity
Stoch Mocchatictt
SBC
GPN
Stoch GPN
BFN
Randoni
Figure 2: Results on the TFBind task (five seeds per set- ting). FelowNets tend to find more diverse high-reward states, especially when the reward is peaky and envi- ronment stochasticity high, making the Stoch-GFN constraints unsatisfiable.
We extend the published code of Pan al. 2023) with an implementation of the EFlowNet objective. Besides the stochas- tic GelowNet (Stoch-GFN) formulation from $2.2 we compare with the two strongest baselines considered in that work: "naïve" Gelow that ignores the environment's transitions (GFN), and a discrete soft actor-critic (SAC; Haarnoja et al.] 2018). We use the hyperparameters from the existing implementation for all methods (except SAC, which we reimplemented because code was not available) and report the same primary metrics: the mean reward of the top-100 sequences among 2048 sampled from trained model and the number of diverse modes found, as measured by the sphere exclusion algorithm from Jain et al. (2022). A model of the environment's transition distribution is learned, consistent with Pan et al. (2023).
The results and error ranges, with different values of the stochasticity a and reward exponent B. are shown in Fig. 2 When the reward is peaky (larger B). EFlowNets outperform other algorithms in both diversity and top-100 reward. This is consistent with situations such as those in Fig. Ta where the Stoch-GFN constraints are unsatisfiable, being more common when the reward is peaky, as the environment's 's random actions place smoothness constraints on the sampling distribution. Of note, our implementation of SAC performs better than what is reported in [aa al. (2023) and often better than Stoch-GFN, which was previously considered only with the flat-reward setting of ß =.
4.2 ADVERSARIAL GAMES
The game-playing capabilities of AFlowNets are evaluated 2-player games. Rewards are modeled as described in $3.3 and the AFlowNets trained with rewards defined by (8) with given a are denoted AFlowNet,. We evaluate how the efficacy of an agent changes with various values of d.
7

---

Published as a conference paper at ICLR 2024
Algorithm 1: Branch-adjusted AFlowNet Training
Data: a, batch size n, number of trajectories K, number of steps L. buffer capacity M,
model and training hyperparameters
Initialize AFlowNet policies Pı, 12, log Z. and replay buffer B with capacity
for i- to N do
Generate K trajectories (sampling from AFlowNet's policies Pt. P2) Add trajectories to B // B is FIFO queue
for L do
(Ti)
1 |= - Sample randomly from B
-- n Σد. LTB (log Z, PI. P2. Tj.A)
Gradient update on VL with respect to log Z and policy parameters
AflowNiet:
AFlowhietss AlphaZero
MphaZoro-MCTS
AFlowNets are trained using the TB loss to
AFlowNelas
Search (d-3)
play tic-tac-toe and Connect-4. For each, we
400
Tic-tac-toe
2000
Connect-4
run tournament against an open-souree Alp-
Elo score
300
1500
haZero implementation (Thakoor et al.) 2016)
200
and a uniform random agent. For tic-tac-toe we also include a tree-search agent which uses AlphaZero's s value function, alpha-beta prun- ing, and a search depth of 3. To compare the agents, we compute their Elo over the course of training using BayesElo (Coulom, 2008 Diaz & Bücck-Kefferr 2023). The training procedure is outlined in Alg. aand details are in (D
1000
-100
10
20
30
40
0
20
20
30
40
Steps (x10*)
Steps (x10²)
400
2000
Elo score
300
1500
1000
100
500
Figure 3 (left) illustrates the Elo of the agents in tic-tac-toe over training steps and time. It is clear that AFlowNets quickly achieve com- petitive Elo with AlphaZero. It is worth noting that AFlowNetz and AFlowNNets achieved and Elo of 334.8 15.5 and 231.1 91.3, whereas AFlowNet achieved an Elo of 338.4 1..1. As such, it appears that A has a diminishing re- turn on game performance in tic-tac-toe.
-100
1.3 2.0
Time (seconds x10²)
Time (seconds x10²)
Figure 3: Elo as a function of training steps and training time. As convention, random uniform baseline agents represent an Elo 0. AFlowNets achieve similar Elo to AlphaZero in tic-tac-toe and AFlowNets quickly learn to outperform AlphaZero Connect-4.
haccurscy
100
The parameter has large effect the perfor- mance of AFlowNets in Connect-4 (cf. Fig. 3 (right)). The AFlowNets with A {10, 15}
80-
% of move
achieve the highest Elo all tested agents.
AFlowNets win almost every game against Al- phaZero and achieve an Elo score roughly 800
20
0
Usifem
points higher. Additional tournament results and further analysis are available in S
Time (seconds) x10
Figure 4: Move quality for the AFlowNet (for set of 10240 randomly generated Connect-4 boards) over the course of training. An optimal move leads to the quick- est win slowest loss. An inaccuracy move that has the same sign as the optimal move (e.g., leading to a win but not as quickly). A blunder leads from winning state to either a drawing or losing state.
As in Prasad al. (2018), we take advantage of the fact that Connect-4 is solved (Allis 1988) to obtain perfect values for arbitrary positions. We compare the moves selected by the AFlowNet with the values computed by a perfect Connect-4 solver (Pons (2019) over the course of training. Fig. 4 shows an evaluation of the AFlowNet's performance using this metric (and baseline values for random uniform agent). The AFlowNets learn to play optimal moves in > 80% of board states after 3 hours of training on RTX8000 GPU.
non-matimal
Table I: Summary of the main differences between AFlowNet and AlphaZero training.
Nel
Alphiieero
Action sampling Objective input
single forward pass
MCTS
complete trajectory batch size traj. length
single state
States per optim. step
butch size
8

---

Published as a conference paper at ICLR 2024
Differences between AFlowNets and AlphaZero methodologies. Distinctions exist between approach and AlphaZero that make direct comparisons between the methods challenging, summa- rized in Table ! Most importantly, the batch-adjusted AFlowNet objective depends on entire game simulation, while the AFlowNet value function updates are performed at individual states. In addition, the game simulations in AFlowNets out Monte Carlo tree search. Thus, generation of training data with AFlowNets is faster than with AlphaZero, assuming the base model architectures are of similar scale.
obtained using single policy rollout, with-
Demo. We invite the reader to play Connect-4 anonymously against a pretrained AFlowNet agent the following URL: htttt::tttttiistts http://tt..yyyymmaaf.tm
5 RELATED WORK
Stochasticity in GelowNets. GFlowNets have been used diversity-secking samplers in various settings with deterministic environment transitions. In particular, they have been interpreted as hierarchical variational inference algorithms (Malkin et al. 2023 Zimmermann et al. (203) and
correspondingly applied to modeling of Bayesian posteriors (Deleu et al. [022] van Krieken et al. 2022 Hu et al. 2023). GelowNets
be trained with stochastic rewardy (Bengio et al. 2023).
and Deleu et al. (2022; 2023); Liu et al. (2022) take advantage of this property to train samplers
of Bayesian posteriors using small batches of observed data. Zhang al. (203bb) proposed to match the uncertainty in a stochastic reward in manner resembling distributional RL (Bellemare al., 2017p; however, the stochasticity is introduced only at terminal states, while we consider stochasticity in intermediate transitions. The stochastic modelling of Pan et al. (2023), we have argued, is insufficient to capture desired sampling behaviours in the problems we consider.
RL in stochastic environments and games. Learning in an environment with stochastic transi- tion dynamics and against adversaries has long been a task of RI. (Sutton Barto 2018). While AlphaZero (Silver et al. 2018) has achieved state-of-the-art performance in chess, Shogi, and Go, it does not explicitly model stochastic transition dynamics. Stochastic MuZero (Antonoglou et al. 2022) is a model-based stochastic planning method that learns model of the environment and policy at the same time, allowing it to perform well in a variety of stochastic games. Both Alp- haZero and MuZero use Monte Carlo tree search for policy and value estimation (Silver al. 2018 Antonoglou et al. 2022] Schrittwieser et al.) 2020). Our EFlowNets bear similarities to a recently introduced approach that integrates over environment uncertainty RL Yang et al. 2023)
6 DISCUSSION
This paper extends GFlowNets to stochastic and adversarial environments. Expected flow networks learn in settings with stochastic transitions while maintaining desirable convergence properties, and adversarial flow networks pit EFlowNets against themselves in self self-play. We successfully applied these algorithms to a stochastic generative modeling problem and to two real-world zero-sum games.
In future work, we intend to scale these methods to larger game spaces (e.g., chess and Go). Such scaling is likely to require algorithmic improvements to address the limitations of our method, While we derived an efficient 'trajectory balance' for tranch-adjusted AFlowNets, trajectory-level objec- tives suffer from high variance for long trajectories and have a high memory cost. Although these limitations did not surface in our experiments, would be interesting to consider interpolations between expected DB and TB, akin to subtrajectory balance for GFlowNets (Madan et al. 2023).
Other future work can consider generalizations incomplete-infommen innoomaatiniooottiionnn games and cooperative multi-agent settings. For games with continuous action spaces, one can analyze the continuous and infinite-agent (mean-fiele fieldd limits. Beyond games, GFlowNets and EFlowNets, in which node flows are computed by aggregation over children either summation (4) or expectation (5) may fall into a more general class of probabilistic flow networks that encompass range of samplers trainable by local consistency objectives, reminiscent of the manner in which the language of circuits unifies probabilistic models with tractable inference (Choi et al. 20200 Vergari et al.) 2021).
9

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
The authors thank Moksh Jain for help with baseline code for the experiments in $4.1 and Manfred Diaz for help with the Elo computations in $4.2 We also thank Quentin Bertrand and Juan Duque for their comments on draft of the paper.
YB acknowledges funding from CIFAR, NSERC, Intel, and Samsung.
GG acknowledges funding from CIFAR.
The research enabled in part by computational resources provided by the Digital Research Alliance of Canada (https: http//aaaaaancccccccccm ca), Mila (https://mil http://mml...uuee.......... and NVIDIA.
REFERENCES
Victor Allis. A knowledge-base approach of connect-four. Int. Comput. Games Assoc., 11:165, 1988.
Ioannis Antonoglou, Julian Schrittwieser, Sherjil Ozair, Thomas K Hubert, and David Silver. Plan- ning in stochastic environments with a learned model. International Conference on Learning Representations (ICLR), 2022.
Mare G. Bellemare, Will Dabney, and Remi Munos. A distributional perspective on reinforcement learning. International Conference on Machine Learning (ICML), 2017.
Emmanuel Bengio, Moksh Jain, Maksym Korablyov, Doina Precup, and Yoshua Bengio. Flow net- work based generative models for non-iterative diverse candidate generation. Neural Information Processing Systems (NeurIPS), 2021.
Yoshua Bengio, Salem Lahlou, Tristan Deleu, Edward J Hu, Mo Tiwari, and Emmanuel Bengio. GFlowNet foundations. Journal of Machine Learning Research, (24):1-76, 2023.
YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying framework for tractable probabilistic models, 2020. URL BRtpittt///ttaaa..coo ucla. edu,
papers/Probcirc2..o
Rémi Coulom. Whole-history rating: A Bayesian rating system for players of time-varying strength. In H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, and Mark H. M. Winands (eds.), Computers and Games, pp. 113-124, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.
Tristan Deleu, António Góis, Chris Emezue, Mansi Rankawat, Simon Lacoste-Julien, Stefan Bauer, and Yoshua Bengio. Bayesian structure learning with generative flow networks. Uncertainty in Artificial Intelligence (UAI), 2022.
Tristan Deleu, Mizu Nishikawa- Nishikawa-Toomey, Jithendaraa Subramanian, Nikolay Malkin, Laurent Char- lin, and Yoshua Bengio. Joint Bayesian inference of graphical structure and parameters with single generative flow network. arXiv preprini arXiv:2305. 19366, 2023.
Manfred Diaz and Aurélien Bücck-aefffer PopRank: A rating library for population Dapulation-based training, 2023. URL /ttps://github. http:u/....oopppp///paaaaao
Jianqing Fan, Zhaoran Wang, Yuchen Xic, and Zhuoran Yang. A theoretical analysis of deep q- learning. In Learning for dynamics and control, pp. 486-489 PMLR, 2020.
Jacob K Goeree, Charles A Holt, and Thomas R Palfrey. Stochastic game theory for social science: A primer on quantal response equilibrium. In Handbook of Experimental Game Theory, pp. 8-47. 2020.
Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based policies. International Conference on Machine Learning (ICMI), 2017.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. International Conference Machine Learning (ICMI.), 2018.
10

---

Published as a conference paper at ICLR 2024
Edward J Hu, Nikolay Malkin, Moksh Jain, Katie Everett, Alexandros Graikos, and Yoshua Bengio. GFlowNet-EM for learning compositional latent variable models. International Conference on Machine Learning (ICML), 2023.
Moksh Jain, Emmanuel Bengio, Alex Hermandez-Garria, Jarrid Rector-Brooks, Bonaventure F.P. Dossou, Chanakya Ekbote, Jie Fu, Tianyu Zhang, Micheal Kilgour, Dinghuai Zhang, Lena Simine, Payel Das, and Yoshua Bengio. Biological sequence design with GFlowNets. Inter- national Conference on Machine Learning (ICML), 2022.
Salem Lahlou, Tristan Deleu, Pablo Lemos, Dinghuai Zhang, Alexandra Volokhova, Alex Hernández- Léna Néhale Ezzine, Yoshua Bengio, and Nikolay Malkin. A theory con- tinuous generative flow networks. International Conference on Machine Learning (ICML), 2023.
Wenqian Li, Yinchuan Li, Zhigang Li, Jianye Hao, and Yan Pang. DAG Matters! GFlowNets enhanced explainer for graph neural networks. International Conference on Learning Represen- lations (ICLR), 2023.
Dianbo Liu, Moksh Jain, Bonaventure F. P. Dossou, Qianli Shen, Salem Lahlou, Anirudh Goyal, Nikolay Malkin, Chris C. Emezue, Dinghuai Zhang, Nadhir Hassen, Xu Ji, Kenji Kawaguchi, and Yoshua Bengio. GFlowOut: Dropout with generative flow networks. International Conference on Machine Learning (ICML), 2022.
Duncan Luce. Individual Choice Behavior: A Theoretical Analysis. Wiley, 1959.
Kanika Madan, Jarrid Rector- Brooks, Maksym Korablyov, Emmanuel Bengio, Moksh Jain, Andrei Nica, Tom Bosc, Yoshua Bengio, and Nikolay Malkin. Learning GelowNets from partial episodes for improved convergence and stability. International Conference on Machine Learning (ICML), 2023.
Nikolay Malkin, Moksh Jain, Emmanuel Bengio, Chen Sun, and Yoshua Bengio. Trajectory balance: Improved credit assignment in GFlowNets. Neural Information Processing Systems (NeurIPS), 2022.
Nikolay Malkin, Salem Lahlou, Tristan Deleu, Xu Ji, Edward Hu, Katie Everett, Dinghuai Zhang, and Yoshua Bengio. GelowNets and variational inference. International Conference on Learning Representations (ICLR), 2023.
Richard D. McKelvey and Thomas R. Palfrey, Quantal response equilibria for normal form games. Games and Economic Behavior, 10(1):6-38, 1995.
Richard D. McKelvey and Thomas R. Palfrey. A statistical theory of equilibrium in games. Japanese Economic Review, 17:186-209 1996.
Richard D. McKelvey and Thomas R. Palfrey. Quantal response equilibria for extensive form games. Experimental Economics, 1(1):9-41, 1998.
Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans. Bridging the gap between value and policy based reinforcement learning. Neural Information Processing Systems (NIPS), 2017.
Ling Pan, Dinghuai Zhang, Moksh Jain, Longbo Huang, and Yoshua Bengio. Stochastic generative flow networks. Uncertainty in Artificial Intelligence (UAI), 2023.
Pascal Pons. Connect 4 game solver. 2019.
https: httt::///ggahubb.cc///saaaaaaaas
Aditya Prasad, Vish Abrams, and Anthony ing alphazero. Medium, 2018. lessons sersons-rrom-- 2023.
Young.
Lessons from implement-
URL https://medinm um. com/orac edevs/
Accessed: 25-08-
Jarrid Rector-Brooks, Kanika Madan, Moksh Jain, Maksym Korablyov, Cheng-Hao Liu, Sarath Chandar, Nikolay Malkin, and Yoshua Bengio. Thompson sampling for improved exploration in GelowNets. arXiv preprint arXiv:2306. 17693, 2023.

---

Published as a conference paper at ICLR 2024
Julian Schrittweser,, loannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588(7839):604-600 2020.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez. Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, and Demis Hassabis. general reinforcement learning algorithm that mas- ters chess, shogi, and go through self-play. Science, 362(6419) 2018. doi: 10.1126/ science.aar6404. URL https: httt::://wwwscieence
abs http:/1.1111/ccccccccccco
aar6404
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Shantanu Thakoor, Surag Nair, and Megha Jhunjhunwala. Learning to play Othello without human knowledge, 2016.
Emile van Krieken, Thiviyan Thanapalasingam, Jakub Tomezak, Frank van Harmelen, and Annette ten Teije. A-NeSI: A scalable approximate method for probabilistic neurosymbolic inference. arXiv preprint arXiv:2212./23393. 2022.
Antonio Vergari, YooJung Choi, Anji Liu, Stefano Teso, and Guy Van den Broeck. A compositional atlas of tractable circuit operations for probabilistic inference. Neural Information Processing Systems (NeurIPS), 2021.
Sherry Yang, Dale Schuurmans, Pieter Abbeel, and Ofir Nachum. Dichotomy of control: Separating what you can control from what you cannot. 2023.
David Zhang, Corrado Rainone, Markus Peschl, and Roberto Bondesan. Robust scheduling with GFlowNets. International Conference Learning Representations (ICLR), 2023a.
Dinghuai Zhang, Nikolay Malkin, Zhen Liu, Alexandra Volokhova, Aaron Courville, and Yoshua Bengio. Generative flow networks for discrete probabilistic modeling. International Conference on Machine Learning (ICML), 2022.
Dinghuai Zhang, L.. Pan, Ricky Q. Chen, Aaron Courville, and Yoshua Bengio. Distributional GFlowNets with quantile flows. arXiv preprint arXiv:2302.05793, 2023b.
Heiko Zimmermann, Fredrik Lindsten, Jan-Willem van de Meent, and Christian A. Naesseth. A variational perspective on generative flow networks. Transactions on Machine Learning Research (TMLR), 2023.
A GFLOWNETS AS QUANTAL RESPONSE AGENTS
GFlowNet policy as a Luce agent. GelowNets in tree-structured spaces are closely related to probabilistic models of imperfect agent behaviour in game theory known quantal response agents McKelley & Palfrey 1996 1995 Goeree et al. 2020). A particular kind of quantal response agent uses the Luce ratio rule (Luce) 1959) to sample strategies in proportion
their expected payoff. GFlowNet trajectories r can be seen as (pure) strategies of an agent in a one-player game, and the reward R(x) the payoff for a trajectory leading to x E X. A GFlowNet that samples trajectories proportionally to the rewards of their last states, i.e., PF(7 (So is thus a Luce quantal response agent. On the level individual actions at a given state s, the policy is that of Luce agent that treats F(s') the total reward accessible from s' the payoff for transition s s'.
Sn x)) o R(x),
EFlowNets learn marginalized quantal response policy. Next, show that EFlowNets Bayesian averrgin)) analogues Luce agents that marginalize out the uncertainty of the environment's 's transitions.
Define a (pure) environment strategy as an induced subgraph Genv of whose vertex set V(Genv) S S has the following properties:
If V(Genv) and s Sp. then the parent of s is in V(Genv). . If V(Gem) n Sawv. then exactly one child of s is in V(Gem)).
12

---

Published as a conference paper at ICLR 2024
If eaGeav) S Sagent then all children of are in V(Geav).
is clear from the first property that any such Geny is a tree. An environment strategy thus amounts to predetermined choice of action at every state that can be reached if the environment takes the actions chosen by the strategy. The environment policy Peny determines a distribution over environment strategies, where the child of each agent state in Gagent is sampled from the policy independently for each s, i.e.,
Pen (Genv)
Pen s).
(11)
IVV s ('CCh())VV(Gmm
The environment strategy is a source of uncertainty for the agent. Any given Geny is a tree that con- tains so and some subset XGm of the terminal states. Viewing Genv (deterministic) GFlowNet the sense of 2.1 there a unique policy pfau and corresponding state flow F on Geny that samples proportionally to the reward R restricted to XG
The following proposition shows that the optimal EFlowNet policy averages the stepwise utilities (i.e., total accessible rewards) of deterministi--eeviinmeen GFlowNets Pfan weighted by their likelihood under Pens-
Proposition Suppose that P Pagent satisfies the EDB constraints. Then, for any Sagent and s' E Ch(s),
Ps (s') s) x BG [R (5') s E v(Geav) where the expectation is taken over the distribution over strategies determined by Pens, restricted to the strategies that contain the state s.
FlowwNets and agent quantal response equilibrium. In two-player games with unadjusted re- wards R7. R2 and rewards R₃ and R₂ defined using the branching factor adjustment 9 we also have the following characterization of the optimal state flows:
(()
XXXX Nkol U[Chite) sf St Skel P 18k) i E (
RR] (x)
(12)
Σ XXXX
Py(sK( sk) Rx
Ch(sk))
ES,
where the notation (s)s) is extended to nonterminal states using the same definition (9. This is easily derived by recursion from the EDB constraints and (9) in similar way to the proof of Prop.
Because Pi(s' s) & Fi(s') ) for s S;, the expression (12) characterizes the policy P; via a form of
agent quantal response (McKelvey & Palfrey 1998), which the action probability of an agent proportional to its expected reward under future actions of the opponent (sampled from its policy) and the agent itself (here, sampled uniformly).
B PROOFS
Proposition There exists a unique pair of state flow function F and agent policy P Pagent satisfying constraints 4 (5) and (6). If Senv = 0. then this pair satisfies the detailed balance constraints
Proof of Proposition 7
If the EDB constraints are satisfied, then satisfies recurrence:
EveCn(s)) F(s')
Sagent
F(s) = Be- (s) F(s')
S Senv
(13)
R(s)
se
where the first case (s E Sagent follows from summing 4 over s'. The uniqueness of F(s) can casily be seen, e.g., by induction on the length of the longest path from s to terminal state.
Because R(x) > 0 for all x E X, and the recurrence preserves the positivity (i.e., F(s') > 0 for all E Ch(s) implies F(s) O), we have F(s) for all s. Therefore, one can recover the unique Pagent that satisties (4) jointly with via Pagent(s' (s' |
F(x')
F(s)
Finally, if Senv = 0. then constraint (5) is vacuous, and the remaining constraints exactly recover
13

---

Published as a conference paper at ICLR 2024
Proposition 2. There exist unique agent policies PI,...,Pr, and state flow functions Fi..... Fn. Rx0 such that Pt and F; satisfy the EDB constraints with respect to the EFlowNet & for all i.
Proof of Proposition As in the proof of Proposition
we give recurrence on the flows:
EseCh(s) Fi(s')
SE
F((s) =
S Sj.j #i.
(14)
Eecchhs Fy(8)
Ri(s)
SE
This recurrence uniquely determines the state flows Fj and therefore the policies P.. It remains to see that if the flows satisfy (14), then each Fi satisfies the recurrence (13 The cases s E X are clear. For the case E ESS. # observe that
S, and
sechts) F((s))((s5), Evehh()) Fj(s")
Σ F((S))((5')
Σ F(()) = S'EC((x)
Exrech(s) Fj(s")
s'ECh(s)
which coincides with the second case of the recurrence (33
Proposition 3. Suppose that in 2-player AFlowNel, the agent policies Pt, P2 and state flow func-
tions FI. F2 are jointly optimal in the sense of Prop. 2 Then the function F(s) = (2(s))((s is flow on G, i.e, satisfies the FM constraint
7. with respect to the reward R(x) (x)
Proof of Proposition R(x) for all x E X.
Because Fx(x) (x) and F2(x) R2(x) for all x E X, we have F(x)
For E S Xx, must show that F(s) = Es'ch((s) F(s'). Suppose without loss of generality that s E Sj. Then
Fi(s))
Fi(s) = Fi(5))
(i(s)
Σ
Fi(s) =2()== Σ F(()))2(s).
3'ECh(s)
s'eCh(s)
which completes the proof.
Proposition 2-player AFlowNet with alternating moves satisfying R (x(x)
(a) Suppose that the agent policies Pı, P2 and state flow functions F1, F22 are jointly optimal in the Then there exists scalar independent of x, such that for every complete
sense of Prop. 2
trajectory 5o
51
Z
Pi(s s;) (x)
I i::;
P2(si+1 St).
(10)
(b) Conversely, if the constraint (10) holds for some constant Z and policies Pi and Pa, then Pt and P2 are the jointly optimal AFlowNet policies.
+ Part (a). We first extend the definition of B; to nonterminal states: if 81 Sm s is any trajectory, define B; == Ilssisma [C((s)).
Proof of Proposition
We claim that for all states s, F2((() B.))) This holds at terminal states x, since
F (x) (x) (x())
(x) By Prop. (s) is a flow, so
1x(x)
suffices to show that (.(s) also satisfies I for X S. Without loss of generality, suppose S₁ and let sp
Si be the trajectory leading Then
Σ
Σ s'ECh(s)
(1(r))22s'')
Ch(s)) B2(s) (2())
3'ECh(s)
establishing the claim.
Returning to the proposition, rearranging factors and using the definition 9 it is necessary to show that
(x(x) TEWeS, P2(Si+1 s;)
B, (x) IiSES, P (Si11 si)
14

---

Published as a conference paper at ICLR 2024
is independent x. We have, using the above claim,
(x) Mssess: Ch(s)) Felsa1
Ri (x)) Mases P2(3 (s) Msses P1(4/41 st)
((0))
Hswes
(i
Fi(s()
Ri (x(x) Nsses Ch(ss)l
Fi (1
(166)1)
Fi(M)
(x)x) HiSESS (Ste))
Fi(s;)
Iiaes
Fi
Fi(s.)
Fi(s))
Fi(si)
= (x)
Fi (See))
Fi(s++))
is n even
isn odd
(i(s))
(s.)
= (so))
(s
20
which is independent of
Part (b). Because jointly optimal AFlowNet policies PI. P2 exist by Prop. 2 and they satisfy (10)
by part (a) of this proposition, suffices show that the constraint (10) uniquely determines P1 and P2 for all pairs of reward functions (R,, R2) for which Ri (x() (x(x) for all x X.
We prove this by strong induction on the number of states in G. The base case |S| (there is unique state which is both initial and terminal) is trivial: the products are empty and the constraint reads Z R1 (x).
Now suppose that the constraint uniquely determines P1 and P2 for all reward functions satisfy- ing Rí (2((xx = (,(x) on graphs with fewer than N states, for some N > 1, and consider an AFlowNet G (S,H) with N states, for which (10) holds and the reward functions satisfy Ri (2) (x) It is easy to see that there exists a state E S \ X such that all children of are terminal; select one such state s.
Suppose that s St. We construct new graph G' and rewards R₁, R2 by deleting the children of making $ terminal state, and modifying the reward function so that Rj (s) ExeCh(s) (s),, setting (s)
preserve (s())) (x) and setting Rx(x) (x) for all other terminal states x. Thus the graph G' is two-player AFlowNet with alternating turns and satisfying the constraint on rewards.
We claim that the constraint (TO) for G. Ri R₂ and pair of policies Pt. P2 on G implies the con- straint for G', R. R2 and the same policies restricted to the states in G'. For all terminal states in G' inherited from the constraint unchanged. For the new terminal state s, we sum the constraints on G for the children .XK E Ch(s). Letting leading to s, we have:
51
Sn = be the trajectory
K
Z
Il
Pi(sin Px) s)
Σ k=1
Ri (2(x))
I
P2(51-1 si)
k=1
Esy,S
K PI(xA 1 = B2(s) I
K
%
Pi(sit | s;)
P2(si+1 | si)
Σ
Ri(x2)
isns:e
k=
itss e.S:
k=1
Z
(i I ss) = B2(s)
Po(san | s;) (s),,,
isnayes,
which is precisely the constraint for G' at the state s. So the constraint 10 is satisfied on G'.
Since G' has fewer than N states, by the induction hypothesis, P1 and P2 are uniquely determined on G' and are therefore equal to the jointly optimal AFlowNet policies. It remains to show that P: s) is uniquely determined. Indeed, the only factor the left side of (10) that varies between
15

---

Published as a conference paper at ICLR 2024
children of is (x s), while the right side, the only such factor is R1 (x). It follows that if the constraint is satisfied, then Pi(x s) or (x),, which uniquely determines PI ().
The case S2 is analogous.
Proposition 5. Suppose that P Pagent satisfies the EDB constraints. Then, for any 8 Sugent and E Ch(s),
Pagent( (s' 5) BG [remm (s') I & V(Genv)
where the expectation is taken over the distribution over strategies determined by Penv, restricted to the strategies that contain the state s.
Proof of Proposition 5
We first note that the expression inside the expectation is well-defined, since s V(Genv) Sugent. then all children of are also in V(Genv).
Now suppose that Pagent satisfies EDB jointly with flow function F. By 4), we have P P'agem( s) o F(s'), and V(Gem) is equivalent s V(Genv) for E Sugent and s' Ch(s). Therefore, it would suffice to show that
F(s) BGam-Pa [ (s) |s V(Gemv)
for all s E S X.
To do so, show that the expression on the right side satisfies the recurrence 133) We consider
three cases:
If s Sagent, then the child set of in any Genv containing is the as its child set in G. follows that
EG |F (s) Is V((Gnv)) = BG
Σ
eeG)
5'ECh(s)
EG 8Gmm-Pan Pane
[ | v(G
s'eCh(r)
EG Pan (Fon((s) V(G
s'ECh(s)
showing the first case of the recurrence.
If s Senv, then in any Genv containing s, has a unique child s' and FGe (s) = F (s'). We decompose the expectation into terms depending on the child of s that is present Genv:
Pan p (s) | V(Geav)) =E
8 P'- (S'E (xmGm) BGm [1.Gem (s) 1s' V(Gem)]
r'EC((s)
= By (x'ss) EG Pan
[Foom (5') I V(Gew)))
which shows the second case of the recurrence. The case s X is simple, since F(s') = G (5') = R(s') for all Geny containing s.
C GAME SPECIFICATION
C.I TIC-TAC-TOF
Two players alternate between placing X tiles and tiles in a x 3 grid. If any player reaches a board with three of their pieces connected by straight line, they win. Although simplistic, tic-tac- toe has a small enough state space that the ground truth EDB-based flow values can be computed and compared to the learned values. This allows for the unique opportunity to verify that the AFlowNet has converged to the predicted stable point. The stable point can be found by recursively visiting each state in the game and backpropagating the rewards, flows, and probabilities.
16

---

Published as a conference paper at ICLR 2024
C.2 CONNECT-4
There are two players who alternate between placing yellow and red tokens (for the sake of simplic- ity, we use X tiles and tiles) in a 6 grid (6 rows, columns). Each token is placed at the top of the grid and falls to the lowest unoccupied point in the column. If any player reaches a board with four of their pieces connected tic-tac-toe: it is quite difficult for even humans to learn, although the first player has been proven to have a winning strategy (Allis) 1988). As such, is computationally infeasible to compute, or to store, the optimal policies at all states in the AFlowNet.
straight line, they win. Connect-4 has far larger state space than
D TRAINING DETAILS
For we collect trajectories as sequences of tuples (state, mask, curr-player, action, done, leg_reward):
state: the current state of the environment
mask: binary mask of legal moves over the action space
curr player: the player whose turn it is to make the action
act i on: the sampled action at the given state
done: whether the action resulted in terminal state
log.reward: the log reward if done
convolutional neural network composed of residual blocks inspired by the AlphaZero architecture (Silver et al., 2018 Thakoor et al. 2016) with a few modifications. We remove the batch normalization layers the population statistics varied too much between training and evaluation. We use only the policy head (using one for each side, e.g., playing as "X" or "O") and increase the number of filters it has recommended by Prasad et al. (2018). We replace ReLU activations by Leaky ReLU activations, reduce the number of residual blocks and reduce the number of filters in each block (128 instead of 256) as fic-tac-toc/Conneet- are simpler than chess/Go. Finally, we include single differentiable parameter log Z.
As architecture, we
The main training hyperparameters are:
jum.trajecttoiiesee erwoohh number of trajectories added to the buffer every epoch bat chesize: batch size used for training and trajectory generation num.steps: number of optimization steps per epoch
ty: the maximum capacity of the replay buffer learning.rate: learning rate for the policy network
replay.buffer.cam
learning.rate.2 2: learning rate for the log (we find that a higher value helps training)
num.residual.blocs number of residual blocks in the architecture
Specific values are included Table 2
D.I TRAININGEEVALUATION POLICY
During training, to generate the training trajectories, we sample actions using the softmax of the policy logits of the AFlowNet with a temperature coefficient of 1.5. At test time, (i.e., for the tournaments), when it is the AFlowNet's turn to play, we select the move corresponding to arg meXxs)((s) Pa(s' | ss, where is the index of the player to make a move at s.
D.2 ALPHAZERO TRAINING
AlphaZero is trained as per the specifications of Thakoor al. (2016). The batch size of AlphaZero is changed to 512 to match the batch size of AFlowNets. Training discrepancies include the number of examples gathered and retained over each iteration, which is significantly different between the AFlowNet implementation and AlphaZero. Naturally, it is quite difficult to compare AlphaZero and AFlowNets exactly because we do have an MCTS analogue. Additionally, AlphaZero trains on single transitions whereas AFlowNets with TB loss train on entire trajectories. This leads to discrepancy in what is considered a training example: a transition versus a trajectory. The number of Monte Carlo tree search iterations for AlphaZero is 25 for both tic-tac-toe and Connect-4.
17

---

Published as a conference paper at ICLR 2024
Hyperparameter
Tic-tac-toe
Connect-4
num trajectories epoch
10240
10240
batch size
512
1024
num_steps
500
250
replayybuuffer.capaccty
10240
250000
learning.rate
le-3
le-3
learning.rate.2
5e-2
5e-2
num mum.resicualbbiokk
10
15
GPU
1XRTX3090Ti
1xRTX8000
Table 2: Hyperparameters used for training the AFlowNets on on tic-tac-toe and Connect-4
Loss rate (against uniform)
X
X
MAE (Node flows)
100
X.
MAE (Edge flows)
10
0.4
Self-play
Self-play
Self-play
0.3
10-1
10-2
0.2
10
10
0.1
0.0
20
10
20
Steps x103
Steps x103
Steps x10
Figure 5: Graphs of learning performance over various training runs. (Left) The average MAE of learned node flows (not in log space) compared ground truth flows computed algorithmically. (Middle) Average MAE for learned edge flows. (Right) Loss rate the three training regimes against a random uniform opponent.
E ADDITIONAL RESULTS FROM ADVERSARIAL GAMES
CONVERGENCE OF EFLOWNETTS/FLLOWNET TO UNIQUE OPTIMUM
aim investigate whether EFlowNets/AFloNNet are capable of learning the correct flows (i.e., those corresponding to the unique optimum). The game tree of tic-tac-toe is small enough that ground truth flows and policies (for a fixed opponent and the stable-point optimum) can be computed algorithmically by backtracking recursively from terminal states.
In addition testing game-playing performance,
We train neural networks, see DD details, to evaluate the following configurations:
(1) EFlowNet with fixed stochastic opponent (policy consists of choosing each legal action with equal probability) from one perspective (e.g., always plays X). EFlowNet versus fixed stochastic opponent, learning both perspectives.
(3) AFlowNet learning using the EDB objective with off-policy self-play.
Figure 5 jillustrates the learning performance of the three tested configurations. For configura- tions, the ground truth flows/policies that satisfy the EDB constraints are learned, as evidenced by the left and middle graphs. Importantly, this even the case for training through self-play, where the AFlowNet converges the actual stable-point optimum.
Interestingly, the AFlowNet does not need to learn the exact flows to achieve strong game-playing performance. For example, here the AFlowNet is able to always win or draw against uniform agent after less than 5000 steps even though its MAE relative to the correct flows still decreases substantially in the next 20000 steps. Additionally, the EFlowNet formulation is not enough to obtain a robust game playing agent, particularly when the agent is playing against does not play well.
18

---

Published as a conference paper at ICLR 2024
Sodta
DON
AlphaZaro
Alphnderr (MC15)
1.00
0.35
gnsfform))
% Optineal Moves
0.25
0.90
0.20
0.85
0.15
0.80
0.10
0.05
0.00
0.70
5000
10000
15000
20000
25000
30000
35000
40000
45000
5000
10000
15000
20000
25000
30000
35000
40000
45000
Step
Figure 6: Graphs of learning performance over various training for AFN, DQN, SoftDON and AlphaZero. (Left) The percent of optimal moves (for TicTacToe solved through minimax) all states. (Right) Loss rate of the algorithms against random uniform opponent.
E.2 COMPARISON TO DQN AND SOFTDQN
We include additional results comparing DQN and SoftDQN to AFlowNets on TicTac'Toe in Fig. Getting standard RL algorithms to work in multi-agent settings (learning through self-play) play) is non trivial and does not work in many common RL libraries.
To remedy this, and ensure fair of comparison possible, implement DQN and its soft equivalent inside our framework (i.e. using the same environment as AFN, the same architecture, etc.). Notably, to achieve agent that could consistently beat uniform opponent, to use minimax version DQN similar to (Fan et al. 2020) for sequential games (i.e. the q-update based on the negation of the maximum q-value of the opponent). For the soft version (denoted SoftDQN), we sample trajectories using the softmax of the Q-values and similarly use the softmax for the updates (once again a minimax fashion).
necessary
E.3 TIC-TAC-TOE TOURNAMENT
To test the performance of AFlowNets against state of the art methods such as AlphaZero, we train popular open-soure AlphaZero implementation Thakoor et al. (2016) to play tic-tac-toe, pitting the agents against each other and baselines in a tournament. In the set of baselines we include uniform opponent and tree-search agen By changing the value of for the AFlowNet, we also test how the learned policy changes with varying rewards. We proceed to test the performance of AFlowNets and TB- Ta-ba AFlowNets.
Results with EDB-based A FloowNets Some selected results of the tournament are listed in Table 3 Note that AlphaZero is trained with Monte Carlo tree search (MCTS), but is tested in the tourna- ment with MCTS both and off. This ensures fair comparison of inference-tin time game-playine capabilities as AFlowNets have no such tree-search mechanism to generate policy.
It is clear from the tournament results in Table B that AlphaZero and AFlowNet agents capa- ble of perfect play in tic-tac-toe, drawing nearly every game that was played. The biggest differ- ences in performance come from playing against the uniform and tree-search agents. It is clear that AFlowNetjo performed the best, winning or drawing all games against the uniform and tree-search agents. Interestingly, while a higher A produces a better X-playing agent, the same not true for agents playing second: against the tree-search and uniform agents, a lower A corresponds to better score. As such, there may be diminishing return with higher values of d, perhaps encouraging overly-risky behaviour.
Training with MCTS seems to greatly improve the speed of convergence, as AlphaZero converges to stable Elo after only few training steps, see Figure 7 In comparison, AFlowNets require more training steps, optimization steps, and training examples reach a similar level of performance
TThe trce-search agent uses AlphaZero's value function, search depth of three, and alpha-beta pruning.
19

---

Published as a conference paper at ICLR 2024
Table 3: Selected results of AFlowNets (AFlowNet,) pitted against AlphaZero (A0) and baselines in tic-tac- toe. The agents listed the rows are playing first as X. agents listed the columns are playing second as O. Nets are trained five times with different seeds. The results of the tournament represent the mean and standard deviation of the games over the different seeds, where wins, draws, and losses are given two points, point, and zero points respectively. Each element the table is the result from the perspective of the X- playing agent in the For example, AO playing X achieved
of 44.2 #: 5.1 against the uniform agent.
x
AFlowNet AFlowNet,
AFlowNetAFlooNNeis
A0
A0+MCTS
Uniform
Tree Search
AFlowNet,
25 1
13.7
2
25
45.6 1.5
45.4
AFlowNetio
25 + 0
+ 13.7
25
25
49.8 1.1
47.6 5.4
AFlowNet:s
15 13.7
15 # 13.7
30 20.9
23.2 # 18.3
43 2.6
36 # 22.0
AO
2
25 0
35 = 13.7
25 =
4.12
50
A0+MCTS
+
25 =
38.4 =: 13.7
25 +
47,4 2.1
49.8 0.4
Uniform
2.3
6.8 a 0.5
13.8 a: 7.6
11 7.5
10.6 3.6
22.8 5.6
Tree Search
0+ 0
0 0
15 22.4
0 0+0
0.4 0.9
37.8 3.6
400
300
200
Elo score
100
AFN
100
AlphaZero
AlphaZeroMMCTS
Tree Search (d=3)
-20
50000
100000
150000
200000
250000
Training steps
Figure Elo over optimization steps while training a EDB-bDseee AelowNet agent in toc- The of
agents after the full course of training are 363.2 7.7. 12.7, 356.9 11.6, 344.3 4 4.66, and 317.6 14.3 for AFlowNetjo- AFlowNetz, AFlowNet15, AlphaZcro+MCTS, and AlphaZero respectively. Other AFlowNet agents and error bars for the haseline models are omitted for clarity.
to AlphaZero in terms of Elo. AFlowNetio achieves the highest Elo, reinforcing its tournament performance in Table 3 Again, appears that a larger À produces a AFlowNet agent, with AFlowNet achieving the lowest Elo of all AFlowNets. The AlphaZero agents also achieve high Elo scores, with AlphaZero+MCTS achieving the better score of the two.
AlphaZero converges to stable Elo after a small number of optimization steps whereas AFlowNets using the EDB constraint require an order of magnitude more steps to reach a similar Elo (about 50k steps versus 5k to 10k steps). A similar trend holds for training time, with AFlowNets requiring about times longer to reach similar Elo scores (AlphaZero+MMCTS took seconds to reach an Blo of 46 whereas the first AFlowNet to reach similar Elo of 51 took 558 seconds). While AFlowNets can certainly learn to play tic-tac-toe effectively, they clearly require far more training time and computation to achieve similar levels of performance to AlphaZero. We have not tested AlphaZero without MCTS in training, nor AFlowNets with tree search, so the comparison naturally favors AlphaZero given the power of tree search.
20

---

Published as a conference paper at ICLR 2024
Table 4: Selected results of AFlowNets (AFlowNet,) pitted against AlphaZero (A0) and random uniform baseline in Connect-4. The agents listed in rows are playing first and the agents listed playing second. AFlowNets are trained three times with different seeds. The results of the tournament represent the mean and standard deviation of the games over the different seeds, where wins, draws, and losses are given two points, one point, and zero points respectively. Each element in the table is the result from the perspective of the agent that played first in the row. For example, A0 playing first achicved score of 49.2 d: 1.8 against the uniform agent.
columns are
x O
AFlowNetz
AFlowNetjo
AFlowNet1s
A0
A0+MCTS
Uniform
AFlowNet,
0+0
5 11.2
50 0
32.8 19.4
50
AFlowNet1o
50 0
20 27.4
50 0
46.2 8.5
50
AFlowNet1s
50 + 0
35 + 22.4
50 + 0
50 + 0
50 + 0
AO
0 0
0 + 0
0 0
25 + 0
49.2 + 1.8
A0+MCTS
8.8 8.7
0.8 + 1.8
0 0
25 0
49 1.0
Uniform
0 0
+
0 0
8.4 2.6 1.2 + 1.6
Results with TB-based AFlowNets The results thus far have focused on EDB-trained agents, but is important to demonstrate the performance of TB-based agents as well. Figure 3 illustrates the Elo over three training runs with different seeds of AFlowNetjo and the baseline models. Clearly, AFlowNet1o matches the Elo of AlphaZero and converges quickly. Compared to Figure it appears that TB-based agents converge about as quickly as AlphaZero, about 10 times faster than the EDB- based agents. Interestingly, the Elo of the TB-based AFlowNets lower than the Elo of the EDB- based AFlowNets.
There appears to be little difference in the performance of a TB-trained AFlowNet with different values of A in tic-tac-toe. This is in contrast to the EDB-trained AFlowNets which seemed to be affected by the setting of A. Similarly to the EDB-based agents, almost every game in the tourna- ment was draw, with small differences between the performance of agent against the baselines dictating the differences Elo.
E.4 CONNECT-4 TOURNAMENT
We also tournament in Connect-4 against AlphaZero and uniform random baseline. Again, we vary d to test how the reward structure changes agent performance. The tournament results in Table Sallefindicate that the effect of similar the experiments in tic-tac-toe. A higher À produces a better agent, however the diminishing return in these experiments relates to reduction in benefit when increasing lambda rather than a decrease in Elo. This supports the idea that the reward structure affects the behaviour of an agent. The results of the Connect-4 tournament corroborate the Elo results of Figure 3 The Elos of agents AFlowNet,, AFlowNetjp- and AFlowNet,s are 1190.8 64.2, 1700.1 60.0, and 1 1835.3 154.9. Clearly, AFlow is the best agent.
21


Reviews:
[{"review_id": "w9ZH8Z0Lz4", "reviewer": "Reviewer_QVYG", "summary": "The paper proposes Expected Flow Networks (EFlowNets) extending GFlowNets to stochastic environments. Stepping forward, Adversarial Flow Networks (AFlowNets) is introduced for adversarial environments like two-player zero-sum games. The authors show that EFlowNets outperform other GFlowNet formulations in tasks such as protein design and AFlowNets outperform AlphaZero in Connect-4.", "questions": "1. Can you provide more clear description of the differences between stochastic environments and common environments?\n2. What is the motivation of extending GFlowNet to stochastic environments and adversarial environments? And what is the general advantage of GFlowNet-based methods compared to RL methods in both environments?\n3. How do you think about the potential of AFlowNet compared to RL methods considering the limitation in the proposed algorithms currently?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper introduces EFlowNets and AFlowNets as extensions of GFlowNets, which provide solutions for generative modeling in stochastic and adversarial environments respectively. \n2. The paper provides theoretical analysis and derives training objectives for EFlowNets and AFlowNets. The experiments conducted demonstrate the effectiveness of the proposed methods. The demo is also interesting.", "weaknesses": "1. The differences between stochastic environments and common environments for GFlowNet may not be stated clearly.\n2. The line of extension is similar to that in reinforcement learning. However, not enough comparisions to RL algorithms are provided in the experiments in both environments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cql6RwR7nb", "reviewer": "Reviewer_g2xq", "summary": "This paper proposes expected flow networks, which extend generative flow networks to stochastic environments. They also extend their formulation to adversarial environments for two-player zero-sum games. Experiments show that the proposed methods achieve promising empirical performance.", "questions": "1. From Figure 3, it seems that the proposed method is much more computation heavy, can you show the computation time requires for each step of each method? Also how does the computation time scale with the size of the problem for each method?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper proposes a new formulation for learning in stochastic environments, which ensures that a set of desiderata can always be satisfied. The propose modification is intuitive and elegant. It can also be generalized to zero-sum game in a straightforward way, making it a widely applicable formulations. The writing is mostly clear and it gives a good introduction.", "weaknesses": "The paper still requires solid background knowledge on generative flow networks and it is not very friendly to non-expert.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wpqV6Vdh8b", "reviewer": "Reviewer_cwh7", "summary": "This paper argues that it can address limitations of previous attempts for extending GFlowNets to stochastic transition dynamics by expected flow networks, which leads to meaningless solution. This paper also studies adversarial flow networks, to tackle the tree-structured MDP.", "questions": "Please check the weakness part.", "limitations": "", "rating": 3, "confidence": 5, "soundness": 1, "presentation": 2, "contribution": 1, "strengths": "This paper studies an interesting setting about GFlowNets in tasks with stochastic transition dynamics.", "weaknesses": "- It is mentioned that \"We propose expected flow networks, ... generalizing GFlowNets on tree-structured state spaces.\" In the simpler case of trees instead of non-tree DAGs, why don't you just apply maximum entropy reinforcement learning (MaxEnt RL) approaches? It has been extensively demonstrated in previous GFlowNets papers that when the DAG degenerates to a tree, it is indeed equivalent to MaxEnt RL approaches (e.g., Soft Q-learning), which can natually handle stochastic worlds. Therefore, it makes little sense for only EFlowNets to be only evaluated in tree-structured state spaces.\n\n- The performance and explanation of EFlowNets does not make sense. As described in the paper, this paper aims to extend (Pan et al., 2023; Bengio et al., 2023) to handle more general cases considering stochasticity in the transition dynamics, i.e., extend GFlowNets -- which aims to sample proportionally to a reward function $R(x)$, i.e., $\\pi(x) \\propto R(x)$, to the settings with stochastic transition dynamics.\nHowever, the solution learned by EFlowNets is incorrect as demonstrated in Figure 1(a). Although it is able to solve $p$ (with a solution of around $0.66$) in this case while $p$ cannot find satisfiable solutions in Stoch-GFlowNets, it leads to sampling $x1$ with probability $p(x_1) \\approx 0.33 \\neq 2/10$, $p(x_2) \\approx 0.33 \\neq 3/10$, $p(x_3) \\approx 0.306 \\neq 1/10$, and $p(x_2) \\approx 0.034 \\neq 4/10$. Although $p$ is solvable in EFlowNets, the learned sampling policy fails to realize the goal of GFlowNets (sampling proportionally from the reward function), and learns a meaningless sampling policy. Consequently, EFlowNets do not address the limitations of Stoch-GFlowNets in some cases where satisfiable solutions are unavailable. However, this claim is made throughout the paper, which is an overstatement in this context.\n\n- The statement seems incorrect -- \"Stochastic GFlowNets directly apply the training algorithms applicable to deterministic GFlowNets (e.g., DB) to the augmented DAG $G$, with the only modification being that the forward policy $P_F$ is free to be learned only on agent edges, while on environment edges it is fixed to the transition function.\" In stochastic environments, the transitions dynamic is unknown, and after I checked the Stochastic GFlowNets paper, I found that it indeed learns the forward policy and the underlying transition dynamics (which is not fixed, unknown and is learned by experiences).\n\n- In the \"Violated desiderata in stochastic GFlowNets\" section, a very important property is missed (which is satisfied by Stochastic GFlowNets with solvable cases but EFlowNets unfortunately violated) -- the correct sampling behavior, which means that GFlowNets function well in stochastic environments which sample proportionally to the reward function. Failures to satisfy this basic and fundamental requirement will lead to meaningless solutions. \n\n- EFlowNets bear great similarity to (Yang et al., 2023), however, the latter aims to extend Decision Transformer to stochastic environments in the realm of RL. Taking the expectation is correct in RL, since the objective of RL is to maximized the expected discounted future rewards. In addition, EFlowNets also bear similarity to Section 3.3.2 about stochastic rewards in (Bengio et al., 2023), which is mentioned about stochasticity in the rewars (not the transition dynamics), which is a case studied in (Zhang et al., 2023). Therefore, it does not make sense to apply the methodology in about learning an expectation as in RL (Yang et al., 2023) to GFlowNets with the hope to tackle stochasticity in transition dynamics as discussed in (Bengio et al., 2023).\n\n- It is mentioned that trajectory balance is used for branch-adjusted AFlowNets. However, most practical games in multi-agent systems are actually partially observable (e.g., StartCraft II), which renders stochasticity in the transition dynamics. TB leads to large variance as mentioned in the text and in experiments in (Madan et al., 2023). Therefore, it seems to be more appropriate to apply this with DB or SubTB (since one of the claims for SubTB is to improve credit assignment). \n\n- It is mentioned that \"This data defines a fully observed sequential game\", which can limit its practical applicability in a wider range of applications with partial observation. \n\n- A very relevant paper extending GFlowNets to the multi-agent setting  (Li et al., 2023) is not cited and discussed. Since both paper study a very similar setting, it is worth comparing the approach with FCN and CFN in (Li et al., 2023), or at least discussed thoroughly. \"Generative Multi-Flow Networks: Centralized, Independent and Conservation. Yinchuan Li, Haozhi Wang, Shuang Luo, Yunfeng Shao, Jianye Hao. 2023.\"\n\n- It is unclear why experiments in Section 4.1 employ very large $\\beta=10, 30$ which is different from (Jain et al., 2022), which leads to the case of a tree with very peaky rewards. In addition, it is worth investigating how the approach behave under the traditional $L_1$ error metric, which measures how well EFlowNets learn compared with other approaches.\n\n- Why the two-play games correspond to a tree instead of a graph? There can be many parent states for a state actually.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vRlsdAUsyN", "reviewer": "Reviewer_C2iS", "summary": "The paper proposes two extensions of generative flow networks (GFlowNets): expected flow networks (EFlowNets), designed to operate in stochastic environments, and adversarial flow networks (AFlowNets) for (two-player) zero-sum games. They experimentally demonstrate that EFlowNets outperform earlier approaches for protein design, and AFlowNets outperform AlphaZero in simple zero-sum games.", "questions": "What was the previous state of the art method for the protein design task considered in Section 4.1? Is it included in the current comparisons?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "GFlowNets have shown promise in developing robust agents in challenging Markov decision processes. The paper provides a novel and natural formulation of GFlowNets to stochastic and adversarial environments. Unlike an earlier attempt by Pan et al., the new formulation satisfies a number of desirable theoretical properties, which is also reflected in the experimental results. For the adversarial setting I am not aware of any prior comparable formulations. Moreover, the experimental results also seem overall promising.", "weaknesses": "First, in terms of the experiments, the current results do not go far enough at least in the zero-sum setting. In particular, the games tested (tic-tac-toe and connect-4) are not large enough in order to make solid conclusions regarding the scalability of the method. It would be much more convincing if the authors used this new formulation to make progress on benchmarks that are otherwise elusive using prior techniques. Overall, I believe that the paper would significantly benefit from having more experiments and on larger benchmarks. It would also expect the adversarial formulation to capture partially observable settings (such as Poker); I do not see any significant obstacles in extending the methodology to partially observable settings. Such extensions would significantly strengthen the contributions of the paper. Besides those issues with the experiments, the other concern is that the new formulations are relatively straightforward, and there is not much conceptual or algorithmic novelty in deriving them based on earlier approaches. Overall, although the results are promising, they seem to be in a rather preliminary stage.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)