summaries: The paper suggests two techniques to improve the calculation of empirically figuring out a Nash equilibrium using an iterative application of best-response dynamics. One method learns the best-response to the previously used strategy. The other uses that technique to model the opponent, and then best-responds to the modeled opponent. The experiments show a faster reaching to NE than without these changes.

summaries: The paper proposes two new methods in the Policy-Space Response Oracle framework. These approaches permit to reuse past knowledge in order to reduce the amount of data required for the RL training. The first algorithm Mixed-Oracles transfers the previous iteration of Deep RL, instead of the second one, Mixed-Opponents, transfers existing strategy action-value estimates.

summaries: The paper focuses on resolving the computational and sample efficiency challenges with current PSRO style approaches. To this end it proposes two different modifications to the standard PSRO setup: 1) Mixed Oracles, and 2) Mixed Opponents. These approaches allow avoiding resetting learning after each outer loop epoch and reduce the stochasticity of dynamics during training. Thee efficacy is demonstrated on relatively simple games but using Deep RL policies where the proposed approaches are at least on par with standard PSRO approach in terms of final performance while drastically improving the sample efficiency.

abstractText: Policy-Space Response Oracles (PSRO) is a general algorithmic framework for learning policies in multiagent systems by interleaving empirical game analysis with deep reinforcement learning (Deep RL). At each iteration, Deep RL is invoked to train a best response to a mixture of opponent policies. The repeated application of Deep RL poses an expensive computational burden as we look to apply this algorithm to more complex domains. We introduce two variations of PSRO designed to reduce the amount of simulation required during Deep RL training. Both algorithms modify how PSRO adds new policies to the empirical game, based on learned responses to a single opponent policy. The first, Mixed-Oracles, transfers knowledge from previous iterations of Deep RL, requiring training only against the opponent’s newest policy. The second, Mixed-Opponents, constructs a pure-strategy opponent by mixing existing strategy’s action-value estimates, instead of their policies. Learning against a single policy mitigates variance in state outcomes that is induced by an unobserved distribution of opponents. We empirically demonstrate that these algorithms substantially reduce the amount of simulation during training required by PSRO, while producing equivalent or better solutions to the game.

authors:
David Balduzzi
Marta Garnelo
Yoram Bachrach
Wojciech M. Czarnecki
Julien Perolat
Max Jaderberg
Thore Graepel

title: Open-ended learning in symmetric zero-sum games

venue: In 36th International Conference on Machine Learning,

authors:
A. Blum
Y. Mansour

title: Learning, regret minimization, and equilibria

venue: In Algorithmic Game Theory,

title: Iterative solution of games by fictitious play

venue: In Activity Analysis of Production and Allocation,

authors:
Sergiu Hart
Andreu Mas-Colell

title: A simple adaptive procedure leading to correlated

venue: equilibrium. Econometrica,

authors:
Hado van Hasslet
Arthur Guez
David Silver

title: Deep reinforcement learning with double Q-learning

venue: In 30th AAAI Conference on Artificial Intelligence,

authors:
Marc Lanctot
Vinicius Zambaldi
Audrūnas Gruslys
Angeliki Lazaridou
Karl Tuyls
Julien Pérolat
David Silver
Thore Graepel

title: A unified game-theoretic approach to multiagent reinforcement learning

venue: In 31st International Conference on Neural Information Processing Systems,

authors:
Stephen McAleer
John Lanier
Roy Fox
Pierre Baldi

title: Pipeline psro: A scalable approach for finding approximate nash equilibria in large games

venue: In 34th International Conference on Neural Information Processing Systems,

authors:
H. Brendan McMahan
Geoffrey J Gordon
Avrim Blum

title: Planning in the presence of cost functions controlled by an adversary

venue: In 20th International Conference on Machine Learning,

authors:
Paul Muller
Shayegan Omidshafiei
Mark Rowland
Karl Tuyls
Julien Perolat
Siqi Liu
Daniel Hennes
Luke Marris
Marc Lanctot
Edward Hughes
Zhe Wang
Guy Lever
Nicolas Heess
Thore Graepel
Remi Munos

title: A generalized training approach for multiagent learning

venue: In International Conference on Learning Representations,

authors:
Shayegan Omidshafiei
Christos Papadimitriou
Georgios Piliouras
Karl Tuyls
Mark Rowland
Jean-Baptiste Lespiau
Wojciech M. Czarnecki
Marc Lanctot
Julien Perolat
Remi Munos

title: α-rank: Multi-agent evaluation by evolution

venue: Scientific Reports,

authors:
Julien Perolat
Joel Z. Leibo
Vinicius Zambaldi
Charles Beattle
Karl Tuyls
Thore Graepel

title: A multi-agent reinforcement learning model of common-pool resource appropriation

venue: In 31st Conference on Neural Information Processing Systems,

authors:
S. Phelps
M. Marcinkiewicz
S. Parsons

title: A novel method for automatic strategy acquisition in N-player non-zero-sum games

venue: In Fifth International Joint Conference on Autonomous Agents and Multiagent Systems,

authors:
L. Julian Schvartzman
Michael P. Wellman

title: Exploring large strategy spaces in empirical game modeling

venue: AAMAS-09 Workshop on Agent-Mediated Electronic Commerce,

title: Stronger CDA strategies through empirical game-theoretic analysis and reinforcement learning

venue: In 8th International Conference on Autonomous Agents and Multiagent Systems,

authors:
Max Olan Smith
Thomas Anthony
Yongzhao Wang
Michael P. Wellman

title: Learning to play against any mixture of opponents

authors:
Finnegan Southey
Michael Bowling
Bryce Larson
Carmelo Piccione
Neil Burch
Darse Billings
Chris Rayner

title: Baye’s bluff: Opponent modelling in poker

venue: In 21st Conference on Uncertainty in Artificial Intelligence,

authors:
Peter D. Taylor
Leo B. Jonker

title: Evolutionarily stable strategies and game dynamics

venue: Mathematical Biosciences,

authors:
William Walsh
Rajarshi Das
Gerald Tesauro
Jeffrey Kephart

title: Analyzing complex strategic interactions in multi-agent systems

venue: Workshop on Game Theoretic and Decision Theoretic Agents,

title: Methods for empirical game-theoretic analysis

venue: In 21st National Conference on Artificial Intelligence,

authors:
Mason Wright
Yongzhao Wang
Michael P. Wellman

title: Iterated deep reinforcement learning in games: History-aware training for improved stability

venue: In 20th ACM Conference on Economics and Computation,

heading: 1 INTRODUCTION

text:
In (single-agent) reinforcement learning (RL), an agent repeatedly interacts with an environment until it achieves mastery, that is, can find no further way to improve performance (measured by reward). In a multiagent system, the outcome of any learned policy may depend pivotally on the behavior of other agents. Direct search over a complex joint policy space for game solutions is daunting, and so more common in approaches combining RL and game theory is to interleave learning and game analysis iteratively.
In empirical game-theoretic analysis (EGTA), game reasoning is applied to approximate game models defined over restricted strategy sets. The strategies are selected instances drawn from a large space of possible strategies, for example, defined in terms of a fundamental policy space: mappings from observations to actions. For a given set of strategies (policies),1 we estimate an empirical game via simulation over combinations of these strategies. In iterative approaches to EGTA, analysis of the empirical game informs decisions about the sampling of strategy profiles or additions of strategies to the restricted sets. Schvartzman & Wellman (2009b) first combined RL with EGTA, adding new strategies by learning a policy for one agent (using tabular Q-learning), fixing other agent policies at a Nash equilibrium of the current empirical game.
Lanctot et al. (2017) introduced a general framework, Policy-Space Response Oracles (PSRO), interleaving empirical game analysis with deep RL. PSRO generalizes the identification of learning targets, employing an abstract method termed meta-strategy solver (MSS) that extracts a strategy profile from an empirical game. At each epoch of PSRO, a player uses RL to derive a new policy by training against the opponentstrategies in the MSS-derived profile.
A particular challenge for the RL step in PSRO is that the learner must derive a response under uncertainty about opponent policies. The profile returned by the MSS is generally a mixed-strategy profile, as in strategically complex environments randomization is often a necessary ingredient for equilibrium. The opponent draws from this mixture are unobserved, adding uncertainty to the multiagent environment.
1The term policy as employed in the RL context corresponds exactly to the game-theoretic notion of strategy in our setting, and we use the terms interchangeably.
We address this challenge through variants of PSRO in which all RL is applied to environments where opponents play pure strategies. We propose and evaluate two such methods, which work in qualitatively different ways: Mixed-Oracles learns separate best-responses (BR) to each pure strategy in a mixture and combines the results from learning to approximate a BR to the mixture. Mixed-Opponents constructs a single pure opponent policy that represents an aggregate of the mixed strategy and learns a BR to this policy. Both of our methods employ the machinery of Q-Mixing (Smith et al., 2020), which constructs policies based on an aggregation of Q-functions corresponding to component policies of a mixture.
Our methods promise advantages beyond those of learning in a less stochastic environment. Mixed-Oracles transfers learning across epochs, exploiting the Q-functions learned against a particular opponent policy in constructing policies for any other epoch where that opponent policy is encountered. Mixed-Opponents applies directly over the joint opponent space, and so has the potential to scale beyond two-player games.
We evaluate our methods in a series of experimental games, and find that both Mixed-Oracles and Mixed-Opponents are able to find solutions at least as good as an unmodified PSRO, and often better, while providing a substantial reduction in the required amount of training simulation.

heading: 2 PRELIMINARIES

text:
An RL agent at time t ∈ T receives the state of the environment st ∈ S, or a partial state called an observation ot∈O. The agent then chooses an action at according to its policy, π :O→∆(A), effecting the environment and producing a reward signal rt∈R. An experience is a (st,at,rt+1,st+1)-tuple, and a sequence of experiences ending in a terminal state is an episode τ . How the environment changes as a result of the action is dictated by the environment’s transition dynamics p :S×A→S. The agent is said to act optimally when it maximizes returnGt= ∑∞ l γ
lrt+l (γ is a discount factor). In value-based RL, agents use return as an estimate of the quality of a state V (ot) =Eπ [∑∞ l=0γ lr(ot+l,at+l) ] , and/or
taking an action in a stateQ(ot,at)=r(ot,at)+γEot+1∈O [ V (ot+1) ] .
A normal form games (NFG) Γ = (Π,U,n) describes a one-shot strategic interaction among n players. When there is more than one agent, we denote agent-specific components with subscripts (e.g., πi). Negated subscripts represent the joint elements of all other agents (e.g., π−i). Each of the players has a set of policies Πi= { π0i ,...,π k i } from which it may choose. Player imay select a pure strategy πi∈Πi, or may randomize play by sampling from a mixed strategy σi∈∆(Πi). At the end of the interaction, each player receives a payoff U :Π→Rn. An empirical NFG (ENFG) Γ̃=(Π̃,Ũ,n) is an NFG induced by simulation of strategy profiles. An ENFG approximates an underlying game Γ, estimating the payoffs through simulation. ENFGs are often employed when the strategy set is too large for exhaustive representation, for example when the strategies are instances from a complex space of policies.
The quality of a strategy profile in an ENFG can be evaluated using regret: how much players could gain by deviating from assigned policies. Regret is measured with respect to a set of available deviation policies. The regret of solution σ to player i when they are able to deviate to policies in Πi ⊆ Πi is: Regreti(σ,Πi)=maxπi∈ΠiUi(πi,σ−i)−Ui(σi,σ−i). Example deviation sets Π employed in this paper are ΠPSRO, the strategies accumulated through a run of PSRO, and ΠEVAL, denoting a static set of held-out evaluation policies. The sum of regrets across all players SumRegret(σ,Π) = ∑ i∈nRegreti(σ,Πi) , sometimes called the Nash convergence, is a measure of how stable a solution is.

heading: 3 METHOD

text:
At each epoch e of the PSRO algorithm a new policy is constructed for each player by best-responding to an opponent profile σ∗,e−1−i from the currently constructed ENFG: π e i ∈BR(σ ∗,e−1 −i ). These policies are then added to each player’s strategy set, Π̃ei ← Π̃ e−1 i ∪{πei }, and the new profiles are simulated to expand the ENFG. Algorithm 1 presents the full PSRO algorithm as defined by Lanctot et al. (2017).
One of the key design choices in iterative empirical game-solving is choosing which policies to add to the ENFG. This was first studied by Schvartzman & Wellman (2009a), who termed it the strategy exploration problem. We want to add policies that both bring the solution to the ENFG closer to the solution of the full game and that can be calculated efficiently. In PSRO, the strategy exploration problem is decomposed into two steps: solution and BR via RL. In the solution step, PSRO derives a profile σ∗,e from the current
empirical game. The method for choosing this profile is termed the meta-strategy-solver (MSS), formally a function from empirical games to solution profiles MSS :Γ̃e→σ∗,e. For example, the MSS might compute a Nash equilibrium of Γ̃e.2 In the BR step, PSRO generates a new policy via RL (the response oracle), training against the target opponent profile computed by the MSS. The choice of MSS and response oracle algorithm constitutes a strategy exploration approach and determines the convergence speed of PSRO.
We observe and address two main problems with the standard version of PSRO (Algorithm 1). First, note that the only thing that changes from one epoch to the next is the other-agent strategy profile σ−i; the transition dynamics remain the same, and the mixed profile σ−i itself likely contains other-agent policies encountered in previous epochs. This suggests a compelling opportunity to transfer learning across epochs; however, the BR calculation step works by training anew. Furthermore, because it is responding to some of the same strategies, the new policy learnt may be similar to the strategies added in previous epochs, and so not the most useful addition to the ENFG. Secondly, the opponent profiles are mixtures (i.e., distribution over opponent policies). This makes the environment dynamics more stochastic from the perspective of the RL agent, making learning more difficult. In Section 3.1 we propose an algorithm that transfers knowledge between iterations, and only trains against the single new opponent. In Section 3.2 we present a second algorithm that avoids responding to similar opponent strategies on subsequent iterations, while also addressing the opponent variance issue and providing scalability to multiple other agents.

heading: 3.1 MIXED-ORACLES

text:
The first problem we address is that during BR calculation there is a missed opportunity for transferring previously learned information. In each epoch, each player learns a BR to a mixed profile of opponent policies. This mixture typically involves the newly added strategies (one per player) for this epoch, but may also include strategies from previous epochs. Training in previous epochs already captured experience against those strategies, so including them in further training entails some redundancy.
The Mixed-Oracles algorithm is a variant of PSRO for two-player games, with a modified BR oracle designed to transfer learning across epochs. This method works by learning and maintaining a collection of BRs to each opponent policy Λei = { λ1i ,...,λ e i } , where λei is the BR to π e−1 −i . During each epoch of MixedOracles, a BR is learned for the single new opponent policy, rather than for the mixed opponent-profile generated by the MSS. A BR to the MSS-generated target mixture is then constructed from the collection of BR results for constituent policies in the mixture. Constructing the new policy is done through a general Combine-Responses function that maps a set of policies and a distribution over the policies into a single policy. The resulting policy should approximately aggregate the behavior of the policies.
By reusing learned behaviors from previous epochs, Mixed-Oracles allows us to focus training exclusively on new opponent policies. The key design choice is how to combine knowledge from the BRs to individual policies into a BR to any distribution of said policies. We provide a general description of Mixed-Oracles, where the Combine-Responses method is abstract, as Algorithm 2.
Smith et al. (2020) propose Q-Mixing as an approach for constructing policies against any mixture of opponent strategies. The method employs Q-values learned against each individual opponent strategy, and thus can support the transfer sought here. Specifically, Q-Mixing averages the Q-values learned against each opponent policy π−i, weighted by their likelihood in the opponent mixture σ−i:
Qi(oi,ai |σ−i)= ∑ π−i ψi(π−i |oi,σ−i)Qi(oi,ai |π−i), (1)
where ψ determines the relative likelihood of playing an opponent ψi :Oi→∆(Π−i). In this study, we use Q-Mixing as our Combine-Responses, where ψ is the prior over the opponent distribution as given by an MSS.

heading: 3.2 MIXED-OPPONENTS

text:
We next examine PSRO’s objective defined by BR to the opponent profile generated by an MSS. Consider the Rock-Paper-Scissors (R-P-S) game in figure 1. Player 1’s initial strategy π11 mostly plays S, which
2Use of NE as MSS corresponds (for two-player games) to the popular double oracle algorithm (McMahan et al., 2003). A variety of other MSSs have been proposed, and assessing their relative merits is a topic of active research (Balduzzi et al., 2019). In experiments reported here, we adopt NE as the baseline MSS; however, our methods readily apply to any MSS.
Algorithm 1: Policy-Space Response Oracles (Lanctot et al., 2017) Input: Initial policy sets for all players Π0 Simulate utilities ŨΠ 0 for each joint π0∈Π0 Initialize solution σ∗,0i =Uniform(Π 0 i ) while epoch e in {1,2,...} do for player i∈ [[n]] do
for many episodes do π−i∼σ∗,e−1−i Train πei over τ∼(πei ,π−i) Πei =Π e−1 i ∪{πei }
Simulate missing entries in ŨΠ e from Πe Compute a solution σ∗,e from Γ̃e
Output: Current solution σ∗,ei for player i
Algorithm 2: Mixed-Oracles Input: Initial policy sets for all players Π0 Simulate utilities ŨΠ 0 for each joint π∈Π0 Initialize solutions σ∗,0i =Uniform(Π 0 i ) Initialize pure-strategy BRs Λ0i =∅ while epoch e in {1,2,...} do
# Best respond to each new opponent. for player i∈ [[n]] do
for many episodes do Train λei over τ∼(λei ,π e−1 −i ) Λei =Λ e−1 i ∪{λei}
# Generate new policies. for player i∈ [[n]] do
πei←Combine-Responses(Λei ,σ ∗,e−1 −i ) Πei =Π e−1 i ∪{πei }
Simulate missing entries in ŨΠ e from Πe Compute a solution σ∗,e from Γ̃e
Output: Current solution σ∗,ei for player i.
induces a best response of R. Player 1’s second strategy π21 is an approximate best response to R, scoring 80% against it. The best response to π21 is P. This leads to an empirical game similar to matching pennies, with player 2 playing an even mixture of Rock and Paper; in particular, player 2’s meta-strategy never plays S, despite it being good against both player 1 strategies so far.
If, as in PSRO, player 1 then adds their BR to this meta-strategy, which is P, then their strategy set still does not contain the Nash equilibrium of the game. The problem is that there are already strategies in the empirical game that can defeat player 2’s strategies, so the new strategy is not useful. This can be detected by inspecting player 2’s Q-functions: Q12 has a very low valuation of P, andQ 2 2 has a very low valuation of R. Responding to S, which is moderately highly valued by both opponentQ functions, is more relevant. To achieve this, we can mix the opponent strategies through their action-value estimates, rather than their action distributions (Figure 1). The BR to this is R, which more usefully extends player 1’s strategy set.3
This example motivates our second algorithm: Mixed-Opponents. This method also employs a combination method, but instead of combining results from training against previously encountered opponents, it combines the strategies of the opponent mixture themselves to construct a single new opponent policy as a target for training. We refer to the method for generating a new opponent policy from a mixture of opponents the Combine-Opponents, and it has the same functional form as the Combine-Responses. The generalized Mixed-Opponent algorithm is shown in Algorithm 3. We employ Q-Mixing (Equation 1) as our Combine-Opponents. In contrast to Mixed-Oracles, which uses Q-Mixing to transfer Q-values across epochs, here we apply it to average Q-values to define a variant training objective.

heading: 3.3 ENVIRONMENTS

text:
We evaluate our algorithms on the Gathering (Perolat et al., 2017) and Leduc Poker (Southey et al., 2005) games, both of which are commonly used in the multiagent reinforcement learning field.
Gathering is a gridworld tragedy-of-the-commons game that is partially observable and general-sum. Agents compete to harvest apples that regrow at a rate proportional to the number of nearby apples. The individual’s interest in harvesting conflicts with the group’s interest in regrowth creating the dilemma. We investigate two versions of this game that differ in the configuration of the map (apple locations, spawn points, etc.): (1) Gathering-Small has all apples in a dense grove central in the map, and (2) Gathering-Open is a larger map with many spread-out apple groves. The former environment will be used to force two agents to interact, while the latter will allow the study of interactions between more than two players. Further details and images of the environments are included in Section D.1.
3In Appendix E, we give precise strategies and Q-values that realize this example.
Algorithm 3: Mixed-Opponents Input: Initial policies for all players Π0 Simulate ŨΠ 0 for each joint π∈Π0 Initialize solutions σ∗,0i =Uniform(Π 0 i ) while epoch e in {1,2,...} do for player i∈ [[n]] do
π−i← Combine-Opponents(Πe−1−i ,σ ∗,e−1 −i )
for many episodes do Train πei over τ∼(πei ,π−i) Πei =Π e−1 i ∪{πei }
Simulate missing entries in ŨΠ e Compute a solution σ∗,e from Γ̃e
Output: Solution σ∗,ei for player i.
Figure 1: Mixed-strategy opponent targeted in PSRO (top) and corresponding Q-Mixed opponent (bottom). (Left) shows the opponent policy Q-values, and (right) shows the resulting opponent policies and their BRs. In Mixed Opponents, the BR expands the strategy space to include the Nash equilibrium of RPS (green dot), but in PSRO it does not.
Leduc Poker is a reduced version of Poker, designed to capture the important characteristics of a full game of Poker. The game proceeds similarly to Poker, where each player chooses to raise/call/fold through two rounds of betting. In this version, we examine the 2-player versions of Leduc Poker. More detailed information about this environment is included in Section D.2.

heading: 3.4 HYPERPARAMETERS

text:
The objective of this study is to minimize the number of timesteps spent training a RL agent across all epochs of PSRO. To this end, how timesteps are counted is critical to the comparison of methods. The number of timesteps used for training is typically a hyperparameter for the RL agent. This presents a challenging dilemma, because (1) we must select this before running PSRO, and (2) any particular setting may not work against all opponent-profiles chosen by the MSS.
To address these issues we take a two-step approach (detailed in Section B). First, we select preliminary hyperparameters by searching for their setting that performs best against a random opponent policy. Then we use these hyperparameters to generate a set of opponent-policies (via PSRO) to use as an objective for selecting final hyperparameters. A subset of the generated policies are used as an opponent test-bed to collect two sets of hyperparameters: pure-hparams performed best on-average against each individual test-opponent, and mix-hparams performed best against a uniform mixture of the test-opponents. These settings are meant to represent the high- and low-variance situations encountered when training mixed and pure strategies.
In this work, our Deep RL algorithm is Double Q-Learning (Hasslet et al., 2016), and our policies have two hidden layers with ReLU activations. 300 hyperparameter settings are sampled in each environment. Complete details are provided in Section D.

heading: 4 EXPERIMENTS

text: Regret as a measure depends on the policies that are available for deviation; therefore, it may be misleading to compare across PSRO runs directly. As a more equitable comparison, we instead measure regret when deviating to both the run’s discovered policies ΠPSRO and a held-out set of evaluation policies ΠEVAL. The evaluation policies’ provide a standard lower-bound on regret across all runs. These policies are constructed by independent PSRO runs, not included in the results here, by sampling from the solution’s support. Payoffs are estimated for 30 episodes for 6 policies in all environments, except Gathering-Open with 9.

heading: 4.1 MIXED-ORACLES

text:
The first research question we address is: does Mixed-Oracles result in a similar quality solution compared to PSRO while utilizing fewer simulation timesteps? We begin by running both algorithms on the GatheringSmall and Leduc-Poker games. We record regrets over PSRO epochs and cumulative training timesteps.
Figure 2 compares the convergence speed of both algorithms on the Gathering-Small environment. We found that Mixed-Oracles converged in roughly half the number of epochs while utilizing a quarter of the number of simulations. Moreover, the solution discovered by Mixed-Oracles had approximately 30% less regret. Figure 3 shows the result on Leduc-Poker, where we observe Mixed-Oracles finding a comparable solution in dramatically fewer cumulative timesteps. These results confirm our hypothesis that Mixed-Oracles will find comparable solutions to PSRO in fewer training timesteps.

heading: 4.2 MIXED-OPPONENTS

text:
Next, we address the question: does Mixed-Opponents result in a better quality solution compared to PSRO while utilizing fewer simulation timesteps? The methodology of this experiment follows the previous experiment: measuring SumRegret on both the Gathering-Small and Leduc-Poker games.
Figure 4 compares the convergence speed of both algorithms on the Gathering-Open game. Both algorithms appear to converge initially after 25 epochs, and at this point, Mixed-Opponents had discovered a solution with 50% less regret. However, while PSRO remained converged as time went on, Mixed-Opponents continues to improve and nearly solves the game. Figure 5 shows the results on Leduc-Poker. Similar to Mixed-Oracles, we also find that Mixed-Opponents finds a similar solution to PSRO in dramatically fewer timesteps. Together these results confirm our second hypothesis that Mixed-Opponents may find a comparable solution to PSRO in less training simulations.

heading: 4.3 >2 PLAYER GAMES

text: An advantage of Mixed-Opponents over Mixed-Oracles is that it can be applied to games with more than two players. Does Mixed-Opponents reduce training-simulation when compared to PSRO in games where there are more than two players? We run both algorithms on the Gathering-Open game with three players. We limit each profile in the ENFG to three simulations, to handle the combinatorial explosion of profiles. Figure 6a shows our results where Mixed-Opponents finds a similar quality solution to PSRO in half of the time.

heading: 4.4 SHARED HYPERPARAMETERS

text:
An important choice in these experiments has been how to measure timesteps elapsed. We used two sets of hyperparameters: specialized for low- and high-variance outcomes of state, which are a result of facing pure- and mixed-strategy opponents respectively. This was motivated by the assumption that lower variance would require less training. In this section, we question that assumption and ask: do Mixed-Oracles and Mixed-Opponents perform at least as well as PSRO when given the same RL hyperparameters?
To answer this question we run all three algorithms with the same set of hyperparameters, forcing all to adopt the same simulation budget. We report results for the Gathering-Small game in Figure 6b. The trends observed in the previous experiment reoccur: Mixed-Oracles and Mixed-Opponents find solutions at least as good as PSRO in fewer timesteps, confirming our hypothesis. In particular, under the pure-hparams, where simulations are more limited, Mixed-Opponents find a better solution than PSRO in half the simulation timesteps.

heading: 5 RELATED WORK

text:
The first published paper to explicitly estimate an ENFG from an agent-based simulation was a study by Walsh et al. (2002) on pricing games and auctions. They analyzed symmetric games with up to twenty players over a small number of hand-crafted heuristic strategies. A few additional works in succeeding years explored the approach, which was developed into an algorithmic framework under the EGTA label by Wellman (2006). The strategy exploration problem within EGTA was first identified and studied by Schvartzman & Wellman (2009a). In this work, they explored three heuristic solutions and found that BR was the most effective method. They also illustrated situations where equilibrium response had poor performance.
Before this formalization, Phelps et al. (2006) were the first to utilize automated strategy generation. Their approach is still seen in PSRO today, where iterative BRs to equilibrium are used to build an empirical
(a) Mixed-Opponents evaluated on the Gathering-Open game with 3 players. (b) Comparison of algorithms when set to the same Deep RL hyperparameters.
Figure 6: Experiments on extension beyond two players and using shared hyperparameters.
game. They utilized a small parametric policy space and used genetic search as their approximate oracle method. Schvartzman & Wellman (2009b) followed this up by introducing reinforcement learning as the approximate oracle method. These algorithms, alongside a trend of deep reinforcement learning being used to solve difficult games, set the stage for the PSRO framework. PSRO highlighted a subclass of EGTA algorithms where an iterative construction of an empirical game is built through iterative BR to an opponent-profile. At each epoch, the opponent profile is determined by a chosen meta-strategy solver (MSS). The PSRO algorithm builds heavily upon the Double-Oracle (DO) algorithm, which iteratively solves for the Nash Equilibrium in two-player zero-sum sub-games (McMahan et al., 2003).
This has culminated in an interest in discovering good strategy-exploration methods within PSRO. PSRO’s strategy exploration happens in two phases: first, a MSS produces an opponent-profile as a learning objective, then reinforcement learning is used as an approximate oracle to best-respond to the objective. Many popular algorithms for computing strategies in game theory have been adapted as MSS: linearprogramming, replicator-dynamics Taylor & Jonker (1978), regret-minimization (Blum & Mansour, 2007), and regret-matching (Hart & Mas-Colell, 2000). Moreover, popular game-solving algorithms can also be viewed through the lens of a MSS. Fictitious play (Brown, 1951) is a MSS where the resulting profile is a uniform-strategy. Similarly, self-play’s resulting profile is a pure strategy containing only the newest policy.
Prompting recent work to leverage the additional information gleaned through the empirical game to construct new MSSs. Wright et al. (2019) extends DO’s MSS to return a decay-weighted linear combination of the current and previous solutions. Omidshafiei et al. (2019) proposes Markov-Conley Chains (MCC) as a solution concept that relates to their new proposed quality measure of policy called α-Rank, and Muller et al. (2020) investigated its use as a MSS.
McAleer et al. (2020) also tackles the problem of the compute requirements of PSRO by addressing its runtime. Their Pipeline-PSRO algorithm enables the RL process across epochs to be trained in parallel. The parallel technology could be leveraged to reduce runtime of both Mixed-Oracles and Mixed-Opponents.

heading: 6 CONCLUSIONS

text: In this study, we investigate PSRO’s approach to strategy exploration and extensions that focus on reducing the time spent on training new policies. PSRO’s strategy exploration occurs in two steps: solution and BR via RL. We first propose Mixed-Oracles which approximates the solution step by training separate BRs to each opponent policy and then combining the results into an approximate BR to the solution. This affords our algorithm the ability to transfer learning about previously encountered opponents. Next, we introduce Mixed-Opponents which modifies the BR training by constructing a single opponent policy that represents an aggregate of the mixed strategy and learns a response to this new opponent. Mixed-Opponents also trivially scales to games with more than two players. Both of these methods further mitigate the variance in state outcomes, by removing an unobserved distribution of opponents, easing learning.

heading: ACKNOWLEDGMENTS

text: Work at the University of Michigan was supported in part by MURI grant W911NF-13-1-0421 from the US Army Research Office.

title: ITERATIVE EMPIRICAL GAME SOLVING VIA SINGLE POLICY BEST RESPONSE


summaries: In this paper the authors tackle the problem of alignment between input tokens and output acoustic features. The key contribution of this paper is replacing the attention mechanism of the Tacotron 2 with an explicit representation of token durations. The attention mechanism is vulnerable to issues such as pauses, repetitions, and skips, and hence using durations directly takes care of such issues. The challenge lies in obtaining the durations. The authors propose different methods toward that end.

summaries: In this paper, the authors introduce a text-to-speech model based on Tacotron 2, called Non-Attentive Tacotron. Instead of an attention mechanism, a duration predictor is utilized to improve robustness, which is evaluated by two metrics, unaligned duration ratio (UDR) and word deletion rate(WDR). The authors propose semi-supervised and unsupervised duration modeling with a fine-grained variational auto-encoder (FVAE).

summaries: This paper presents an approach based on the Tacotron model for speech synthesis, where the attention mechanism is replaced by a duration predictor. It also presents a short study on semi-supervised and unsupervised training. The paper also introduces two metrics to evaluate the robustness of the model. The experiments shows that the proposed model is on par with the Tacotron baselines in terms on MOS score and better in terms of the new metrics.

abstractText: This paper presents Non-Attentive Tacotron based on the Tacotron 2 text-to-speech model, replacing the attention mechanism with an explicit duration predictor. This improves robustness significantly as measured by unaligned duration ratio and word deletion rate, two metrics introduced in this paper for large-scale robustness evaluation using a pre-trained speech recognition model. With the use of Gaussian upsampling, Non-Attentive Tacotron achieves a 5-scale mean opinion score for naturalness of 4.41, slightly outperforming Tacotron 2. The duration predictor enables both utterance-wide and per-phoneme control of duration at inference time. When accurate target durations are scarce or unavailable in the training data, we propose a method using a fine-grained variational auto-encoder to train the duration predictor in a semi-supervised or unsupervised manner, with results almost as good as supervised training.

authors:
Sercan O Arik
Mike Chrzanowski
Adam Coates
Gregory Diamos
Andrew Gibiansky
Yongguo Kang
Xian Li
John Miller
Andrew Ng
Jonathan Raiman
Shubho Sengupta
Mohammad Shoeybi

title: Deep Voice: Real-Time Neural Text-to-Speech

venue: In Proc. ICML,

authors:
Dzmitry Bahdanau
Kyunghyun Cho
Yoshua Bengio

title: Neural Machine Translation by Jointly Learning to Align and Translate

venue: In Proc. ICLR,

authors:
Eric Battenberg
RJ Skerry-Ryan
Soroosh Mariooryad
Daisy Stanton
David Kao
Matt Shannon
Tom Bagby

title: Location-Relative Attention Mechanisms For Robust Long-Form Speech Synthesis

venue: In Proc. ICASSP,

authors:
Stanislav Beliaev
Yurii Rebryk
Boris Ginsburg

title: TalkNet: Fully-Convolutional NonAutoregressive

venue: Speech Synthesis Model. arXiv preprint arXiv:2005.05514,

authors:
Fadi Biadsy
Ron J. Weiss
Pedro J. Moreno
Dimitri Kanvesky
Ye. Jia

title: Parrotron: An End-to-End Speech-to-Speech Conversion Model and its Applications Hearing-Impaired Speech and Speech Separation

venue: In Proc. Interspeech,

authors:
W. Chan
N. Jaitly
Q. Le
O. Vinyals

title: Listen, Attend and Spell: A Neural Network for Large Vocabulary Conversational Speech Recognition

authors:
Nanxin Chen
Yu Zhang
Heiga Zen
Ron J Weiss
Mohammad Norouzi
William Chan

title: WaveGrad: Estimating Gradients for Waveform Generation

venue: arXiv preprint arXiv:2009.00713,

authors:
Chung-Cheng Chiu
Anshuman Tripathi
Katherine Chou
Chris Co
Navdeep Jaitly
Diana Jaunzeikare
Anjuli Kannan
Patrick Nguyen
Hasim Sak
Ananth Sankar
Justin Tansuwan
Nathan Wan
Yonghui Wu
Xuedong Zhang

title: Speech Recognition for Medical Conversations

authors:
Jan K Chorowski
Dzmitry Bahdanau
Dmitriy Serdyuk
Kyunghyun Cho
Yoshua Bengio

title: Attention-based models for speech recognition

venue: In Proc. NeurIPS,

authors:
Shaojin Ding
Ye Jia
Ke Hu
Quan Wang

title: Textual Echo Cancellation

venue: arXiv preprint arXiv:2008.06006,

authors:
Jeff Donahue
Sander Dieleman
Mikołaj Bińkowski
Erich Elsen
Karen Simonyan

title: End-to-End Adversarial Text-to-Speech

venue: arXiv preprint arXiv:2006.03575,

authors:
Andrew Gibiansky
Sercan Arik
Gregory Diamos
John Miller
Kainan Peng
Wei Ping
Jonathan Raiman
Yanqi Zhou

title: Deep voice 2: Multi-speaker neural text-to-speech

venue: In Advances in neural information processing systems,

title: Generating Sequences with Recurrent Neural Networks

venue: arXiv preprint arXiv:1308.0850,

authors:
Jiatao Gu
James Bradbury
Caiming Xiong
Victor OK Li
Richard Socher

title: Non-autoregressive neural machine translation

venue: arXiv preprint arXiv:1711.02281,

authors:
Haohan Guo
Frank K Soong
Lei He
Lei Xie

title: A New GAN-based End-to-End TTS Training Algorithm

authors:
Mutian He
Yan Deng
Lei He

title: Robust Sequence-to-Sequence Acoustic Modeling with Stepwise Monotonic Attention for Neural TTS

authors:
Ye Jia
Yu Zhang
Ron J. Weiss
Quan Wang
Jonathan Shen
Fei Ren
Zhifeng Chen
Patrick Nguyen
Ruoming Pang
Ignacio Lopez-Moreno
Yonghui Wu

title: Transfer Learning from Speaker Verification to Multispeaker Text-To-Speech Synthesis

authors:
Ye Jia
Ron J Weiss
Fadi Biadsy
Wolfgang Macherey
Melvin Johnson
Zhifeng Chen
Yonghui Wu

title: Direct Speech-to-Speech Translation with a Sequence-to-Sequence Model

authors:
Jacob Kahn
Morgane Rivière
Weiyi Zheng
Evgeny Kharitonov
Qiantong Xu
Pierre-Emmanuel Mazaré
Julien Karadayi
Vitaliy Liptchinsky
Ronan Collobert
Christian Fuegen
Tatiana Likhomanenko
Gabriel Synnaeve
Armand Joulin
Abdelrahman Mohamed
Emmanuel Dupoux

title: Librilight: A Benchmark for ASR with Limited or No Supervision

authors:
Nal Kalchbrenner
Erich Elsen
Karen Simonyan
Seb Noury
Norman Casagrande
Edward Lockhart
Florian Stimberg
Aaron van den Oord
Sander Dieleman
Koray Kavukcuoglu

title: Efficient Neural Audio Synthesis

authors:
Tom Kenter
Vincent Wan
Chun-An Chan
Rob Clark
Jakub Vit

title: CHiVE: Varying Prosody in Speech Synthesis with a Linguistically Driven Dynamic Hierarchical Conditional Variational Network

authors:
Diederik P Kingma
Max Welling

title: Auto-Encoding Variational Bayes

authors:
Kundan Kumar
Rithesh Kumar
Thibault de Boissiere
Lucas Gestin
Wei Zhen Teoh
Jose Sotelo
Alexandre de Brebisson
Yoshua Bengio
Aaron Courville

title: MelGAN: Generative Adversarial Networks for Conditional Waveform Synthesis

authors:
Younggun Lee
Taesu Kim

title: Robust and fine-grained prosody control of end-to-end speech synthesis

authors:
Naihan Li
Shujie Liu
Yanqing Liu
Sheng Zhao
Ming Liu

title: Neural Speech Synthesis with Transformer Network

venue: In Proc. AAAI,

authors:
Dan Lim
Won Jang
Hyeyeong Park
Bongwan Kim
Jesam Yoon

title: JDI-T: Jointly Trained Duration Informed Transformer for Text-To-Speech without Explicit Alignment

venue: arXiv preprint arXiv:2005.07799,

authors:
Minh-Thang Luong
Hieu Pham
Christopher D Manning

title: Effective approaches to attention-based neural machine translation

venue: arXiv preprint arXiv:1508.04025,

authors:
Aäron van den Oord
Sander Dieleman
Heiga Zen
Karen Simonyan
Oriol Vinyals
Alex Graves
Nal Kalchbrenner
Andrew Senior
Koray Kavukcuoglu

title: WaveNet: A Generative Model for Raw Audio

venue: arXiv preprint arXiv:1609.03499,

authors:
Vassil Panayotov
Guoguo Chen
Daniel Povey
Sanjeev Khudanpur

title: Librispeech: An ASR Corpus Based on Public Domain Audio Books

authors:
Daniel S Park
Yu Zhang
Ye Jia
Wei Han
Chung-Cheng Chiu
Bo Li
Yonghui Wu
Quoc V Le

title: Improved Noisy Student Training for Automatic Speech Recognition

authors:
Wei Ping
Kainan Peng
Andrew Gibiansky
Sercan O Arik
Ajay Kannan
Sharan Narang
Jonathan Raiman
John Miller

title: Deep Voice 3: Scaling text-to-speech with convolutional sequence learning

authors:
Ryan Prenger
Rafael Valle
Bryan Catanzaro

title: WaveGlow: A Flow-based Generative Network for Speech Synthesis

authors:
Yi Ren
Yangjun Ruan
Xu Tan
Tao Qin
Sheng Zhao
Zhou Zhao
Tie-Yan Liu

title: FastSpeech: Fast, Robust and Controllable Text to Speech

authors:
Yi Ren
Chenxu Hu
Tao Qin
Sheng Zhao
Zhou Zhao
Tie-Yan Liu

title: FastSpeech 2: Fast and High-Quality End-to-End Text-to-Speech

venue: arXiv preprint arXiv:2006.04558,

authors:
Jonathan Shen
Ruoming Pang
Ron J. Weiss
Mike Schuster
Navdeep Jaitly
Zongheng Yang
Zhifeng Chen
Yu Zhang
Yuxuan Wang
RJ Skerrv-Ryan
Rif A. Saurous
Yannis Agiomyrgiannakis
Yonghui Wu

title: Natural TTS Synthesis by Conditioning WaveNet on Mel Spectrogram Predictions

authors:
RJ Skerry-Ryan
Eric Battenberg
Ying Xiao
Yuxuan Wang
Daisy Stanton
Joel Shor
Ron Weiss
Rob Clark
Rif A Saurous

title: Towards End-to-End Prosody Transfer for Expressive Speech Synthesis with Tacotron

authors:
Jose Sotelo
Soroush Mehri
Kundan Kumar
Joao Felipe Santos
Kyle Kastner
Aaron C. Courville
Yoshua Bengio

title: Char2Wav: End-to-End speech synthesis

venue: In Proc. ICLR workshop,

authors:
Guangzhi Sun
Yu Zhang
Ron J Weiss
Yuan Cao
Heiga Zen
Yonghui Wu

title: Fully-Hierarchical Fine-Grained Prosody Modeling for Interpretable Speech Synthesis

authors:
David Talkin
Colin W Wightman

title: The aligner: Text to speech alignment using markov models and a pronunciation dictionary

venue: In The Second ESCA/IEEE Workshop on Speech Synthesis,

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N. Gomez
Lukasz Kaiser
Illia Polosukhin

title: Attention Is All You Need

venue: In Proc. NIPS,

authors:
Yuxuan Wang
RJ Skerry-Ryan
Daisy Stanton
Yonghui Wu
Ron J Weiss
Navdeep Jaitly
Zongheng Yang
Ying Xiao
Zhifeng Chen
Samy Bengio
Q. Le
Y. Agiomyrgiannakis
R. Clark

title: Saurous. Tacotron: Towards End-to-End Speech Synthesis

authors:
Ronald J. Williams
David Zipser

title: A Learning Algorithm for Continually Running Fully Recurrent Neural Networks

venue: Neural Computation,

authors:
Chengzhu Yu
Heng Lu
Na Hu
Meng Yu
Chao Weng
Kun Xu
Peng Liu
Deyi Tuo
Shiyin Kang
Guangzhi Lei
Dan Su
Dong Yu

title: DurIAN: Duration informed attention network for multimodal synthesis

authors:
H. Zen
K. Tokuda
A. Black

title: Statistical Parametric Speech Synthesis

venue: Speech Communication,

authors:
Heiga Zen
Andrew Senior
Mike Schuster

title: Statistical Parametric Speech Synthesis Using Deep Neural Networks

authors:
Heiga Zen
Viet Dang
Rob Clark
Yu Zhang
Ron J Weiss
Ye Jia
Zhifeng Chen
Yonghui Wu

title: LibriTTS: A Corpus Derived from LibriSpeech for Text-to-Speech

authors:
Zhen Zeng
Jianzong Wang
Ning Cheng
Tian Xia
Jing Xiao

title: AlignTTS: Efficient Feed-Forward Text-to-Speech System without Explicit Alignment

authors:
Jing-Xuan Zhang
Zhen-Hua Ling
Li-Rong Dai

title: Forward attention in sequence-to-sequence acoustic modeling for speech synthesis

authors:
Zewang Zhang
Qiao Tian
Heng Lu
Ling-Hui Chen
Shan Liu

title: Adadurian: Few-shot adaptation for neural text-to-speech with durian

venue: arXiv preprint arXiv:2005.05642,

authors:
Yibin Zheng
Jianhua Tao
Wen. Zhengqi
Jiangyan Yi

title: Forward–backward decoding sequence for regularizing end-to-end tts

venue: IEEE/ACM Trans. Audio Speech & Lang. Process.,

heading: 1 INTRODUCTION

text:
Autoregressive neural text-to-speech (TTS) models using an attention mechanism are known to be able to generate speech with naturalness on par with recorded human speech. However, these types of models are known to be less robust than traditional approaches (He et al., 2019; Zheng et al., 2019; Guo et al., 2019; Battenberg et al., 2020). These autoregressive networks that predict the output one frame at a time are trained to decide whether to stop at each frame, and thus a misprediction on a single frame can result in serious failures such as early cut-off. Meanwhile, there are little to no hard constraints imposed on the attention mechanism to prevent problems such as repetition, skipping, long pause or babbling. To exacerbate the issue, these failures are rare and are thus often not represented in small test sets, such as those used in subjective listening tests. However, in customer-facing products, even a one-in-a-million chance of such problems can severely degrade the user experience.
There have been various works aimed at improving the robustness of autoregressive attention-based neural TTS models. Some of them investigated reducing the effect of the exposure bias on the autoregressive decoder, using adversarial training (Guo et al., 2019) or adding regularization to encourage the forward and backward attention to be consistent (Zheng et al., 2019). Others utilized or designed alternative attention mechanisms, such as Gaussian mixture model (GMM) attention (Graves, 2013; Skerry-Ryan et al., 2018), forward attention (Zhang et al., 2018), stepwise monotonic attention (He et al., 2019), or dynamic convolution attention (Battenberg et al., 2020). Nonetheless, these approaches do not fundamentally solve the robustness issue.
Recently, there has been a surge in the use of non-autoregressive models for TTS. Rather than predicting whether to stop on each frame, non-autoregressive models need to determine the output length ahead of time, and one way to do so is with an explicit prediction of the duration for each input token. A side benefit of such a duration predictor is that it is significantly more resilient to the failures afflicting the attention mechanism.
However, one-to-many regression problems like TTS can benefit from an autoregressive decoder as the previous mel-spectrogram frames provides context to disambiguate between multi-modal outputs.
In this paper, we propose, Non-Attentive Tacotron1, a neural TTS model that combines the robust duration predictor with the autoregressive decoder of Tacotron 2 (Shen et al., 2018).
Our work is similar to DurIAN (Yu et al., 2019; Zhang et al., 2020), which incorporates the duration predictor with an autoregressive decoder. But besides the differences in architecture, we also introduce a couple of novel features in our model.
The key contributions of this paper are summarized as follows:
1. Replacing the attention mechanism in Tacotron 2 with duration prediction and upsampling modules leading to better robustness with the naturalness matching recorded natural speech;
2. Introduction of Gaussian upsampling significantly improving the naturalness compared to vanilla upsampling through repetition;
3. Global and fine-grained controlling of durations at inference time;
4. Semi-supervised and unsupervised duration modeling of Non-Attentive Tacotron, allowing the model to be trained with few to no duration annotations; and
5. More reliable evaluation metrics for measuring robustness of TTS models, as well as comparing Non-Attentive Tacotron with Tacotron 2 with respect to those metrics.

heading: 2 RELATED WORKS

text:
In the past decade, model-based TTS synthesis has evolved from hidden Markov model (HMM)-based approaches (Zen et al., 2009) to using deep neural networks. Over this period, the concept of using an explicit representation of token (phoneme) durations has not been foreign. Early neural parametric synthesis models (Zen et al., 2013) require explicit alignments between input and target and include durations as part of the bag of features used to generate vocoder parameters. Explicit durations continue to be used with the advent of the end-to-end neural vocoder WaveNet (Oord et al., 2016) in works such as Deep Voice (Arik et al., 2017; Gibiansky et al., 2017) and CHiVE (Kenter et al., 2019).
As general focus turned towards end-to-end approaches, the autoregressive sequence-to-sequence model with attention mechanism used in neural machine translation (NMT) (Bahdanau et al., 2015) and automatic speech recognition (ASR) (Chan et al., 2016) became an attractive option, removing the need to represent durations explicitly. This led to works such as Char2Wav (Sotelo et al., 2017), Tacotron (Wang et al., 2017; Shen et al., 2018), Deep Voice 3 (Ping et al., 2018), and Transformer TTS (Li et al., 2019). Similar models have been used for more complicated problems, like direct speech-to-speech translation (Jia et al., 2019), speech conversion (Biadsy et al., 2019), and speech enhancement (Ding et al., 2020).
Tacotron 2, on which our work is based, is one such model. It connects a character-level encoder and an autoregressive decoder producing mel spectrogram frames with the use of a location-sensitive attention mechanism (Chorowski et al., 2015).
Recently, there has been a surge of non-autoregressive models, bringing back the use of explicit duration prediction. This approach initially surfaced in NMT (Gu et al., 2017), then made its way into TTS with models such as FastSpeech (Ren et al., 2019; 2020), AlignTTS (Zeng et al., 2020), TalkNet (Beliaev et al., 2020), and JDI-T (Lim et al., 2020). See Appendix C for a rough categorization of these models.
To train the duration predictor, FastSpeech uses target durations extracted from a pre-trained autoregressive model in teacher forcing mode, while JDI-T also extracts target durations from a separate autoregressive model but co-trains it with the feed-forward model. TalkNet uses a CTC-based ASR model to extract target durations, while CHiVE, FastSpeech 2, and DurIAN use target durations from an external aligner module utilizing forced alignment. Finally, AlignTTS forgoes target durations completely and uses a specialized alignment loss inspired by the Baum-Welch algorithm to train a mixture density network for alignment.
1Audio samples available in supplemental materials.

heading: 3 MODEL

text:
Modern neural TTS models typically consist of two separate networks: (1) a feature generation network that transforms input tokens (e.g., grapheme or phoneme ids) into acoustic features (e.g., mel-spectrogram), and (2) a vocoder network that transforms the acoustic features into a time-domain audio waveform. This paper focuses on the feature generation network, and can be used with any vocoder network, e.g., WaveNet (Oord et al., 2016), WaveRNN (Kalchbrenner et al., 2018), WaveGlow (Prenger et al., 2019), MelGAN (Kumar et al., 2019), or WaveGrad (Chen et al., 2020). The architecture of Non-Attentive Tacotron is illustrated in Figure 1a. See Appendix A for specific parameter value settings.
The model follows that of Tacotron 2 (Shen et al., 2018), transforming input idsX = (x1, . . . ,xN ) of length N into mel-spectrogram predictions Y = (y1, . . . ,yT ) of size T ×K. Phonemes are used as inputs, and include a silence token at word boundaries as well as an end-of-sequence token. The ids are used to index into a learned embedding and is then passed through an encoder consisting of 3 × (dropout, batch normalization, convolution) layers followed by a single bi-directional LSTM with ZoneOut to generate a 2-dimensional output of length N . This output is concatenated with a speaker embedding vector to produce the final encoder outputH = (h1, ...,hN ).
The autoregressive decoder also follows Tacotron 2, and predicts mel-spectrograms one frame at a time. At training time, teacher forcing (Williams & Zipser, 1989) is employed and the previous groundtruth mel-spectrogram frame is used as input, while at inference time the previous predicted mel-spectrogram frame is used. This previous frame is passed through a pre-net containing two fully-connected layers of ReLU units with dropout, then concatenated with an upsampled (aligned) encoder output corresponding to the current frame. The upsampled encoder outputs for future frames are not visible to the decoder at the current frame. In Tacotron 2, this upsampling or alignment is achieved using a location-sensitive attention mechanism (Chorowski et al., 2015), while in this work the attention mechanism is not used and a separate upsampling mechanism described later is used in its stead. The result is then passed through two uni-directional LSTM layers with ZoneOut. The LSTM output is concatenated with the upsampled encoder output yet again then projected to the mel-spectrogram dimension as frames of a preliminary predicted spectrogram Y ′. Once all the mel-spectrogram frames have been predicted, they are passed through a 5-layer batch normalized convolutional post-net with tanh activation on all except the last layer. The post-net predicts a residual to add to the prediction Y ′ to obtain the final prediction Y .
In place of the attention mechanism used in Tacotron 2, duration-based models upsample the encoder outputs using per-token duration information. This can be done by simply repeating each encoder
output by its duration as in FastSpeech (Ren et al., 2019), but instead we adopt a different process we call Gaussian upsampling, which is described in subsection 3.1. Note that while durations in seconds are used for loss computation, they are converted to durations in integer frames for upsampling.
For Gaussian upsampling, a duration and a range parameter must be predicted for each token. The range parameter is called thus because it controls the range of a token’s influence. The duration predictor passes the encoder output through two bi-directional LSTM layers followed by a projection layer to predict the numeric duration d = (d1, . . . , dN ) for each input token. During training, these predicted durations are only used for loss computation, and the target durations are used instead in the upcoming steps2. The range parameter predictor passes the encoder output concatenated with durations through two bi-directional LSTM layers followed by a projection layer and a SoftPlus activation to predict a positive range parameter σ for each input token.
After the encoder outputs are upsampled, a Transformer-style sinusoidal positional embedding (Vaswani et al., 2017) is concatenated. The positional embedding tracks the index of each upsampled frame within each token; if the duration values are [2, 1, 3], the indices for the positional embedding would be [1, 2, 1, 1, 2, 3].
The model is trained using a combination of duration prediction loss and mel-spectrogram reconstruction loss. The duration prediction loss is the L2 loss between predicted and target durations in seconds, and the mel-spectrogram reconstruction loss is a L1 + L2 loss between the predicted and the groundtruth mel-spectrogram both before and after the post-net (following Jia et al. (2018)).
L = Lspec + λdurLdur (1)
Ldur = 1
N ‖d− d∗‖22 (2)
Lspec = 1
TK T∑ t=1 ( ‖y′t − y∗t ‖1 + ‖y ′ t − y∗t ‖ 2 2 + ‖yt − y ∗ t ‖1 + ‖yt − y ∗ t ‖ 2 2 ) (3)

heading: 3.1 GAUSSIAN UPSAMPLING

text:
Given a sequence of vectors to be upsampled H = (h1, . . . ,hN ), integer duration values d = (d1, . . . , dN ), and range parameter values σ = (σ1, . . . , σN ), we compute the upsampled vector sequence U = (u1, . . . ,uT ) as:
ci = di 2 + i−1∑ j=1 dj , wti = N ( t; ci, σ 2 i )∑N j=1N ( t; cj , σ2j ) , ut = N∑ i=1 wtihi
That is, we place a Gaussian distribution with standard deviation σi at the center of the output segment corresponding to the i-th input token as determined by the duration values d, and for each frame we take a weighted sum of the encoder outputs in accordance with the values of Gaussian distributions at that frame. This is similar to the softmax-based aligner in Donahue et al. (2020), except a learned σ rather than a fixed temperature hyperparameter is used here.
Compared with vanilla upsampling by repetition (as in Ren et al. (2019)), which can be seen as a case of learning a hard monotonic attention, Gaussian upsampling results in an alignment that is more akin to single-component GMM attention. Another benefit of Gaussian upsampling is that it is fully differentiable, which is critical to semi-supervised and unsupervised duration modeling (section 4) as it allows the gradients from the spectrogram losses to flow through to the duration predictor.

heading: 3.2 TARGET DURATIONS

text:
Neural TTS models using duration need alignments between input tokens and output features. This can be accomplished by implementing an aligner module in the model or by using an external aligner.
2Note that target durations may not be required with semi-supervised and unsupervised duration modeling. See section 4.
In our work, target durations are extracted by an external, flatstart trained, speaker-dependent HMMbased aligner with a lexicon (Talkin & Wightman, 1994). However, sometimes it is difficult to train a reliable aligner model and/or extract accurate alignments due to data sparsity, poor recording conditions, or unclear pronunciations. To address this problem, we introduce semi-supervised and unsupervised duration modeling.

heading: 4 SEMI-SUPERVISED AND UNSUPERVISED DURATION MODELING

text:
A naı̈ve approach to unsupervised duration modeling would be to simply train the model using the predicted durations (instead of the target durations) for upsampling, and use only mel-spectrogram reconstruction loss for optimization. To match the length between the predicted durations and the target mel-spectrogram frames, the predicted per-token durations can be scaled by T/ ∑ i di. In
addition to that, an utterance-level duration loss Lu = 1N (T − ∑ i di) 2 could be added to the total loss. However, experiments show that such an approach does not produce satisfying naturalness in the synthesized speech (subsection 6.3).
The proposed unsupervised duration modeling is illustrated in Figure 1b. We instead utilize a fine-grained VAE (FVAE) similar to Sun et al. (2020) to model the alignment between the input tokens and the target mel-spectrogram frames, and extract per-token latent features from the target mel-spectrogram based on this alignment. The token encoder output H is aligned to the target spectrogram Y ∗ using an attention mechanism following Lee & Kim (2019):
ci = Attn(hi, fspec(Y ∗)),
where hi is used as the query in the attention, and fspec is a spectrogram encoder whose output per frame is used as the values in the attention. A simple dot-product attention from Luong et al. (2015) was used in this work. A latent feature zi is then computed from ci and hi using a variational auto-encoder (VAE) (Kingma & Welling, 2014) with a Gaussian prior N (0, I), optimized through the evidence lower bound (ELBO):
log p (Y |H) ≥ − ∑ i DKL (q (zi | hi, ci) ‖ p (zi)) + Eq(zi|hi,ci) [log p (Y |H,Z)] (4)
where the first term is the KL divergence between the prior and posterior, and the second term can be approximated by drawing samples from the posterior.
Because these latent features are extracted from the target spectrogram with an alignment, they are capable of carrying duration related information. At training time, the per-token duration d is predicted from the concatenation of the token encoder output H and the posterior latent Z; while at inference time, the prior latent is used for Z (either sampled from the distribution or using the distribution mode), and the internal attention mechanism of the FVAE is not used.
Unlike Sun et al. (2020), scheduled sampling was not utilized for factorizing latent dimensions. These latent features are only used for duration prediction, and are not used for range parameter prediction or mel-spectrogram reconstruction. We also cap the range parameters for each token to twice its predicted duration in this setup for better training stability. As in section 3, durations predicted in seconds are used for loss computation, but are converted to durations in integer frames for upsampling.
The overall loss used for semi-supervised and unsupervised training is thus
L = Lspec + λdurLdur + λuLu + λKLDKL, (5) where DKL and Lspec correspond to the first and second terms in Equation 4, respectively, and Ldur is only counted for examples with target duration labels (i.e. supervised examples). The last three terms are all weighted per valid token.

heading: 5 ROBUSTNESS EVALUATION

text:
Previous work typically evaluated the robustness of TTS systems on a small set of handpicked “hard cases” (He et al., 2019; Zheng et al., 2019; Guo et al., 2019). Although such evaluation is helpful for guiding improvements, it is not reflective of the overall robustness of the system. The handpicked
samples may be biased to the weaknesses of a certain system, and is prone to lead further optimization to overfit to the specific evaluation set.
In this work, we evaluate the robustness of TTS systems on large evaluation sets in an automated way by leveraging existing ASR systems. We run ASR and forced alignment evaluations on the synthesized speech against the verbalized text, and report two metrics measuring over- and under-generation:
1. Unaligned duration ratio (UDR): The synthesized speech is forced aligned with the verbalized input text using an ASR system. Each token in the input text is aligned to a segment in the synthesized audio. Any long audio segments (> 1 second) not aligned to any input token are typically due to over-generation from the TTS system, such as long pauses, babbling, word repetitions, or failures to stop after finishing the utterance. The total duration of such long unaligned segments divided by the total output duration is the UDR. Note that short unaligned segments are ignored. If the synthesized speech is unable to be aligned with the input text, it is considered as having a UDR of 100%.
2. ASR word deletion rate (WDR): This is the deletion error portion in a standard ASR word error rate (WER) evaluation. Under-generation in the synthesized speech, such as early cutoff and word skipping, is reflected by a higher WDR.
As the ASR system will make mistakes, the metrics above are just an upper-bound on the actual failures of the TTS system.

heading: 6 EXPERIMENTS

text:
All models were trained on a proprietary dataset with 66 speakers with 4 different English accents (US, British, Australian, and Nigerian). The amount of data per speaker varied from merely 5 seconds to 47 hours, totaling 354 hours.
A preliminary experiment comparing different attention mechanisms (including monotonic, stepwise monotonic, dynamic convolution and GMM attention (GMMA)) showed that GMMA performed the best. We therefore compared our non-attentive Tacotron not only with Tacotron 2 with locationsensitive attention (LSA) which was used in the original Tacotron 2 paper but also with Tacotron 2 with GMMA. The Tacotron 2 models used reduction factor 2 and L1 + L2 loss.
Following Shen et al. (2018), predicted features were obtained in teacher-forcing mode from a Tacotron 2 model and used to train a WaveRNN vocoder which was then used for all experiments.

heading: 6.1 NATURALNESS

text:
The naturalness of the synthesized speech was evaluated through subjective listening tests, including 5-scale Mean Opinion Score (MOS) tests and side-by-side preference tests. The sentences were synthesized using 10 US English speakers (5 male / 5 female) in a round-robin fashion. The amount of training data for the evaluated speakers varied from 3 hours to 47 hours.
Table 1 contains MOS results. Non-Attentive Tacotron with Gaussian upsampling matched Tacotron 2 (GMMA) in naturalness, and both were close to the groundtruth audio. A preference test between
Non-Attentive Tacotron and Tacotron 2 (GMMA) further confirmed this result, as shown in Figure 2. Non-Attentive Tacotron with vanilla (repeating) upsampling was rated as significantly less natural than with Gaussian upsampling.
The effectiveness of a learned range parameter versus a fixed temperature hyperparameter set at 10.0 as per Donahue et al. (2020) is compared using a preference test in Table 2. While there is only a slight perceived benefit in using a learned range parameter, it reduces the need to tune another dataset-dependent hyperparameter. Additionally, in multi-speaker setups it is possible that the optimal σ may be speaker-dependent.
6.2 PACE CONTROL
Table 3 shows WER and MOS results after modifying the utterance-wide pace by dividing the predicted durations by various factors. The WER is computed on speech synthesized on transcripts from the LibriTTS test-clean subset with the same 10 speakers in subsection 6.1, and then transcribed by an ASR model described in Park et al. (2020) with a WER of 2.3% on the ground truth audio.
With pace between 0.8× – 1.25×, the WERs were hardly impacted. The WER was significantly worse when the pace was increased to 1.5× normal, partially because the ASR model used was not optimized for speech so fast. In contrast, the subjective MOS decreased rapidly when the pace was sped up or slowed down significantly. However, most of the comments from raters were simply complaining about the pace, such as “too slow to be natural” (0.8x) or “way too fast” (1.25x).
Non-Attentive Tacotron is also able to control the pace of the synthesized speech at a finer granularity, such as per-word or per-phoneme, while still maintain the naturalness of the synthesized speech. Figure 3 shows examples of controlling the pace for specific words in a sentence.

heading: 6.3 SEMI-SUPERVISED AND UNSUPERVISED DURATION MODELING

text:
Ten different US English speakers (5 male / 5 female) each with about 4 hours of training data were used for evaluating the performance of the unsupervised and semi-supervised duration modeling.
The duration labels for these 10 speakers (i.e. about 11% of the training data) were withheld for the semi-supervised models, and all duration labels were withheld for the unsupervised models.
Figure 4 shows predicted alignment after Gaussian upsampling and the internal alignment from the attention module in the FVAE compared with the alignment computed from the target durations, for the unsupervised model. Despite not having access to any target durations, both the FVAE and duration predictor were able to produce an alignment close to that computed from the target durations.
As shown in Table 4, with the use of the FVAE, the naturalness of both semi-supervised and unsupervised models were very close to that of the supervised models, even though duration prediction errors were higher. The autoregressive decoder trained with teacher forcing may have been powerful enough to correct the duration prediction errors to some degree. However, the naturalness degraded significantly without the use of the FVAE. Although the duration error from the semi-supervised model without FVAE was lower than that from the unsupervised model with FVAE, the former was significantly less natural than the latter. This may be due to a lower consistency between supervised and unsupervised speakers without FVAE.
Although these models were close to the supervised model in MOS, manual investigation found that samples from both semi-supervised models and unsupervised models had a small chance of containing slight errors that do not occur in the supervised model, such as unclear pronunciations, phoneme repetitions, or extra pauses. However, they are significantly less severe than similar errors from Tacotron 2, mostly impacting just one or a few phonemes. These errors are further confirmed in the large scale robustness evaluation (subsection 6.4).
The utterance-wide or fine-grained pace control (subsection 6.2) can be applied to the semi-supervised and unsupervised models as well. However, as the alignments are not as accurate, the synthesized speech with fine-grained pace control are not as natural as from the supervised model. The duration may be extended by simply inserting more silence, and the extended portion may include phoneme repetitions or unclear pronunciations.

heading: 6.4 ROBUSTNESS

text:
We evaluated the robustness of the neural TTS models by measuring UDR and WDR on two large evaluation sets: LibriTTS: 354K sentences from all train subsets from the LibriTTS corpus (Zen et al., 2019); and web-long: 100K long sentences mined from the web, which included a small amount of irregular text such as programming code. The median text lengths of the two sets were 74 and 224 characters, respectively. The input was synthesized using the same 10 speakers in subsection 6.3 in a round-robin fashion. All model outputs were capped at 120 seconds.
We used the ASR model trained on the LibriSpeech (Panayotov et al., 2015) and LibriLight (Kahn et al., 2020) corpora from Park et al. (2020) for measuring WDR, and a confidence islands-based forced alignment model (Chiu et al., 2018) for measuring UDR.
Table 5 shows the robustness metrics for Tacotron 2 and Non-Attentive Tacotron. Tacotron 2 (LSA) suffered from severe over-generation as measured by UDR, especially on long inputs. Manual investigation uncovered that they were typically long babbling or long silence, often at the end (failure to stop). It also had a high level of under-generation as measured by WDR, typically due to early cutoff. Tacotron 2 (GMMA) performed almost as well as the supervised Non-Attentive Tacotron in WDR because of its soft monotonic nature, which made end-of-sentence prediction easier. However, it still had significantly higher level of over-generation compared to Non-Attentive Tacotron, even when unsupervised or semi-supervised duration modeling is used for the latter. The robustness of semi-supervised and unsupervised Non-Attentive Tacotron is significantly worse than the supervised one. Manual investigation uncovered that the typical failure pattern is that part of the spectrogram is not correctly synthesized (often as silence, but sometimes as babbling), despite that the duration prediction seems reasonable. Such failure pattern contributes to both UDR and WDR. This indicates further improvements to be made. Even then, the semi-supervised and unsupervised Non-Attentive Tacotron still performs significantly better on over-generation compared to Tacotron 2.
In practice, we also observed that Tacotron 2 required significantly more care in data preprocessing to achieve this level of robustness, including consistent trimming of leading and trailing silences and filtering out utterances with long pauses. On the other hand, Non-Attentive Tacotron is significantly less sensitive to the data preprocessing steps.

heading: 7 CONCLUSIONS

text: This paper presented Non-Attentive Tacotron, showing a significant improvement in robustness compared to Tacotron 2 as measured by unaligned duration ratio and word deletion rate, while also slightly outperforming it in naturalness. This was achieved by replacing the attention mechanism in Tacotron 2 with an explicit duration predictor and Gaussian upsampling. We demonstrated the ability to control the pacing of the entire utterance as well as individual words using the duration predictor. We also described a method of modeling duration in a semi-supervised or unsupervised manner using Non-Attentive Tacotron when accurate target duration are scarce or unavailable by using a fine-grained variational auto-encoder, with results almost as good as supervised training.

heading: A MODEL PARAMETERS

heading: C CLASSIFICATION OF SOME TTS MODELS

heading: B WER BREAKDOWNS IN THE ROBUSTNESS EVALUATION

title: CONTROLLABLE NEURAL TTS SYNTHESIS INCLUDING UNSUPERVISED DURATION MODELING