Policy-Based Self-Competition for Planning Problems
Authors: Jonathan Pirnay
Quirin Göttl
Jakob Burger
Dominik Gerhard Grimm
Venue: ICLR 2023 poster (2023)
Keywords: reinforcement learning
alphazero
self-competition
self-critical
gumbel
mcts

Abstract: AlphaZero-type algorithms may stop improving on single-player tasks in case the value network guiding the tree search is unable to approximate the outcome of an episode sufficiently well. One technique to address this problem is transforming the single-player task through self-competition. The main idea is to compute a scalar baseline from the agent’s historical performances and to reshape an episode’s reward into a binary output, indicating whether the baseline has been exceeded or not. However, this baseline only carries limited information for the agent about strategies how to improve. We leverage the idea of self-competition and directly incorporate a historical policy into the planning process instead of its scalar performance. Based on the recently introduced Gumbel AlphaZero (GAZ), we propose our algorithm GAZ ‘Play-to-Plan’ (GAZ PTP), in which the agent learns to find strong trajectories by planning against possible strategies of its past self. We show the effectiveness of our approach in two well-known combinatorial optimization problems, the Traveling Salesman Problem and the Job-Shop Scheduling Problem. With only half of the simulation budget for search, GAZ PTP consistently outperforms all selected single-player variants of GAZ.

Published as a conference paper at ICLR 2023
POLICY-BASED SELF-COMPETITION FOR PLANNING PROBLEMS
Jonathan Pirnay':2, Quirin ,öttl', Burger' & Dominik G. Grimm 1.2
'Tehhiical University of Munich, Campus Straubing for Biotechnology and Sustainability 2 "Weihenstephan- Triesdorf Trrissoo University of Applied Sciences (jonathan, pin pirnay, Nominik.r grrim) (hswt... de, tum. de}
ABSTRACT
AlphaZero-type algorithms may stop improving on single-player tasks in case the value network guiding the tree search is unable to approximate the outcome of an episode sufficiently well. One technique to address this problem is transform- ing the single-player task through self-competition. The main idea is com- pute a scalar baseline from the agent's historical performances and to reshape an episode's reward into a binary output, indicating whether the baseline has been exceeded or not. However, this baseline only carries limited information for the agent about strategies how to improve. We leverage the idea of competiiinn and directly incorporate historical policy into the planning process instead of its scalar performance. Based on the recently introduced Gumbel AlphaZero (GAZ), we propose our algorithm GAZ 'Play-to-Plan' (GAZ PTP), in which the agent learns to find strong trajectories by planning against possible strategies of its past self. We show the effectiveness of our approach in two well-known combina- torial optimization problems, the Traveling Salesman Problem and the Job-Shop Scheduling Problem. With only half of the simulation budget for search, GAZ PTP consistently outperforms all selected single-player variants of GAZ.
INTRODUCTION
One of the reasons for the success of AlphaZero (Silver et al. 2017) is the use of a policy and value network to guide the Monte Carlo tree search (MCTS) to decrease the search trec's width and depth. Trained on state-outcome pairs, the value network develops an 'intuition' to tell from single game positions which player might win. By normalizing values in the tree to handle changing reward scales (Schadd et al. 2008) [Scrittwieeer et al.) 2020). AlphaZero's 's mechanisms can be applied to single-agent (or single-player) tasks. Although powerful, the MCTS relies on value approximations which can be hard to predict (van Hasselt et al., 2016 Pohlen et al. 2018). Furthermore, without proper normalization, it can be difficult for value function approximators to adapt to small improve- ments in later stages of training. In recent years there has been an increasing interest in learning sequential solutions for combinatorial optimization problems (COPs) from knowledge via deep reinforcement learning. Particularly strong results have been achieved with policy gradient meth- ods by using variants of self-critical training (Rennie al.) 2017 Kool al. 2018 Kwon et al.) 2020) where it is avoided to learn a value function at all. By baselining the gradient estimate with the outcome of rolling out a current or historical policy, actions are reinforced by how much better (or worse) an episode is compared to the rollouts. Something similar is achieved in ACTSSbased algorithms for single-player tasks by computing a scalar baseline from the agent's 's historical perfor- mance. The reward of the original task is reshaped to binary +1 outcome indicating whether an episode has exceeded this baseline or not (Laterre et al. 2018, [Schmidt et al. 2019 Mandhane et al.) 2022). This self-competition brings the original single-playe playerr task closer two-player game and bypasses the need for in-tree value scaling during training. The scalar baseline against which the agent is planning must be carefully chosen it should neither be too difficult nor too easy to out- perform. Additionally, in complex problems, a single sealar value holds limited information about the instance at hand and the agent's strategies for reaching the threshold performance.
In this paper, we follow the idea of self-competition in AlphaZero-style algorithms for determin- istic Lingle-player sequential planning problems. Inspired by the original powerful 'intuition' of

---

Published as a conference paper at ICLR 2023
AlphaZero to evaluate board positions, propose to evaluate states in the value function not by comparing them against a scalar threshold but directly against states at similar timesteps coming from historical version of the agent. The agent learns by reasoning about potential strategies of its past self. We summarize our contributions as follows: (i) We assume that in a self-competitive framework, the scalar outcome of a trajectory Ç under some baseline policy is less informative for tree-based planning than ('s intermediate states. Our aim is to put the flexibility of rollouts in self- critical training into a self-competitive framework while maintaining the policy's information in intermediate states of the rollout. We motivate this setup from the viewpoint of advantage baselines, show that policy improvements are preserved, and arrive at a simple instance of gamification where two players start from the same initial state, take actions in turn and aim to find a better trajectory than the opponent. (ii) We propose the algorithm GAZ Play-to-Plan (GAZ, PTP) based on Gum- bel Alpha7ero (GAZ), the latest addition to the AlphaZero family, introduced by (Danihelka et al.) (222).. An agent plays the above game against a historical version of itself to improve a policy for the original single-player problem. The idea is to allow only one player in the game to employ MCTS and compare its states to the opponent's ss to guide the search. Policy improvements obtained through GAZ's tree search propagate from the game to the original task.
We show the superiority of GAZ PTP over single-playe variants of GAZ on two COP classes, the Traveling Salesman Problem and the standard Job-Shop Scheduling Problem. We compare GAZ. PTP with different single-player variants of GAZ, with and without self-competition. We consistently outperform all competitors even when granting GAZ PTP only half of the simulation budget for search. In addition, we reach competitive results for both problem classes compared to benchmarks in the literature.
RELATED WORK
Gumbel AlphaZero In GAZ. Danihelka et al. (2022) redesigned the action selection mechanisms of AlphaZero and MuZero (Silver et al. 2 et al. 2020). At the root node, actions to explore are sampled without replacement using the Gumbel- trick (Vieiral Kool et al. 2019b). Sequential halving (Karnin et al., 2013) is used to distribute the search simulation budget among the sampled actions. The singular action remaining from the halving procedure is selected as the action to be taken in the environment. At non-root nodes, action values of unvisited nodes are completed by value interpolation, yielding updated policy. An action is then selected deterministically by matching this updated policy to the visit count distribution (Grill et al. 2020). This procedure the- oretically guarantees a policy improvement for correctly estimated action values, both for the root action selection and the updated policy at non-root nodes, Consequently, the principled search of GAZ works well even for a small number of simulations, as opposed to AlphaZero. which might perform poorly if not all actions are visited at the root node. Similarly to MuZero, GAZ normalizes action values with min-max normalization based on the values found during the tree search to handle changing and unbounded reward scales. However, if for example node value is overesti- mated, the probability of good action might be reduced even when all simulations reach the end of the episode. Additionally, value function approximations might be challenging if the magnitude of rewards changes over time or must be approximated over long time horizons (van Hasselt et al.) 2016 Pohlen al. 2018).
Schrittwieser
Self-critical training Rennie et al. (0117) introduce self-critical training, policy gradient method that baselines the REINFORCE (Williams) 1992) gradient estimator with the reward obtained by rolling out the current policy greedily. As a result, trajectories outperforming the greedy policy are given positive weight while inferior ones are suppressed. Self-critical training eliminates the need for learning a value function approximator (and thus all innate training challenges) and reduces the variance of the gradient estimates. The agent is further provided with an automatically controlled curriculum to keep improving. Self-critical methods have shown great success in neural combinato- rial optimization. Kool et al. (2018) use a greedy rollout of a periodically updated best-so-far policy as baseline for routing problems. Kwon et al. (2000) and Kool et al. 2019a) bundle the return of multiple sampled trajectories to baseline the estimator applied to various COPs. The idea of using rollouts to control the agent's 's learning curriculum is hard to transfer one-to-one to MCTS-based algorithms, as introducing a value network to avoid full Monte Carlo rollouts in the tree search was exactly one of the great strengths in AlphaZero (Silver al. 2017).
2

---

Published as a conference paper at ICLR 2023
Self-competition Literature is abundant learning by creating competitive environments for (practical) single-player problems, e.g. Bansal et al. p; Sukhbaatar et al. (2018) : Zhong et al.
2019); Xu & Lieberhem (2020); Wang et (2020); Göttl al. (2022). Reward mechanisms based on ceef-competition for AiphaZZeo--type algorithms are different but comparable to self-critical train- ing in policy gradient methods. A scalar baseline is computed from the agent's historical perfor- mance against which the current agent needs to compete. A reward of #1 is returned at the end of an episode, depending on whether the trajectory performed better than the baseline, eliminating the need for value scaling and normalization. An iterative process of improvement is created by contin- uously or periodically updating the baseline according to the agent's 's performance. As in self-critical training, the baseline provides the agent automatically with the right curriculum to improve. We use the term self-competition in the context of competing against historical performance to distinguish from self-play as in board games, where usually the latest agent version is used. Ranked Reward (Laterre et al.) (2018) stores historical rewards a buffer which is used to calculate a threshold value based on predetermined percentile. Mandhane et al. (2022) use an exponential moving average- based scheme for the threshold and apply self-commetition to maximize a constrained objective. Beloborodov al. (2020) use similar approach as Ranked Reward, but also allow non-binary wards in 11,, 1j. The described self-competition based on combining historical performances cannot differentiate between problem instances. If an instance's difficulty is higher than usual, in extreme cases the agent might obtain reward of 1 even though the found solution is optimal, thus adding significant noise the reshaped reward (Bello et al. 2016 Laterre et al. 2018).
3 PRELIMINARIES
3.1 PROBLEM FORMULATION
We consider undiscounted Markov decision processes (MDPs) of finite problem horizon T with state space S, a finite action space A, a reward function r: S x A - R, and an initial state distribution Pn- The goal to find state-dependent policy π which maximizes the expected total reward
Ge := Beg E Eco (:100)
Er(st,ai)
where 17t (-|s;) is the distribution over possible trajectories S. = (St, Ot...., .,...,,,,.11 ay sT) ob- tained by rolling out policy from state 8t timestep & up the finite horizon T. We use the subscript & in actions and states to indicate the timestep index. For an action O ~ (-(ss)) in the trajectory, the state transitions deterministically to 8t41 F(st, ae) according to some known de- terministic state transition function F: S x A + S. We shortly write a₃St := F(st, az) for a state transition in the following. With abuse of notation, accumulated return of a trajectory. As usual, we denote by
write r(Gi) =ET0 "(scti, a++1) for the
V* (st) ;= (( [r(S))] (s), == r(su, 0z) + E (( [r(S++)] A (s; az) == (st, - (s:))
the state-value function, action-value function and advantage function w.r.t. the policy x. Further- more, for two policies т and μ. we define
TT (st, s)) = E Be (-1s)) (r(S))-((C) (-())))))))
(1)
as the expected difference in accumulated rewards taken over the joint distribution of 17 (-(se) and (-1s(). We define QT+H(ss s/; ax) : r(), + (=*H(a 8f) and A $/; ar)
QT s/: az) Va s)) analogously.
The following lemma follows directly from the definitions. It tells us that we can work with the policy μ as with any other scalar baseline, and that policy improvements are preserved. A proof is given in Appendix 1 A.I
Lemma Let n, and p be state-dependent policies. For any states 8t, of E S and action as E A. we have
A AT(s(, = TMP (st, at), and
(2)
Σ ((arss)) (sx)=
Σ
# ((a.ls:) (a.lss)) s/: av) V=. s))
(3)
4,
a
3

---

Published as a conference paper at ICLR 2023
3.2 MOTIVATION FOR THE -WAYEL GAME
We now consider MDPs with episodic rewards, i.e., we assume r(st, ax) - 0 for L < T 1. The policy target and action selection within the search tree in GAZ is based on the following policy update: At some state 8, given logits of the form logit" (a) for an action a predicted by a policy n, an updated policy TGAZ obtained by setting
feg (a) logit" (a) + (AA
(4)
Here, is some monotonically increasing linear function and (s)
VT is an
advantage estimation, where (s) is value approximation based on the output of value network and (s, a) is a Q-value approximation coming from the tree search statistics (and is set to (T(s) for unvisited actions). Note that (4) differs from the presentation in Danihelka et al. (2022) due to the additional assumption that a is linear, which matches its practical choice (see Appendix A.2 for derivation). The update (4) is proven provide policy improvement but relies on the correctness of the value approximations V*.
Our aim is to couple the ideas of self-critical training and self-competition using a historical policy. Firstly, the baseline should adapt the difficulty of an instance via rollouts in self-critical train- ing. Secondly, we want to avoid losing information about intermediate states of the rollout as when condensing it to scalar value.
Consider some initial state 80 Po. policy π, and a historical version μ of x. Let ggre (So, 1T 1T-1. be the trajectory obtained by rolling out μ greedily. We propose to plan against Grreedy timestep by timestep instead of baselining the episode with r(ch i.e., we want to approximate VT (st, s() for any state sc. By Lemma
1
we have for any policy x'
Σ [r((alss)0' 2 (s.)
Σ n (aels: ((aell=)Q**((( ( s(;aa) 2 VT.H(s))()). (5)
So if a improves policy baselined by μs, then x' improves π in the original MDP. Furthermore, (st, az) in (4) can be swapped with an approximation of Á (st, s/; az) for the update in GAZ. Note that "**"ss, s Ec,,c; (r(S))-r(( r(()) = Ec,cc [sgn(r(C.) - r(()) |r(Ge) r(G Es- pecially in later stages of training, improvements might be small and it can be hard to approx- imate the expected reward difference (r((e) - r(())-- Thus, we switch to binary reward as in self-competitive methods and arrive
TT sgn
(St, 60) E Reg " (+1a2) (gn(r(G)--r((s)) Chon"" (1))))
the final target output of the value network in the self-competitive formulation. Note that (6) uncou- ples the network from the explicit requirement to predict the expected outcome of the original MDP decide if in a more advantageous state timestep t than μ (for further details, see Appendix D
We can define Qig analogously to (6) and obtain an improved policy x' via
logit" (ar) :- logit (a.) + ( (st, s/za,) - V (st, K())
4
GAZ PLAY-TO-PLAN
4.1 GAME MECHANICS
Given the original MDP, the above discussion generalizes to a two-player zero-sum perfect informa- tion game with separated states: two players start with identical copies s) and s s-1 respectively. of an initial state 8o ~ Po- The superscripts and indicate the first (max-) and second (min-) player, respectively. Player 1 observes both states (s) sn ) chooses an action oj and transitions to the next state of a] Afterwards, player -1 observes (5),,5)) chooses action ag -1 and transitions to state #1 % % -1 Then, player 1 observes ( chooses action at. and in this manner both players take turns until they arrive at terminal states s/ and ST Given the resulting trajectory Cp for player p (1,-10 -1.. the outcome of the game is set 1 if r(G)) 2 r(C- (player wins) and 2 = -1 otherwise (player loses). In case of equality, player wins to discourage player -1 from simply copying moves.
4

---

Published as a conference paper at ICLR 2023
Algorithm 1: GAZ Play-to-Plan PTPZ.PPP) Training
Input: Po: initial state distribution; :arena: set of initial states sampled from Po
Input: 0 S 7 < 1: self-play parameter
Init policy replay buffer M < and value replay buffer Mv <- Init parameters 0, for policy net me: S + AA and value net V S x 8 1-1.1]
Init 'best' parameters f foreach episode do
Sample initial state so Po and set si 8o for p
Assign learning actor to player position: +- randomm {1, 1}}
To
with probability ?
Set greedy actor's policy μ for O.....
T&B
with probability 1
do
for player p = 1, -1 do if player p * then
Take greedy action af according to policy pus?) and receive state 5441
else
Perform policy improvement with MCTS using (i -) and aa(-) I)) for player p
where in tree, player -p samples (resp. chooses greedily) actions from μ Receive improved policy [s()),, action of and new state 4/11
Store i Ix (x()) in M
Have trajectories ÇP (s) ag. ....... ................................ -- 17 11 for players p E {1,-1)
r(r((²) 2 r((-1))
game outcome from perspective of player
-1 else
Store tuples s, 2) and (s, 1/41 in My for all timesteps
Periodically update 8 EseeJmm (r(GGracdt) r (S6,,
groedy
>> 0
4.2 ALGORITIM
Algorithm summarizes our approach for improving the agent's performance, and we provide an illustration in the appendix in Figure 2 In each episode, 'learning actor' improves its policy by playing against a 'grredy actor', which is a historical greedy version of itself. We elaborate on main parts in the following (more details can be found in Appendix B}.
Network and training An agent maintains a state-dependent policy network ne: S > AA and value network V S x S + [-1, parameterized by 0 and v. respectively, where A,A is the prob- ability simplex over actions and V,, serves as a function approximator of (6). The agent generates experience in each episode for training the networks by playing the game in Section 4.1 against frozen historically best policy version тąe of itself. Initially, and 0 are equal. The networks are trained from experience replay in AlphaZero, where store value targets from the perspective of both players and only policy targets coming from the learning actor.
Choice of players The learning actor and greedy actor are randomly assigned to player positions at the beginning of each episode. The greedy actor simply chooses actions greedily according to its policy Taz. In contrast, the learning actor chooses actions using the search and action selection mechanism of GAZ to improve its policy and dominate over иTn. We found the policy to become stronger when the learning actor makes its moves sometimes after and sometimes before the greedy actor. At test time, we fix the learning actor the position of player 1.
GAZ tree search for learning actor The learning actor uses MCTS to improve its policy and dominate over the greedy behavior of Tgz. We the AlphaZero variant (as opposed MuZero) in Danihelka et al. (2022) for the search, i..., we do not learn models for the reward and transition dynamics. The search tree built through several simulations, usual, each consisting of the phases
5

---

Published as a conference paper at ICLR 2023
selection, expansion, and backpropagation. Each node in the tree is of the form . = =s', "s',s-1_ k), consisting of both players' states, where k E {1. -1] indicates which player's 's turn it is. Each edge (N.a) a) is node paired with certain action a. We apply the tree search of GAZ similarly to two-player board game, with two major modifications:
(i Choice of actions: For the sake of explanation, let assume that 1, i.e., the learning actor takes the position of player 1. In the selection phase, an action is chosen at any node as follows: If the learning actor is move, we regularly choose an action according GAZ's tree search rules, which are based on the completed Q-values. If it is the greedy actor's turn, there are two ways to use the policy Tyæ: we either always sample, or always choose greedity an action from Ta.. By sampling a move from T8B, the learning actor is forced to plan not against only one (possibly suboptimal) greedy trajectory but also against other potential trajectories. This encourages exploration (see Figure 1 in the experimental results), but single action of the learning actor can lead to separate branches the search tree. On the other hand, greedily choosing an action is Seredy computationally more efficient, as only the states in the trajectory S0, are needed for comparison in the MCTS (see Appendix 6 for notes on efficient implementation). However, if the policy Tœa too strong or weak, the learning actor might be slow improve in the beginning.
We refer to the variant of sampling actions for the greedy actor in the tree search as GAZ PTP 'sampled tree' (GAZ PTP ST) and as GAZ PTP "greddy tree' (GAZ PTP GT) in case actions are chosen greedily.
(ii) Backpropagation: Actions are chosen as above until a leaf edge (a,a) with N = (s s k) is reached. When a leaf edge (N, a) is expanded and k = -1 11, the learning actor is to move in the new node Nr = (s as aa_-_1 1). We proceed by querying the policy and value network to obtain (e")") and v (s 1). The new node / is added to the tree and the value approximation is backpropagated up the search path. I = 1, i.e. the turn of the greedy actor in N' = (as! s- -1), we only query the policy network Tan (}- choose an action ā from it (sampled or greedy), and directly expand the edge (N, a). In particular, we do not backpropagate value approximation of state pairs where the greedy actor is to move. Nodes, where it's the greedy actor's turn, are similar to afterstates (Sutton & Barto 2018), which represent chance transitions in stochastic environments. We further illustrate the procedure in Appendix[B..
Arena mode To ensure we always play against the strongest greedy actor, we fix at the beginning of the training a large enough 'arena' set of initial states Jaremu ~ Po on which periodically To and THE are pitted against each other. For each initial state so E Tarenas the policies Te and та2 are unrolled greedily to obtain the trajectories $6,00 and <greedy respectively. We replace 8 with 0 if (r(Careedl) r((0,,00)) ) 0.
ExgEJamn
Self-play parameter The parameters 0, R might be initialized disadvantageously (worse than uniformly random play), so that the learning actor generates no useful experience while maintaining a greedy policy worse than zgn. We especially experienced this behavior when using small number of simulations for the tree search. To mitigate this and to stabilize training, we switch to self play-pla in an episode with a small nonzero probability 7, i.e., the greedy actor uses the non-stationary policy my instead of Tga.
EXPERIMENTS
We evaluate our algorithm on the Traveling Salesman Problem (TSP) and the standard Job-Shop Scheduling Problem (JSSP). For this purpose, we train the agent on randomly generated instances learn heuristics and generalize beyond presented instances.
Experimental goal There is a plethora of deep reinforcement learning approaches for training heuristic solvers for COPs, including Bello et al. (2016); Deudon et al. 2) Kool et al. (2018); Xing et al. (2020); da Costa al. (2020); Kool et al. (2022) for the TSP and Zhang et al. (2020); Park ct al. (2021a b): Tassel et al. (2021) for the JSSP. Most of them are problem-specific and especially
concentrate on how optimize (graph) neural network-based architectures, state representations,

---

Published as a conference paper at ICLR 2023
and reward shaping. Additionally, learned solvers often focus on short evaluation times while cepting a high number of training instances. Our main goal is to show the performance of GAZ PTP compared with applying GAZ in single-player way. Nevertheless, recent learned solvers to put our approach into perspective. An in-depth comparison is difficult for several reasons. (i) Running MCTS is slower than single (possibly batch-wise) rollout of a policy network. As we do not aim to present an optimized learned solver for TSP or JSSP, we omit com- parisons of inference times. (ii) The network architecture is kept simple be adjustable for both problem classes. (iii) We give only episodic rewards, even if there would be (canonical) intermedi- ate rewards. Furthermore, we do not include heuristics in state representations. (iv) Eventually, the agent starts from zero knowledge and runs for a comparably lower number of episodes: 100k for TSP (for comparison, Kool et al. (2018) trains on 128M trajectories), 20k for JSSP (40k trajectories in Zhang et al. (2020)).
also present results of
5.1 SINGLE-PLAYER VARIANTS
We compare our approach GAZ PTP with the following single-player GAZ variants:
GAZ Single Vanilla We apply GAZ for single-agent domains to the original MDP. For the value target, we predict the final outcome of the episode, i.e., we train the value network V;: S - R on tuples of the form (st, r(Ga)) for trajectory Ço (Sg, Gp. ..... .......,0r-... 0r-11 sT). We transform the Q- values with a min- max normalization based on the values found inside the tree search to cope with different reward scales MCTS (Schrittwieser et al. 2020 Danihelka et al. 2022). For details, see Appendix C.I.3
GAZ Single N-Step Same as 'GAZ Single Vanilla', except: we bootstrap N steps into the future for the value target, as used in MuZero (Schrittwieser et al. 2020) and its variants (Hubert et al.] 2021 Antonoglou al. (022). As do not assume intermediate rewards, this is equivalent to predicting the undiscounted root value of the search tree N steps into the future. We set N = 20 in all instances.
GAZ Greedy Scalar This is a self-competitive version with scalar baseline, which can differen- tiate between instances as self-critical setting. the start each episode, full greedy rollout So greedy from the initial state so is performed with a historical policy to obtain an instance-specifi baseline R = (Cgrrdyy ) E TR. At test time, max R, learning actor's outcome) is taken as the result in the original MDP. A listing of the algorithm is provided in Appendix C.I.4 C.1.14
5.2 GENERAL SETUP
We outline the common experimental setup for both TSP and JSSP. Full details and specifics can be found in Appendix C.T
GAZ MCTS
We closely follow the original work of Danihelka et al. (2022) for the choice of the function in (4) and the completion of Q-values. The number of simulations allowed from the search tree's 's root node critical since a higher simulation budget generally yields more accurate value estimates. Although two edges are expanded in single simulation in the modified tree search of GAZ PTP, the learning actor considers only one additional action in the expansion step because the greedy actor's moves are considered environment transitions. Nevertheless, single-player variants twice as many simulations at the root node as GAZ PTP in all experiments.
grant the
Network architecture The policy and value network share a common encoding part f: S - Rd mapping states some latent space Rd, A policy head g: Rd + A.A and value head l:: 12d x Rd - [-1, are stacked on top of f such that (s) = (f and (z s') = (s). problems. ff is based on the Transformer architecture Vaswani et al. 2017 and the policy head uses a pointing mechanism as in (Bello et al. 2016) and (Kool et al. 2018). For GAZ PTP and all single-player variants, the architecture of / is identical, and g, h similar (see Appendix C.1.5
((s')) f(). For both
7

---

Published as a conference paper at ICLR 2023
Table 1: Results for TSP and JSSP. 'Num Sims' refers to the number simulations starting from the root of the search tree.
Method
Num Sims
Obj.
Gap
Obj.
Gap
Obj.
Gap
T
20
71 50
100
Optimal (Concorde)
3.84
0.00%
5.70
0.00%
7.76
0.00%
Kool et al. 2018 (gr.)
3.85
0.34%
5.80
1.76%
8.12
4.53%
GAZ Single Vanilla
200
3.86
0.58%
6.06
6.36%
9.87
27.15%
TSP
GAZ Single N-Step
200
3.86
0.58%
5.92
3.98%
9.14
17.72%
GAZ Greedy Scalar
200
3.87
0.83%
6.02
5.74%
11.21
44.43%
GAZ PTP
100
3.84
0.19%
5.81
1.90%
8.16
5.11%
GAZ PTP GT
100
3,84
0.17%
5.78
1.55 %
8.01
3.16%
GAZ PTP ST
greedy!
3.86
0.74%
5,90
3.63%
8.35
7.60%
GA7. PTP GT
greedy!
3.86
0.61 %
5.82
2.15%
8.10
4.32%
15 x
20 x 20
30 x 20
Upper Bound
1228.9
0.0%
1617.3
0.0%
1921.3
0.0%
Zhang et 2020
1547.4
26.0%
2128.1
31.6%
2603.9
33.6%
GAZ Single Vanilla
100
1585.8
29.0%
2062.4
27.5%
2579.1
34.4%
JSSP
GAZ Single N-Step
100
2038.4
66.0%
3604.6
123.0%
4111.2
114.6%
GAZ Greedy Scalar
100
1447.9
17.8%
4721.5
191.9%
6184.3
222. 1%
GAZ PTP ST
50
1432.0
16.6%
1973.2
22.0%
2539.1
32.3%
GAZ PTP GT
50
1455.4
18.4%
1961.4
21.3%
2506.7
30.6%
GAZ PTP ST
greedy' greedy!
1505.7
22.6%
1993.0
23.2%
2601.8
35.6%
GAZ PTP GT
1478.8
20.3%
2003.7
23.9%
2584.2
34.6%
5.3 RESULTS
Results for TSP and JSSP are summarized in Table For TSP, we also list the greedy results of the self-critical method Kool al. (2018). They train similar attention model autoregressively with
greedy rollout baseline. For JSSP, we include the results of the L2D method of Zhang et al. (2020). who propose a single-agent approach taking advantage of the disjunctive graph representation of JSSP. There exist optimized approaches for TSP and JSSP, which achieve even better results. Since is not our aim to present a new state-of-the-as art solver, an exhaustive comparison not necessary. All experiments, except for the robustness experiments below, are seeded with 42.
Traveling Salesman Problem The TSP is a fundamental routing problem that, given a graph, asks for node permutation (a complete tour) with minimal edge weight. We focus on the two- dimensional Euclidean case in the unit square [0, 1]2 C R22 and train on small- to medium-size sized instances with 20, 50 and 100 nodes. Tours are constructed sequentially by choosing one node to visit after the other. We run the agent for 100k episodes (see Appendix C.2 for further details). We report the average performance of GAZ variants on the 10,000 test instances of Kool et al. 2018). Optimality gaps are calculated using optimal solutions found by the Concorde TSP solver (Apllegaee et al. 2006). Both GAZ PTP ST and GAZ PTP GT consistently outperform all single- player variants, and obtain strong results even when simply unrolling the leamned policy greedily (see 'Num Sims = greedy' T.. GAZ PTP GT yields better results than GAZ PTP ST across all instances, especially when rolling the learned policy greedily. While all methods perform well on n = 20, the single-player variants strongly underperform on n = 50 and n = 100. GAZ. 100.
Greedy Scalar fails to improve early in the training process for
Job-Shop Scheduling Problem The JSSP is optimization problem in operations research, where we are given & jobs consisting of individual operations, which need to be scheduled on m machines. We focus the standard case, where there is bijection between the machines and the operations of job. The objective is to find a schedule with a minimum makespan, i.e., the time
We greedily unroll the policy which trained with 100 (resp. 50 for JSSP) simulations.
8

---

Published as a conference paper at ICLR 2023
TSP 50
JSSP 15x15
JSSP 20x20
GAZ
20
Groady Scalar
24
GAZ Single Varill
.35
1.5
UaZ Single Ft-Sepp
-0-
18
25
16
14
10000
20000
50000
2000
4000
5000
5000
10000
4000
6000
8000
Figure 1: Mean training performance on TSP and JSSP, run with distinct seeds (42, 43, 44, 45). Shades denote standard errors. We omit the results for GAZ Single N-Step on JSSP for readability.
when all jobs are finished (see Appendix C.3 for details). The size of a problem instance is denoted iteratively choose unfinished jobs of which
by x (jobs x machines). To construct schedule, to process the next operation. The agent is run for 20k episodes. We report results on instances of medium size 15 15. 20 x 20, and 30 20 of the well-known Taillard benchmark set (Taillard 1993), consisting of 10 instances for each problem size. Optimality gaps are calculated with respect to the best upper bounds found in the literature (see Appendix C.3.3p. As for TSP, our method out- performs all single-player variants of GAZ. In contrast to TSP, the performance of GAZ PTP ST and GAZ PTP GT is comparable. Due to the reduced network evaluations, GAZ PTP GT is generally more favorable. GAZ Greedy Scalar yields strong results only for 15 x 15 but fails to learn on larger instances, similar to GAZ Single N-Step.
Reproducibility We further evaluate the robustness and plausibility on four different seeds for TSP n = 50 and JSSP 15 x 15 and 20 x 20 in Figure T To lower the computational cost, we reduce the number of episodes on TSP to 50k and JSSP to TOk, with a simulation budget of 100 for TSP (70 for JSSP) for single-player variants, and 50 for TSP (35 for JSSP) for GAZ PTP. The different seeding leads to only small variations in performance for TSP. JSSP is more challenging. Again, observe that GAZ PTP outperforms the single-player variants across all seeds. Especially, GAZ PTP escapes bad initializations early in the training process and becomes stable. The in-tree sampling of GAZ PTP ST encourages exploration, leading to swift early improvements.
Value estimates as baselines By comparing pairs of states to guide the tree search, we provide the network some freedom to model the problem without relying explicitly on predicted expected objectives. In Appendix D we compare approach with using value estimates of historical policy as baselines the advantage function of GAZ's tree search.
Limitations In contrast to GAZ PTP GT, the search space increases exponentially for the variant GAZ. PTP ST. and an additional network evaluation is needed for Tan (-) in each MCTS simulation (see Appendix [B.6). Nevertheless, our empirical results show that both GAZ PTP variants perform well in general with small number of simulations. In this paper, we only consider problem classes with constant episode length. However, the methodology presented extends to varying episode lengths: Once player finishes, only its terminal state is considered in the remaining tree search (i.e., within the two-player game, the unfinished player keeps its turn). Furthermore, even though GAZ's s policy improvements propagate from the two-player setup to the original single-player problem by Lemma I an improved policy does not necessarily imply improved greedy behavior. Especially in later stages of training, it can take thousands of steps until the distribution of σe is sharp enough for updating the parameters 8
6 CONCLUSION
We introduced GAZ PTP. self-competitive method combining greedy rollouts as in self-critical training with the planning dynamics of two-player games. The self-critical transformation of a de- terministic single-plaer task does not alter the theoretical policy improvement guarantees obtained through the principled search of GAZ. Experiments on the TSP and JSSP confirm that our method learns strong policies in the original task with low number of search simulations.

---

Published as a conference paper at ICLR 2023
7 REPRODUCIBILITY STATEMENT
We provide information about network architectures, hyperparameters and training details in the appendix. Our code in PyTorch (Paszke al. 2017) available on https://githun. com/
gr 1cimmlle www.mmm.bbm......mmmmmmmmmm..... httpppooocyy--aeeesss---------oe
ACKNOWLEDGMENTS
This work was funded by the Deutsche Forschungsgemminschaatt (DFG, German Research Founda- tion) 466387255 within the Priority Programme "SPP 2331: Machine Learning in Chemical Engineering". The authors gratefully acknowledge the Leibniz Supercomputing Centre for provid- ing computing time on its Linux-Cluster.
REFERENCES
Ioannis Antonoglou, Julian Schrittwieser, Sherjil Ozair, Thomas K. Hubert, and David Silver. Plan- ning in stochastic environments with learned model. International Conference on Learning Representations, 2022.
David L. Applegate, Robert E. Bixby, Vasek Chvatal, and William Cook. The traveling salesman problem: a computational study. Princeton university press, 2006.
Trapit Bansal, Jakub Pachocki, Szymon Sidor, Ilya Sutskever, and Igor Mordatch. Emergent com- plexity via multi-agent competition. 1rXiv:1710.03748, 2017.
Irwan Bello, Hieu Pham, Quoe V. Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. International Conference on Learning Representationss 2016.
Dmitrii Beloborodov, Alexander E. Ulanov, Jakob N. Foerster, Shimon Whiteson, and A.I. Lvovsky. Reinforcement learning enhanced guantum-inspired algorithm for combinatorial optimization. Machine Learning: Science and Technology, 2:025009, 2020.
Paulo da Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. Asian Conference on Machine Learning, 2020.
Will Dabney, Georg Ostrovski, David Silver, and Rémi Munos. Implicit quantile networks for distributional reinforcement learning. In International conference machine learning, pp. 1096- 1105. PMLR, 2018
Ivo Danihelka, Arthur Guez, Julian Schrittwieser, and David Silver. Policy improvement by planning with gumbel. International Conference on Learning Representations, 2022.
Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin
Rousseau. Learning heuristies for the tsp by policy gradient. International conference on the integration of constraint programming, artificial intelligence, and operations research, 2018.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chupter of the Association for Computational Linguisties: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume I (Long and Short Papers), pp. 4171-4186. Association for Computational Linguistics, 2019.
Quirin Göttl, Dominik G. Grimm, and Jakob Burger. Automated synthesis steady stead state continuous processes using reinforcement learning. Frontiers of Chemical Science and Engineering, 16:288- 302, 2022.
Yean-Bastien Grill, Florent Altché, Yunhao Tang. Thomas Hubert, Michal Valko, loannis Antonoglou, and Rémi Munos. Monte-carlo tree search as regularized policy optimization. Inter- national Conference Machine Learning, 2020.
10

---

Published as a conference paper at ICLR 2023
Dan Hendrycks and Kevin Gimpel. Gaussian enror linear units (gelus). orXhv:1606.084151 2016.
Thomas Hubert, Julian Schrittwieser, loannis Antonoglou, Mohammadamin Barekatain, Simon Schmitt, and David Silver. Learning and planning in complex action spaces. International Con- ference on Machine Learning, 2021.
Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. International Conference Machine Learning, 2013.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv: 2014.
Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn solve routing problems! Inter- national Conference on Learning Representations, 2018.
Wouter Kool, Herke van Hoof, and Max Welling. Buy 4 reinforce samples, get baseline for free! International Conference on Learning Representations, 2019a.
Wouter Kool, Herke van Hoof, and Max Welling. Stochastic beams and where to find them: The gumbel-top-k trick for sampling sequences without replacement. International Conference on Machine Learning. 2019b.
Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic pro- gramming for vehicle routing problems. arXiv:2102.11756, 2022.
Yeong-Dat -Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances Neural Information Processing Systems, 2020.
Alexandre Laterre, Yunguan Fu, Mohamed K. Jabri, Alain-Sam Cohen, David Kas, Karl Hajjar, Torbjørn S Dahl, Amine Kerkeni, and Karim Beguir. Ranked reward: Enabling self-play rein- forcement learning for combinatorial optimization. Advances in Neural Information Processing Systems 31, 2018.
Kevin Leyton-Brown Brown and Yoav Shoham. Essentials of game theory: A concise multidisciplinary in- troduction (Synthesis lectures on artificial intelligence and machine learning). volume 1. Morgan & Claypool Publishers, 2008
Amol Mandhane, Anton Zhernov, Maribeth Rauh, Chenjie Gu, Miaosen Wang, Flora Xue, Wendy Shang, Derek Pang. Rene Claus, Ching-Han Chiang, Cheng Chen, Jingning Han, Angie Chen, Daniel Mankowitz, Jackson Broshear, Julian Schritwieser,, Thomas Hubert, Oriol Vinyals, and Timothy Mann. Muzero with self-competition for rate control in vp9 video compression. arXiv:2202.06626, 2022.
Junyoung Park, Sanjar Bakhtiyar, and Jinkyoo Park. Schedulenet: Learn to solve multi-agent scheduling problems with reinforcement learning. S.t1::20000005:000 2021a.
Junyoung Park, Jaehyeong Chun, Sang Hun Kim, Youngkook Kim, and Jinkyoo Park. Learning to schedule job-shop problems: representation and policy learning using graph neural network and reinforcement learning. International Journal of Production Research, 59:3360-3377 2021b.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. Conference Neural Information Processing System, 2017.
Tobias Pohlen, Bilal Piot, Todd Hester, Mohammad Gheshlaghi Azar, Dan Horgan, David Bud- den, Gabriel Barth-Maron, Hado Van Hasselt, John Quan, Mel Večerík, Matteo Hessel, Remi Munos, and Olivier Pietquin. Observe and look further: Achieving consistent performance on 2018.
atari.
Steven J. Rennie, Etienne Marcheret, Youssef Mroueh, Jerret Ross, and Vaibhava Goel. Self-critical sequence training for image captioning, IEEE Conference on Computer Vision and Pattern Recog- nition, 2017.
11

---

Published as a conference paper at ICLR 2023
Maarten P.D. Schadd, Mark H.M. Winands, H.J. van den Herik, Guillaume M.J.B.. Chaslot, and Jos W.H.M. Uiterwijk. Single-player monte-carlo tree search. International Conference on Com- puters and Games, 2008.
Dan Schmidt, Nick Moran, Jonathan S. Rosenfeld, Jonathan Rosenthal, and Jonathan Yedidia. Self- play learning without a reward metric. D.Xiv:/912.07577 2019.
Julian Schrittwieser, loannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, and David Silver. Mas- tering atari, go, chess and shogi by planning with learned model. Nature, 588:604-609 2020.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lillicrap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. Mastering the game go without human knowledge. Nature, 550:354-333 359, 2017.
Sainbayar Sukhbaatar, Zeming Lin, Ilya Kostrikov, Gabriel Synnaeve, Arthur Szlam, and Rob Fer- gus. Intrinsic motivation and automatic curricula via asymmetric self-play. 2018.
Richard Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction, volume 2. MIT press, 2018
Eric Taillard. Benchmarks for basic scheduling problems. European Journal of Operational Re- search, 64:278-285, 1993.
Pierre Tassel, Martin Gebser, and Konstantin Schekotihin. A reinforcement learning environment for job-shop scheduling. arXiv:2104.037600 2021.
Hado P Hasselt, Arthur Guez, Matteo Hessel, Volodymyr Mnih, and David Silver. Learning values across many orders of magnitude. Advances in Neural Information Processing Systems 29, 2016.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Informa- tion Processing Systems 30, 2017.
Tim Vieira. URL reservoir-sampling.
Hui Wang, Mike Preuss, Michael Emmerich, and Aske Plaat. Tackling morpion solitaire with alphazero-like ranked reward reinforcement learning. 2020 22nd International Symposium on Symbolic and Numeric Algorithums for Scientific Computing (SYNASC), 2020.
Qiang Wang, Bei Li, Tong Xiao, Jingbo Zhu, Changliang Li, Derek F. Wong, and Lidia Chao. Learning deep transformer models for machine translation. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 1810-1822, Florence, Italy, July 2019. Association for Computational Linguistics. doi: 00.18653/v1/19-1111
Ronald J. Williams. Simple statistical maddient-followingg algorithms for cennectioiistrriinffcemmmmm learning. Machine learning, 8:229-254 256,,566611 1992.
Zhihao Xing, Shikui Tu, and Lei Xu. Solve traveling salesman problem by monte carlo tree search and deep neural network. MXXi:2000500687) 2020.
Ruiyang Xu and Karl Lieberherr. Learning self-play agents for combinatorial optimization prob- lems. The Knowledge Engineering Review, 35, 2020.
Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Yan Liu. Do transformers really perform badly for graph representation? Advances Neural Information Processing Systems, 34:28877-28888 2021.
Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay S. Tan, and Xu Chi. Learning to dis- patch for job shop scheduling via deep reinforcement learning. Advances in Neural Information Processing Systems, 2020.
12

---

Published as a conference paper at ICLR 2023
Fangwei Zhong, Peng Sun, Wenhan Luo, Tingyun Yan, and Yizhou Wang. Ad-vat+: An asymmetric ducling mechanism for learning and understanding visual active tracking. IEEE transactions on pattern analysis and machine intelligence, 43(5):1467-1482, 2019.
A PROOFS
A.1 PROOF OF LEMMA 1
Lemma: Let n. it and be state-dependent policies. For any states St, 8 E and action de E A,
have
A (5(8; = A ar), and
Σ #(aels)) (8t, an) (*(s)) = Σ #(aels)) s/i ai) Va.u(s s))
42
a
Proof: We recall the definitions for the sake of clarity:
VT st) = E (l (r((t) - r(() (-
(Te s/: = r((), az) V-W st)
(s at) = (T) se) VT (st,
Note that
T (1 [r((c)] (ss (e [r(()]
(8)
( [r(G)),
(11)))))))
by the law of iterated expectations and because the realization of a trajectory following does not depend on μ and vice versa. Hence by linearity expectations
(*((s)) (s()) = Cawn"(1ss)) (r(Ge r(()) = (st, (1s)()))))
(10)
and it follows that
AT (St,
Q" U1) V=(8))
(11)
Q7 (st, 01) - VH((1) (V) - VM(si))
(12)
(1) + ((((s)))) - V2(5) - (V*(s)) - VV((())
(13)
r(st, az) (a 5/) VT. 5t)
(14)
@T s/; V (st, s/)
(15)
(st, s/3 at)
(16)
13

---

Published as a conference paper at ICLR 2023
Furthermore, we have
Σ ((alss))(* ai) - (s))
F(a +
V (a(ss)) - (*)))
(17)
((ar ((a))s) + (arst) (#(6))
(18)
+ +V((s()) V*((s))
#(aclv)) (r(8)) + V*
(19)
=Qrin
+V*(51)) (s(
Σ a(a (x) ((a
(20)
Σ
क ((cesss (s)
de
=VP(4))
F(a (ss (V* vs(()) (((())
(21)
Σ
7(a ((Q - (T st).
(22)
a
A.2 DERIVATION OF THE LOGIT UPDATE
In Danihelka et 2022), the improved policy aGAZ is obtained by the logit update
logit"ész (a) == logit" (a) + aQ" as)
(23)
Subtracting the constant o (s)()) does not alter the subsequent softmax-output the logits, so we equivalently set
logit"(uz(a) (a) logit" (a) (Q"" (s)
lincar
(agit"(a) + (s(( v'*(s))
(24)
logit (o)
(25)
B ADDITIONAL ALGORITHM DETAILS
B.1 A NOTE ON SELF-PLAY IN THE TWO-PLAYER GAME
The mechanics of the proposed two-player game differ from classical board games such as chess or Go, as a player's action does not influence the opponent's state. We can interpret trajectories in the original MDP as strategies in the game: if some trajectory gives a higher final reward than trajectory 3, its corresponding strategy weakly dominates strategy 8 (Leyton-Brown & Shoham, 2008]. This desired and means that playing a will always yield an outcome z at least as good as playing B, no matter what the opponent does. Usually, in AlphaZero-type self-play for board games, both players choose their moves utilizing MCTS. By limiting the tree search to the learning actor, can distill even incremental policy improvements to the policy network effectively.
B.2 MODIFIED TREE SEARCH
We provide a schematic view of the proposed game in Figure 2 and an illustration of the modi- fied selection, expansion and backpropagation in Figure
As outlined in Section 4.2 we do not
14

---

Published as a conference paper at ICLR 2023
1
1
0
0
0
81
8T
TT
We
Vv
Figure 2: Schematic view of the proposed game in an example instance of the Traveling Salesman Problem: The learning actor is player 1 (solid outline, blue), the greedy actor is player -1 (dashed outline, red). The learning actor chooses moves via MCTS, taking into account the states of both players, whereas the greedy actor moves greedily with respect to only its own state.
(s (s',a-1)
GAZ with xp, V,
(a'a'
a a-'o=
(a'ot, ā
1s
(b'a's',
(8)
(b'a's1, ba
V2
Figure 3: Example MCTS for the learning actor, when sampling actions for the greedy actor: In nodes with solid lines (blue), the learning actor (player 1) is to move, and in nodes with dashed lines (red), the greedy actor (player -1) is move. In the selection phase (solid arrows), an action is selected in solid nodes according to the search principles of GAZ, based To and the completed Q-values. In nodes with dashed lines, an action is sampled from Tga. Suppose the dashed edge (A) is expanded in the expansion phase, then it is the greedy actor's 's turn in the following node: an action is sampled from Tae (ā (á='s- ') and the corresponding edge (B) is immediately expanded as well. Only then is the predicted value of the following solid node backpropagated through the search path.
evaluate state pairs with V, in nodes where it's the greedy actor's turn. This due to computa- tional efficiency. Suppose the greedy actor is player 1,, and it is the greedy actor's turn in node N == (as* -1). which was added to the tree in expansion step. By the modified tree search, an action is sampled from Ts=(s As the policy only depends on the player's state, Taa 11 -1) for any state 5² without additional
can be reused for the action sampling in node (5² network evaluations, as the value function does not need to be queried. This can reduce the number of network evaluations in subsequent simulations.
This is different from the experiments in Stochastic MuZero (Antonoglou et al. 2022). where the au-
thors report significantly improved results for AlphaZero on Backgammon and 2048 when Q-value learned for afterstates (chance nodes). For GAZ PTP, we did not experience notable improvements and trade the learned Q-value for increased computational efficiency.
For evaluation at test time, the greedy actor's moves are not sampled in the tree search but chosen greedily to increase the search tree's depth.
B.3 A NOTE ON THE ARENA MODE
As only the sign of the reward difference ((o,,ro)-((aa is considered to compute the outcome of the game, and not its magnitude, training non-stationary policy through self-play can exhibit
15

---

Published as a conference paper at ICLR 2023
behavior where the overall performance of a policy in the original MDP gradually degrades, though the agent gets better at beating itself. In the optimal case, we would like to replace the frozen parameters 8 with 8, if
E Eso ((10)) > Exo "i and (r0)))((6))
This cannot be guaranteed alone by the binary reward in our self-competitive framework. We settle for a fixed arena set Jasena on which the policies are pitted greedily, to ensure an improved greedy actor and avoid cycling performance due to stochasticity far as possible.
B.4 REPLAY BUFFER
Given trajectory CO = (of; ug T- 1: s..) for player p E (1, (1,-1). training data stored in replay buffers the end of an episode as follows: For the value network, the final game out- come z is bootstrapped from the perspective of both players, i.c. we store tuples (s), 2) and (sT 18411:11 -2). For the policy network, we store tuples (I only for the learning actor I [1,-1}, where I (s() is the improved policy obtained through the GAZ tree search at state sy
B.5 LOSS FUNCTIONS
We train the value network by minimizing the squared error (V'(s, 2)² for sampled tuple (s, s', in the replay buffer, and the policy network by minimizing the Kullback-Leibler divergence (I((((s) (s)) for a tuple (s))).
B.6 EFFICIENT IMPLEMENTATION OF GAZ PTP GT
Algorithm iis general formulation of our method encompassing both variants in which the greedy actor samples actions in the search tree in one (GAZ PTP ST) and chooses actions greedily in the other (GAZ PTP GT). For GAZ PTP GT, only states of the greedy actor encountered in the - s47), are needed in the MCTS for the learning actor. Furthermore, the policy and value network share in practice encoding part f: S Rd such that (s = hs) f(s')) for a value head h: R x g + [- 1] (see Section 5.2). Hence, at the beginning of an episode, S0.7,3 can be obtained once in advance of the tree search, the policies and T& are independent. The states so...., S can be batched, and their latent representations (sn),...., [( E IR can be stored in memory, effectively reducing the number network evaluations in each search simulation from two (as desired in network-guided MCTS).
trajectory ggeedy
60,5, = (so,
C EXPERIMENTAL DETAILS
C.1 GENERAL SETUP
C.1.1 TRAINING LOOP
All algorithmic variants fit into the asynchronous training loop commonly used for MuZero, where learning process receives generated trajectories, stores them in a replay buffer, and performs training steps for the network. Multiple playing processes generate trajectories from initial states randomly sampled on the fly, using periodically updated network checkpoints from the learning process for MCTS. We generate experience with 100 playing processes and update the network checkpoint every 100 training steps in all variants.
C.1.2 GAZ MCTS
Given node A in the search tree, denote ((a) the visit count of the edge (N a) for action a. We follow Danihelka et al. 2002)) for the choice of the monotonically increasing linear function o in and set
(
(Cvisit + max N(b)) Cscale q.
b
16

---

Published as a conference paper at ICLR 2023
Algorithm 2: GAZ Greedy Scalar Training
Input: Po: initial state distribution
Input: : set of initial states sampled from
Init policy replay buffer Mr < and value replay buffer Mv <-
Init parameters 0, for policy net m S - AA and value net V,: S x R - 1-1,1]
Init 'best' parameters g foreach episode do
Sample initial state 80
Po
Perform greedy rollout using aga and obtain R <- r(50,=g0
for t 0, - do
Perform policy improvement with MCTS using (+ R) and policy mo(-)
Receive improved policy (s;),, action a, and new state 8p4-1
Store [T,, in Mr
Have trajectory Ç - (50; 0o...... 8T-1; -1-1
if r()) 2 R
b outcome as reshaped binary reward
else
Store tuples (st, 2) in My for all timesteps t
Periodically update 0 + +0 1f Ef Eacu
(r(Cgr000))
r (Soprog > 0
We set the constants to Cvisit 50 and Cscale = 1.0, which has shown be stable across various simu- lation budgets (Danihelka et al., (202)). We complete the vector Q-values using the authors' value interpolation proposed in their appendix: For every unvisited action, the Q-value approximation in 4 is set V. where
1 1+ I+E,N(1)
NO) Es, SL N(b) (b)) a, S.L. N(a)>0
Σ {(a)((a)
V
(26)
Here, V is the value approximation of node N coming from the value network. We abuse the notation by omitting states (resp. state pairs for GAZ PTP), as (26) is used in all GAZ variants. In particular, unvisited actions are given zero advantage
C.1.3 GAZ NORMALIZATION
Rewards in single-player tasks usually have different scales and are not limited to +1 We follow Schrittwieser al. 2020): Danihelka al. 2022),, and perform min-max normalization in GAZ Single Vanilla and GAZ Single N-Step (prior to rescaling by σ)) on the vector of completed Q- values with the values observed the tree up that point. L.c., the maximum value is given by max ((s, a) (and analogously for the minimum value). This pushes normalized advantages into the interval 1]
C.1.4 GAZ GREEDY SCALAR
We provide listing of the training algorithm for GAZ Greedy Scalar in Algorithm 2
C.1.5 GENERAL NETWORK ARCHITECTURE
Feed-forward In the following, a feed-forward network (FF) always refers to a multilayer percep- tron (MLP) with equal input and output dimensions and one hidden layer of four times the input dimension, with GELU activation (Hendrycks & Gimpel 2016).
State encoding We model a sate-enc network f: S + Rd. followed by a policy head g: Rdd A,A and state-value head h, which is of the form h: Rd Rd [-1, 1] for GAZ
17

---

Published as a conference paper at ICLR 2023
РTP. For both TSP and JSSP, f is based the Transformer architecture and its underlying multi- head attention (MHA) layers Vaswani et al. 2017). For some state s E S, the network f outputs a 0m where á E IRd and å; R are latent representa- The network architecture of f is identical for GAZ PTP
concatenation of vectors f() = [8; ai:....
tions of the state and actions a...... am
and all single-player variants (see C.2.3 and C.3.4).
Value head The value head consists of an MLP with two hidden layers of size d with GELU activation for TSP (and three hidden layers of size 2d for JSSP). The input and output of the MLP differ between variants:
GAZ PTP: We input a concatenation 3| Rdd of latent state vectors for both players. The output is mapped to [-1, 1] via tanh-activation.
GAZ Greedy Scalar: We input concatenation [s'; R) RR+1, where R E is the outcome of the greedy rollout. As in GAZ PTP, the output is mapped to [-1, 1] via tanh- activation.
GAZ Single Vanilla/N-Step: Only the latent state Rd serves as the input, with linear output.
Policy head For the policy head g. the logit for an action as E fai...., am computed using pointing mechanism based on the attention of å and the ā; 's similarly to (Bello et al. 2016) and (Kool et al. 2018):
We compute (sidgle-head) attention weights u Um E C,
C via
(WQ3)
U3 = C' tanh
(27)
Vd
with constant C 10 and learnable linear maps Wº, W'; Rd -R The weight u, interpreted as the logit for the probability of action a; and is set to -oo for infeasible (masked) actions.
In GAZ. PTP, the above process performed with w (f + instead of 8, where y = SHA (a; a....., ām)) is transformation of the vector š through a layer of single-head attention (SHA) with 8 as the only query, and keys a....., am- This is to simplify the task of aligning the state encoding f for the value and policy head, as in GAZ PTP the value head operates two separate state encodings. The same design choice did not make any difference GAZ Greedy Scalar/Single Vanilla/N-Ste Step,
removed it to speed up computation.
C.1.6 HYPERPARAMETERS
Arena episodes are played every 400 episodes in GAZ PTP and GAZ Greedy Scalar. In all exper- iments, the replay buffer holds data of the latest 2000 episodes. We set the self-play parameter to 0.2. We use Adam (Kingma & Ba 2014) as optimizer, with constant learning rate of 10-1 sampling batches of size 256 at each training step. Gradients are clipped to unit Lo-norm.
C.2 TSP
C.2.1 ENVIRONMENT
An initial state su given by n nodes, where su {# constructed sequentially by picking one node to visit after the other, iteratively completing partial tour. particular, actions are represented by (unvisited) nodes. The agent decides from which node it starts the tour.
Fn S [0, C An ordered tour is
We take a relative view at timestep t > and represent state (partial tour) for t > by a tuple (4,, stant Fr,end, X; { Lt,,-) .). where I, is the length of the current partial tour, Lt.start = a--1 is the last node in the partial tour, Ft,end = au is the first chosen node (and must be eventually returned to) and X, is the remaining set of unvisited nodes from which the next action is picked. The terminal state 8y is a complete solution with Xy = 0. The negative length of the full tour is given as reward the end of the episode (and zero rewards in between). All tour lengths
18

---

Published as a conference paper at ICLR 2023
scaled by division with v2n (the supremum of possible tour length with nodes in the unit square).
C.2.2 DATA GENERATION AND TRAINING
Initial states for training are uniformly sampled on the fly. We fix 300 states for the arena set Jarem which is identical for GAZ. PTP and GAZ. Greedy Scalar. During training, the model is evaluated periodically on a fixed validation set of 100 states to determine the final model. The final model is evaluated on the 10,000 instances of Kool et al. (2018), which were generated with the random seed 1234. The agent is run for 100k episodes, keeping a ratio of the number of played episodes to the number of optimizer steps of approximately the number of input nodes, but for comparability, we train it from scratch for each E {20, 50, 100)- We sample (at most) 16 actions without replacement at the root GAZ's search tree. The simulation budget in the tree search is 100 for our approach and 200 for all single-player variants.
0. In. The network architecture is independent of
We augment training data by applying random reflection, rotation, and linear scaling within the unit square to states sampled from the replay buffer.
C.2.3 STATE ENCODING NETWORK
The state encoding network consists of sequence-to-sequeeeee Transformer architecture similar to the encoder in Kool et al. (2018). We use latent dimension of d = 128 in all TSP experiments. The network is composed of the following components:
Learnable lookup embeddings Eloken E Lend Esturt ind gend-ind in Rdd
Affine maps Wilen, W/num; R + Rd and W/node, R² + Rd.
A simple stack of five Transformer blocks with eight heads in the self-attention and layer normalization before the MHA and the FF (Wang et al.) 2019). The structure of Trans- former block summarized in Figure 4
We illustrate the encoding procedure in Figure (1, F2 starts endd X, ( Ft, -...))). construct input sequence
For an intermediate state 8t
=
(Eooken w Wmom (n - (), Wmode (ser ) + E iat w-noee (Ier Wnodeeeee,nd Wande (zt,, (..,)).... Wrode (It.,, )).
+ Frend-ind
The sequence element corresponding to tokken is token representing the state, similar to the class token in natural language processing (NLP) (Devlin et al. 2019). The two-dimensional nodes are affinely embedded into Rd As Transformer architectures are invariant to sequence permutations by design, we add the learnable lookup embeddings Esttant ind gend ind to the start and end nodes to indicate them. This is comparable to position embeddings in NLP. For an initial state 8o, we use Wlen(() (0) for the second sequence element. Further, there are no start and end nodes in the initial state yet, Wroode ( W/node (n).
use the learnable embeddings Estart gend instead of the affine embeddings
The sequence is passed to the stack of Transformer blocks. For each attention head and pair of nodes œ, in the sequence, we add a spatial bias wr || y112 + by E R to the attention weight corresponding to x, y, similarly in Graphormer architectures (Ying et al. 2021
As outlined in C.1.5 f eventually outputs fst) = [3; āj: an where & is the first output sequence element corresponding to the state token Eioken and ā; corresponds to the output sequence element of the i-th remaining node Wrode (xx,))
The main structural difference to Kool al. (2018) is that in our case the latent representation of state is not computed autoregressively. but is re-done at each state from the partial tour length and two-dimensional coordinates of remaining nodes.
19

---

Published as a conference paper at ICLR 2023
(4.)
W y
Normilication
Plytat
W Lian gatan-oo
Transtormar block
W (Feyta
Washd (Feeze) graedind
W
NHA
(rlnl( (2te)
41
F1yol
W (m))) (2l)))
8g
81
A
Figure 4: (A) Structure a Transformer block with pre-normalization. We use layer normalization for TSP. The Transformer block takes in sequence of elements in .2d and outputs sequence in Rd of the same length. (B) Schematic view of the relative state encoding for TSP experiments: The agent initially chose to start the tour with the node at the bottom (red). In an intermediate state st. the last node in the partial tour is the current start node st.ttt The node Zt,end corresponds to the initial node in the tour, as the agent eventually must return to it to complete the tour. A sequence in I2 is constructed from the state and passed through stack of Transformer blocks. The output sequence elements corresponding to the state token Eloken and the unvisited nodes constitute the output of the network f.
C.3 JSSP
C.3.1 PROBLEM FORMULATION
In the standard JSSP, we are given set of k: jobs J (. each consisting of m operations which need to be scheduled on m machines. Each job j. is a permutation (or,))"= of the machines, where 0s, {1...., . indicates which machine the 1-th operation of job needs to run. Finishing an operation takes some processing time Pi, E (0, 1]. The operations a job must run in order (precedence constraints), a machine only process operation time, and there is no preemption. The objective is to find a schedule with minimum makespan.
C.3.2 ENVIRONMENT
A schedule must satisfy all precedence constraints, and there is a bijection between operations of job and the m machines. Thus, we can represent a schedule by (not necessarily unique) sequence of jobs Jim where j: E J is an unfinished job of which the next unscheduled operation should be scheduled at the earliest time possible. In particular, we can represent feasible actions in the environment by the set of unfinished jobs, limiting the number of possible actions to k. Note that a timestep in the environment corresponds to the /-th chosen action (unfinished job), and not equal to the passed processing time in the schedule.
state 8t is given by a tuple
((cr,)) (ee, (.)
where
Gr E R2 is the finishing time of the latest scheduled operation on the I-th machine ('machine availability").
6t, E R>0 is the finishing time of the last scheduled operation of a job ji Cjobb availabil- ity'), and
Jr jobs').
S is the subset of jobs with unscheduled operations ('unfinished
In particular, we have Co.1 0. co,: = 0 and Jo = J at the initial state 80- Let ē miny Cr, in the following. The negative makespan max; Ct,1 is given as a reward at the end of the episode (and zero rewards in between). Similarly to the TSP environment, with 100. so that for all problem sizes the makespan lies roughly in (0, 1). We illustrate the state representation in Figure
scale the final makespan by division
20

---

Published as a conference paper at ICLR 2023
Buch
Wa (Gy - 8e GL5 Be 9. - 22)
(03 60 i. eo By (fo)
J2
js
sooll (0)
po 19
1o (3) mot (M
1)
(2,
W Pamtnng (3) promeitinn (1p))))
meseonooon wommoaani 1/
pocomnn (8)
Machine
3
1
2
2
W ( (1): pipmalion (2):
panemaso (3) p.a3
W (Pparaii (2); poppration (3):)ss))
W ( pandinn
([]
(3))
Machine
Transtormrr block
Machine
A
612
8, Ct2
C1,1 time
Processing
31
Juscy
65 Ct.3
Figure 5: (A) Exemplary Gantt chart of an unfinished schedule, illustrating the relative state repre- sentation for ISSP: We assume an instance with three jobs f1 J2 and three machines. The tuple below a job indicates on which machines its operations must run. In the depicted unfinished sched- ule, all three operations of ju, the first operation of j2, and the first two operations of js have been scheduled. The schedule can be represented by the sequence (J2, J1, J1. J1. Ja. Dashed lines in- dicate examples of machine and job availability times. (B) Latent representations for the unfinished jobs j2, are obtained by passing a sequence of operations to the first stack of Transformer blocks. Already scheduled operations masked. The ouput tokens corresponding Etoken used as latent job representations and form part of the sequence on which a second Transformer network operates.
Table 2: Best solutions for Taillard instances from the literature, "*" means the solution is optimal.
TaO1
Ta02
Ta03
Ta04
Ta05
Ta06
Ta07
Ta08
Ta09
Ta1o
1231
1244
1218
1175
1224
1238
1227
1217
1274"
1241
Ta21
Ta22
Ta23
Ta24
Ta25
Ta26
Ta27
Ta28
Ta29
Ta30
1642*
1600
1557
1644*
1595
1643
1680
1603*
1625
1584
Ta41
Ta42
Ta43
Ta44
Ta45
Ta46
Ta47
Ta48
Ta49
Ta50
2005
1937
1846
1979
2000
2006
1889
1937
1961
1923
C.3.3 DATA GENERATION AND TRAINING
For a given number of jobs and machines m. we generate training data on the fly by randomly sampling machine permutation (o=,))² Sm for each job ji, and a random processing time Par E (0, 1] for each operation. We fix 200 instances for Jarena and a small validation set of size 20. We evaluate the model on the 10 benchmark instances of Taillard (Tailladd 1993) for each size: instances ta01-tal0 (size 15 x 15), instances ta21-ta30 (size 20 x 20) and instances ta4 1-a50 (size 30 x 20). The benchmark instances have integer processing times in [1, 100), which we rescale to the unit interval by division with 100. We summarize the best upper bounds from the literature in Table as reported Zhang et al. (022).. An episode takes is- m actions, so to reduce computation time, we limit the simulation budget to 50 for our approach and 100 for all single-player variants, running the agent for 20k episodes. We keep a ratio of the number of played episodes to the number of optimizer steps of approximately 1 to 0.02k m. We train from scratch for each problem size. As the action space is rather small (at most & actions at each timestep), we consider all feasible actions for the simulations the root of the search tree.
During training, we augment states sampled from the replay buffer by linearly scaling processing times Pt.1. job availability times e,,; and machine availability times Cr21 with random scalar in (0, 1). Furthermore, we shuffle the machines on which operations must be scheduled (c.g. operations on some machine A are reassigned some machine B and the other way round).
21

---

Published as a conference paper at ICLR 2023
C.3.4 STATE ENCODING NETWORK
There are two types of sequences problem instance. (i) For each job Jis we have sequence of operations, where the order of operations matters, (ii) The entirety of jobs forms sequence, where the order does not matter (similar to the sequence of nodes in the TSP). The encoding network consists of two stacked Transformer models, where the first one computes a latent representation for each job separately, and the second one operates on the sequence of these job representations to compute a state encoding. Both networks operate in latent space of dimension d = 64.
Job encoding The Transformer network for encoding each job from the sequenee of its unfinished operations consists of:
Learnable one-dimensional embeddings pmachine peperation {L....,m. + Rd.
Learnable lookup embedding Fjob in IRd
Affine maps W 1R20-1 - Rdd Wim-avail; T Rd. and Wi-avail ; R - RRd.
A simple stack of three Transformer blocks with four heads in the self-attention and in- stance normalization before the MHA and the FF.
Let E Jr be an unfinished job. We construct sequence in TRd
(Fjob
Wim-avail ((ce,1 - ....... Ct.m -2))), Wii-vall (max(0, ex, 2}).
( pmachine (o,,1); poperation (1):
W ([Paaccciiie (oi.m): puperration (m);
which passed to the stack of Transformer blocks. We mask all operations which have already been scheduled. The first element in the output sequence corresponding to Einb is taken latent representation of the job ji, which we denote by jlatent E Rdd
The job encoding procedure is depicted in Figure
State encoding The network for encoding the state representation from the sequence of latent job representations consists of:
Learnable lookup embedding Eloken in Rdd
Affine maps W/num, Wilen - Rd Wieb; RR Rd and Wmm-vail-2 R" + Rd
A simple stack of four Transformer blocks with four heads in the self-attention and instance normalization before the MHA and the FF.
From the set of unfinished jobs Jr Lir.1.... J. construct sequence
(Eooken
Wonum (me), Weee((s)) W - Ct ,,, (z)))s
Wriob (atentt) ..... Wijb (glaeer) )),
which is passed to the stack of Transformer blocks. Finally, ff outputs f(s)) = [s; ar:..., ān-t).
where the first output sequence element corresponding Eloken and à; corresponds to the output sequence element of the i-th unfinished job Wieb (glatca)).
D VALUE ESTIMATES AS TIMESTEP-DEPENDERN BASELINES
In this section, we provide more insight into why comparing pairs of states in the value function instead of directly comparing pairs of predicted values be beneficial in self-competitive setting.
22

---

Published as a conference paper at ICLR 2023
To recall, at some state st for action at, the policy logit update in GAZ (both for the in tree action selection and obtaining a policy training target) is given by
logit four (a) = logit" (a) + (A"
where A"(s,a) a- Qs ae) from the tree search and value network evaluations (cf. equation (4) in Section 3.2). In the following discussion, for ease of notation, denote by ky the current policy of the learning actor, and by :- Th the historical best greedy policy.
(T) is advantage estimation based on the Q-value estimates
As proposed in Section 3.2 in GAZ. PTP, we comparing pairs of states at timestep / assess how good the learning actor performs compared with its historical version. This is achieved by swapping the term Ar (s,,, ax) in the logit update with
(st, s(; == Qud" (st, -iin))-Taaaaa (Se,
where the state s/ comes from (greedy) trajectory of the policy j (see equation The sgn in the subscript indicates that the value network is trained to estimate the sign of the episodic reward difference in the original MDP (cf. equation (6). In the self-competitive framework, are working with the assumption that predicting the expected episode outcome without sophisticated techniques can be hard task. By supplying the value network with training data consisting of state pairs and binary targets to decide which state is more advantageous, the network is given a certain amount of freedom in how to model the problem and does not rely explicitly (as e.g. GAZ Single Vanilla) on the value network's 's capability to predict the expected outcome.
In contrast, by explicitly using value predictions, the advantage estimation a timestep can also be formulated as
(se, 0z) (st, a1) 1/:
(28)
where the baseline by is estimate of [ço=(so,ah-st .f...........))>)))> yn-r [V"(s(]]. In this case, baselining the Q-values from the standard togge-player tree search with the expectation of the value of the historical policy μ at timestep f. This is sensible, as it allows us to compute the estimate bj for all timesteps in advance of the learning actor's 's episode (similarly to GAZ PTP GT, see B.6) without the need to reevaluate the states s encountered by y in the tree search. By using by we maintain the postulated benefit of keeping instance-specift, information about the behavior of μ in intermediate timesteps (via value estimates). Additionally, the MCTS can be run with GAZ in the standard single-player way, as baselining with b," fits elegantly into GAZ's in-tree action selection and policy improvement mechanisms (see equations (4) and (28) ). In the following, we refer to this method as GAZ Single Timestep Baseline (GAZ Single TB) and consider two ways of obtaining 6":
(i) (GAZ Single TB Greedy) Let co cgreedy = (so, " .b...., obtained by rolling out μ greedily. As counterpart GAZ PTP GT, we
................................ S 11-1,
1, sTy) be the trajectory
by = Vs())
where V, S > R is the learning actor's 's (single-player) value network.
(ii) (GAZ Single TB Sampled) For i {1, {1.....kk) k) for some k E N, sample trajectories
Co.i (so, ....... - -
1,00 $7,1)
using μ. and average over the value network evaluations via
6
V.
We provide listing of the method in Algorithm 3
The algorithmic variant GAZ PTP GT is similar to GAZ Single TB Greedy, except that we compare pairs of states in GAZ PTP GT, and value estimates in GAZ Single TB Greedy. Furthermore, the number of network evaluations is the same in both variants because only a single greedy rollout of μa is required. Value estimates (resp. latent states for GAZ PTP GT) can be stored in memory for usage in the MCTS. We compare the two variants of GAZ Single TB with GAZ Single Vanilla and GAZ PTP GT in small-scale experiments for TSP 100 (50 search simulations, 20k episodes) and JSSP
23

---

Published as a conference paper at ICLR 2023
Algorithm 3: GAZ Single TB Training
Input: Po: initial state distribution
Input: : set of initial states sampled from
Init policy replay buffer Mr < and value replay buffer My <- Init parameters 0, for policy net m S - AA and value net V2: S - RR
Init 'best' parameters g 8 foreach episode do
Sample initial state 8o Po Obtain 7 baseline values bo...... by via
be (s) 1 11 Vo(s,)) for t = .,...,, 7 do
greedy for greedy trajectory So for sampled trajectories Çu,i
TB Greedy
TB Sampled
Perform policy improvement Z with single-player MCTS using V-(-) and policy no (-),
baselining logit updates with b,...., by-1 in tree
Receive improved policy [s(s),, action a₃ and new state 86+-1
Have trajectory Ç t (sp: ao: ................................ ST-1: ST)
Store (st. (x)) Mr for all timesteps
Store (C)r(() in Mv
Periodically update 8 + E Eng (F(S6)e00)) - r r(
> 0
Table 3: Results for TSP 100 (50 simulations and 20k episodes) and JSSP 15x 15 (35 simulations and 10k episodes). Results are averaged + standard deviation across three seeds E {42, 43, 44). GAZ Single Vanilla fails learn for seed 44.
TSP n = 100
JSSP 15 x 15
Method
Obj.
Gap
Obj.
Gap
GAZ PTP GT
8.06 + 0.04
3.8% + 0.5%
1505.2 + 55.7
22.0% + 3.8%
GAZ Single Vanilla
10.76 + 0.04
38.6% 1: 0.5%
2823.6 + 1787.5
129.8% 1 145,4%
GAZ Single TB Greedy
10.30 0.19
32.6% 2.5%
1532.5 +: 20.3
24.7% 1 1.6%
GAZ Single Sampled
10.82 0.20
39.4% 2.6%
1910.8 1 498.3
55.5% 1: 40.6%
15 x 15 (35 search simulations, 10k episodes). For GAZ Single TB Sampled, we sample k = 10 trajectories. The results are presented Table
Even though GAZ Single TB still relies on the value network being able to predict the expected outcome of episode sufficiently well, the small-scale experiments indicate that GAZ Single TB provides better advantage baseline to form curriculum for the learning actor than the value interpolation of GAZ Single Vanilla. GAZ Single TB Greedy in particular obtains comparable results to GAZ PTP GT for JSSP, and improves faster than GAZ Single Vanilla for TSP. We believe that GAZ Single TB can provide much stronger method than the value interpolation (26) of GAZ. for baselining the Q-values in problems where it is 'casier' to predict the expected outcome of an episode, or in combination with more sophisticated value prediction techniques, such as the target scaling techniques proposed in Pohlen et al. (2018) or Implicit Quantile Networks (Dabney al. 2018).
24


Reviews:
[{"review_id": "dnzOGQJARs", "reviewer": "Reviewer_vDBJ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposes an MCTS/AlphaZero-type algorithm for single player task. There several crucial deviation from the standard variant: it is using the Gumbel variant of AlphaZero, and more crucially, instead of estimating the state-value function, it is biasing it (adversarily) with returns obtained in playouts using a historical version of the player. The algorithm is applied on TSP and JSSP instances obtaining strong performances. \n", "summary_of_the_review": "The paper proposes some interesting variation of state-of-the-art algorithms, which may be successful in some domain. The applicability is somewhat limited by the requirement of uniform length episodes, and by the suitability of pairwise comparisons in the domain, but there likely exist sufficient number of domains were the approach is relevant. \n", "strength_and_weaknesses": "The idea of competing against a playout of a historical variant is interesting, and it is inserted in the AlphaZero framework in an elegant way. \n\nThe approach proposed in the paper replaces the problem of state-value estimation with a pairwise estimation problem. Pairwise comparison were tested previously in two-player game frameworks as well (with moderate success), but it is unclear that pairwise approaches are less frequent because of the particular approaches or because they proved more difficult than the original estimation problem in the test domains. Nevertheless the approach proposed is interesting, and there will always be domains that are more suited to pairwise comparisons.\n\nAn apparent limitation, which does not seem to be highlighted sufficiently in the paper, is that length of the episodes need to be equal. This is not a problem in the test domains considered in the paper, but many single agent problems do have varying episode length. \n\nUsing combinatorial optimization problems as test domains is somewhat surprising choice, but maybe that was due to the necessity of equal episode length and the efficiency of the pairwise comparisons.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "5CKRILkaao", "reviewer": "Reviewer_8mG6", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper introduced Gumbel AlphaZero Play-to-Plan (GAZ PTP), a self-competitive method combining greedy rollouts as in self-critical training with the planning dynamics of two-player games.\nThe main idea is to compute a scalar baseline from the agent’s historical performances and to reshape an episode’s reward into a binary output, indicating whether the baseline has been exceeded or not. \nGAZ PTP leverages the idea of self-competition and directly incorporates a historical policy into the planning process instead of its scalar performance. Based on the Gumbel AlphaZero (GAZ), the agent learns to find strong trajectories by planning against possible strategies of its past self.\nThen, experiments on the Travel Salesman Problem (TSP) and Job-Shop Scheduling Problem (JSSP) confirm that the method learns strong policies in the original task with a low number of search simulations.\n", "summary_of_the_review": "It is interesting to use self-competitive planning TSP or JSSP with binary episode reward (win or lose). However, when compared to other DRL methods, the performances of this paper are not so good. The trained model is not size-agnostic, and thus a big weakness of it. In summary, we tend to reject this paper.\n", "strength_and_weaknesses": "**Strength:**\n\n1. It is interesting to use self-competitive planning TSP or JSSP with binary episode reward (win or lose). This binary episode reward somehow handles the reward designing problem, which is an issue on RL problems. \n\n**Weakness:**\n\n1. This method trains from scratch for each problem size, compared to those GNN-DRL methods (cited in this paper) which are size-agnostic methods. This makes it inefficient since the problem size varies in such problems. \n\n2. The performances for TA benchmarks 15x15, 20x20, 30x20 (for JSSP) are all worse than those obtained in Schedulenet (Park et al., 2022). Namely 16.6%, 22%, 32.3% (even with MCTS), w.r.t. schedulenet’s 15.3%, 17.2%, 18.7% respectively. Even, the bigger the problem sizes are, the worse the gap ratios are. The same for TSP. Thus, this makes this paper weaker or skeptical. \n\n3. This paper mentions that MCTS method must need more inference time than DRL method in testing. However, the time is not included in the experiments. \n\n4. The presentation is quite confusing. See the next section. \n\n\n\n\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "20zt0JxWWM1", "reviewer": "Reviewer_T4pL", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper describes a new \"policy-based self-competition\" approach for training policies for single-agent (planning) problems with Gumbel AlphaZero. It uses rollouts from a DNN policy (without search) to provide reference/baseline values, such that binary reward signals (without any need for normalisation) for the DNN+search agent can be provided depending on whether or not it outperforms the baseline.", "summary_of_the_review": "An interesting paper with a lot of potential, but there is a major point where I can't help but feel like the problem is modelled in a way that is, unnecessarily, hugely overcomplicated (even if it is a very interesting way to model it). If I am correct, I feel that this is an important issue, hence my current score. But I also do not rule out the possibility that I simply completely missed some key detail, in which case I hope the authors will be able to provide clarification.\n\n---\n\n**After discussion with authors**: The authors' comments and added content in the new revision have helped me a lot to clear up confusion.", "strength_and_weaknesses": "**Strengths**:\n- Contributions look sound, interesting ideas, also novel\n- Promising/good empirical results\n\n**Weaknesses**:\n- Some of the core ideas behind the approach leave me wondering about a bunch of unaddressed questions. I think these need to be cleared up somehow. See detailed comments below.\n\n---\n\n**After discussion with authors**: The authors' comments and added content in the new revision have helped me a lot to clear up confusion.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster