Sylvain Gelly

Marc Schoenauer

Michèle Sebag

Olivier Teytaud

Levente Kocsis

David Silver

Csaba Szepesvári

The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions

The ancient oriental game of Go has long been considered a grand challenge for artificial intelligence. For decades, computer Go has defied the classical methods in game tree search that worked so successfully for chess and checkers. However, recent play in computer Go has been transformed by a new paradigm for tree search based on Monte-Carlo methods. Programs based on Monte-Carlo tree search now play at human-master levels and are beginning to challenge top professional players. In this paper we describe the leading algorithms for Monte-Carlo tree search and explain how they have advanced the state of the art in computer Go.

INTRODUCTION

Sequential decision making has been studied in a number of fields, ranging from optimal control to operations research to artificial intelligence (AI). The challenge of sequential decision making is to select actions that maximise some long term objective (e.g., winning a game), when the consequences of those actions may not be revealed for many steps. In this paper we shall focus on a new approach to sequential decision making that was developed recently in the context of two-player games.

Classic two-player games are excellent testbeds for AI. They provide closed micro-worlds with simple rules that have been selected and refined over hundreds or thousands of years so as to challenge human players. They also provide clear benchmarks of performance both between different programs and against human intelligence.

In two-player games such as chess, checkers, othello and backgammon, human levels of performance have been exceeded by programs that combine brute force tree-search with human knowledge or reinforcement learning [START_REF] Schaeffer | The games computers (and people) play[END_REF].

For over three decades however, these approaches and others have failed to achieve equivalent success in the game of Go. The size of the search space in Go is so large that it defies brute force search. Furthermore, it is hard to characterize the strength of a position or move. For these reasons, Go remains a grand challenge of artificial intelligence; the field awaits a triumph analogous to the 1997 chess match in which Deep Blue defeated the world champion Gary Kasparov [START_REF] Schaeffer | The games computers (and people) play[END_REF].

The last five years have witnessed considerable progress in computer Go. With the development of new Monte-Carlo algorithms for tree search [START_REF] Coulom | Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search[END_REF][START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF], computer Go programs have achieved some remarkable successes [?, 18], including several victories against top professional players. The ingredients of these programs are deceptively simple. They are provided with minimal prior knowledge about the game of Go, and instead they acquire their expertise online by simulating random games in self-play. The algorithms are called Monte-Carlo tree search (MCTS) methods because they build and expand a search tree while evaluating the strength of individual moves by their success during randomized play.

THE GAME OF GO

The game of Go is an ancient two-player board game that originated in China. It is estimated that there are 27 million Go players worldwide. The game of Go is noted for its simple rules but many-layered complexity.

The Rules of Go

The black and white players alternate turns. On each turn they place a single stone of their corresponding color on an N × N board. The standard board size is 19 × 19, but smaller boards, namely, boards of size 9 × 9 and 13 × 13 are also played to a lesser extent in competitive play, for study, and also for computer Go development. A group is a connected set of stones (using 4-connectivity) of the same color. A liberty is an empty location that is adjacent to a The first victory of a computer program, Fuego (White) against a 9 dan professional Go player, Zhou Junxun (Black), in an even game.

group. A group is captured when it has no more liberties. The stones of a captured group are removed from the board. It is illegal to play suicidal moves that would result in self capture. A group is termed dead when it is inevitable that it will be captured. The aim of the game is to secure more territory than the other player. Informally, territory describes the empty locations on the board that are unambiguously controlled by one player. The game ends when both players pass, at which time the two players count their scores. Each player receives one point for every location of territory that they control, and one point for each captured stone. White receives a bonus, known as komi, compensating for the fact that black played first. The player with the highest score wins. The precise scoring details vary according to regional rules; however, all major scoring systems almost always lead to the same result. Figure 1 shows a complete game of 9 × 9 Go.

The handicap is the number of compensation stones that the black player is allowed to place on the board before alternating play. The goal of handicap is to allow players of different strength to play competitively. "Even games" are games with handicap 0 and a komi of 7.5 (the komi can vary according to regional rules).

The ranks of amateur Go players are ordered by decreasing kyu and then increasing dan, where the difference in rank corresponds to the number of handicap stones required to maintain parity. Professional players are ordered by increasing dan, on a second scale (Figure 2). The title "top professional" is given to a professional player who has recently won at least one major tournament.

Go: A Grand Challenge for AI

Since the introduction of Monte-Carlo tree search in 2006, the ranks of computer Go programs have jumped from weak kyu level to the professional dan level in 9 × 9 Go, and to strong amateur dan level in 19 × 19 Go (see Section 5).

The game of Go is difficult for computer programs for a number of reasons. First, the combinatorial complexity of the game is enormous. There are many possible moves in each turn: approximately 200 in Go, compared to 37 for chess. Furthermore, the length of a typical game is around 300 turns, compared to 57 in chess. In fact, there are more than 10 170 possible positions in Go, compared to 10 47 in chess; and approximately 10 360 legal move sequences in Go, compared to 10 123 in chess [START_REF] Schaeffer | The games computers (and people) play[END_REF].

Another factor that makes Go challenging is the long-term influence of moves: the placement of a stone at the beginning of the game can significantly affect the outcome of the game hundreds of moves later. Simple heuristics for evaluating a position, such as counting the total material advantage, have proven to be very successful in chess and checkers. However, they are not as helpful in Go since the territorial advantage of one player is often compensated by the opponent's better strategic position. As a result, the best known heuristic functions evaluate positions at beginner level. All this makes the game of Go an excellent challenge for AI techniques, since a successful Go program must simultaneously cope with the vast complexity of the game, the long-term effects of moves, and the importance of the strategic values of positions. Many real-world, sequential decision making problems are difficult for exactly the same reasons. Therefore, progress in Go can lead to advances that are significant beyond computer Go and may ultimately contribute to advancing the field of AI as a whole. One support for this claim is the fact that Monte-Carlo tree search, which was originally introduced in Go, has already started to achieve notable successes in other areas within AI [START_REF] Zinkevich | Optimal unbiased estimators for evaluating agent performance[END_REF][START_REF] Nakhost | Monte-Carlo exploration for deterministic planning[END_REF].

MONTE-CARLO TREE SEARCH

The common approach used by all the strongest current computer Go programs is Monte-Carlo tree search (MCTS) [START_REF] Coulom | Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search[END_REF]. In this section, we first introduce game trees and discuss traditional approaches to game tree search. Next, we discuss how Monte-Carlo techniques can be used to evaluate positions. Finally, we introduce the UCT strategy [START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF], which guides the development of the search tree towards positions with large estimated value or high uncertainty.

Game Tree Search

We begin by discussing search algorithms for two-player games in general. In such games, there are two players, whom we shall call Black and White. The players move in an alternating manner and the games are assumed to be deterministic and to be perfect information. Determinism rules out games of chance involving, e.g., dice throws or shuffled cards in a deck. Perfect information rules out games where the players have private information such as cards that are hidden from the other players. More specifically, perfect information means that, knowing the rules of the game, each player can compute the distribution of game outcomes (which is a single game outcome, if deterministic) given any fixed future sequence of actions. Another way of putting this latter condition is to say that both players have perfect knowledge of the game's state. In board games such as Go, chess and checkers, disregarding subtleties such as castling restrictions in chess and ko rules in Go, the state is

-2 -2 +7 -2 +9 -4 -4 +5 +9 -6 -4 -4 -2 +7 +3 max min max min a 1 a 2 b 1 b 2 b 1 b 2 a 1 a 2 a 1 a 2 a 1 a 2 a 1 a 2
Figure 3: A minimax game tree for a small twoplayer game. Black selects actions to maximise his value; White selects actions to minimise her value.

identical to the board position, i.e., the configuration of all pieces on the board. The rules of the game determine the terminal states in which the game ends. There is a reward associated with each terminal state, which determines how much Black earns if the game ends in that state. There are no intermediate rewards, i.e., the reward associated with each non-terminal state is zero. The goal of Black is to get the highest final reward, while the goal of White is to minimize Black's reward.

A game tree organizes the possible future action sequences into a tree structure. The root of the tree represents the initial state (and the empty action sequence), while each other node represents some non-empty, finite action sequence of the two players. Each finite action sequence leads deterministically to a state, which we associate with the node corresponding to that action sequence (Fig. 3).

Note that the same state can be associated with many nodes of the tree, because the same state can often be reached by many distinct action sequences, known as transpositions. In this case, the game can be represented more compactly by a directed acyclic graph over the set of states.

The optimal value of a game tree node is the best possible value the player at that node can guarantee for himself, assuming that the opponent plays the best possible counterstrategy. The mapping from the nodes (or states) to these values is called the optimal value function. Similarly, the optimal action value of a move at a node is defined to be the optimal value of the child node for that move.

If the optimal values of all children are known, then it is trivial to select the optimal move at the parent: the Black (respectively, White) player simply chooses the move with the highest (respectively, lowest) action-value. Assuming that the tree is finite, the optimal value of each node can be computed by working backwards from the leaves, using a recursive procedure known as minimax search.

While minimax search leads to optimal actions, it is utterly intractable for most interesting games; the computation is proportional to the size of the game tree, which grows exponentially with its depth. A more practical alternative is to consider a subtree of the game tree with limited depth. In this case, computation begins at the leaves of the subtree. The (unknown) true optimal values at the leaf nodes are replaced with values returned by a heuristic evaluation function. If the evaluation function is sufficiently "high quality", the action computed is expected to be near-optimal.

The computation can be sped up by various techniques, the most well-known being α -β pruning, which is often used together with iterative deepening.

The evaluation function is typically provided by human experts, or it can be tuned using either supervised learning based on a database of games, or using reinforcement learning and self-play [START_REF] Schaeffer | The games computers (and people) play[END_REF]. Programs based on variants of minimax search with α -β pruning have outperformed human world champions in chess, checkers, and othello [START_REF] Schaeffer | The games computers (and people) play[END_REF].

Monte-Carlo Simulation

In some games of interest, e.g., in the game of Go, it has proven hard to encode or learn an evaluation function of sufficient quality to achieve good performance in a minimax search. Instead of constructing an evaluation function, an alternative idea is to first construct a policy (sometimes called a playout policy), and then to use that policy to estimate the values of states. A policy is a mapping from states to actions, in other words a policy determines a way to play the game. Given a policy pair (one policy for each player, which if symmetric can be represented by a single policy), a value estimate for a state s can be obtained by simulation: start in state s and follow the respective policies in an alternating manner from s until the end of the game, and use the reward in the terminal state as the value of state s. In some games, it is easier to estimate the value indirectly by simulation, i.e., it may be easier to come up with a simple policy that leads to good value estimates via simulation, than to estimate those values directly.

A major problem with the approach described so far is that it can be very sensitive to the choice of policy. For example, a good policy may choose an optimal action in 90% of states, but a suboptimal action in the remaining 10% of states. Because the policy is fixed, the value estimates will suffer from systematic errors, as simulation will always produce a single, fixed sequence of actions from a given state. These errors may often have disastrous consequences, leading to poor evaluations and an exploitable strategy.

Monte-Carlo methods address this problem by adding explicit randomization to the policy and using the expected reward of that policy as the value estimate. The potential benefit of randomization is twofold: it can reduce the influence of systematic errors and it also allows one to make a distinction between states where it is "easy to win" (i.e., from where most reasonable policy pairs lead to a high reward terminal state) and states where it is "hard to win". This distinction pays off because real-world opponents are also imperfect, and therefore it is worthwhile to bias the game towards states with many available winning strategies. Note that the concepts of "easy" and "hard" do not make sense against a perfect opponent.

When the policy is randomized, computing the exact expected value of a state under the policy can be as hard as (or even harder than) computing its optimal value. Luckily, Monte-Carlo methods can give a good approximation to the expected value of a state. The idea is simply to run a number of simulations by sampling the actions according to the randomized policy. The rewards from these simulations are then averaged to give the Monte-Carlo value estimate of the initial state.

In detail, the value of action a in position s0 (the root of the game tree) is estimated as follows. Run N simulations from state s0 until the end of the game, using a fixed ran- domized policy for both players. Let N (a) be the number of these simulations in which a is the first action taken in state s0. Let W (a) be the total reward collected by Black in these games. Then, the value of action a is estimated by

0/1 6/7 2/3 3/4 0/1 1/1 2/2 0/1 2/2 1/1 1/1 0 1 1 1 1 1 1 1 1 1 0 0 9/12
W (a)
N (a) . The use of Monte-Carlo methods in games dates back to [START_REF] Widrow | Punish/reward: Learning with a critic in adaptive threshold systems[END_REF] [START_REF] Widrow | Punish/reward: Learning with a critic in adaptive threshold systems[END_REF], who applied Monte-Carlo simulation to blackjack. The use of Monte-Carlo methods in imperfect information and stochastic games is quite natural. However, the idea of artificially injecting noise into perfect information, deterministic games is less natural; this idea was first considered by [START_REF] Abramson | Expected-outcome: a general model of static evaluation[END_REF] [START_REF] Abramson | Expected-outcome: a general model of static evaluation[END_REF]. Applications of Monte-Carlo methods to the game of Go are discussed by Bouzy and Helmstetter [START_REF] Bouzy | Monte-Carlo Go developments[END_REF].

Monte-Carlo Tree Search

Monte-Carlo tree search (MCTS) combines Monte-Carlo simulation with game tree search. It proceeds by selectively growing a game tree. As in minimax search, each node in the tree corresponds to a single state of the game. However, unlike minimax search, the values of nodes (including both leaf nodes and interior nodes) are now estimated by Monte-Carlo simulation.

In the previous discussion of Monte-Carlo simulation, we assumed that a single, fixed policy was used during simulation. One of the key ideas of MCTS is to gradually adapt and improve this simulation policy. As more simulations are run, the game tree grows larger and the Monte-Carlo values at the nodes become more accurate, providing a great deal of useful information that can be used to bias the policy towards selecting actions which lead to child nodes with high values. On average, this bias improves the policy, resulting in simulations that are closer to optimal. The stronger the bias, the more selective the game tree will be, resulting in a strongly asymmetric tree that expands the highest value nodes most deeply. Nevertheless, the game tree will only typically contain a small subtree of the overall game. At some point, the simulation will reach a state that is not represented in the tree. At this point, the algorithm reverts to a single, fixed policy, which is followed by both players until a terminal state is reached, just like Monte-Carlo simulation. This part of the simulation is known as a roll-out.

More specifically, MCTS can be described by four phases.

Until a stopping criterion is met (usually a limit on available computation time), MCTS repeats four phases: descent, roll-out, update, and growth. During the descent phase, initiated at the current state s0, MCTS iteratively selects the highest scoring child node (action) of the current state. The score may simply be the value of the child node, or may incorporate an exploration bonus (see next section). At the end of the descent phase, i.e., upon reaching a leaf node of the current tree, the roll-out phase begins, where just like in Monte-Carlo simulation, a fixed, stochastic policy is used to select legal moves for both players until the game terminates. At the end of the roll-out, the final position is scored to determine the reward of Black. In the update phase, the statistics (number of visits and number of wins) attached to each node visited during descent are updated according to the result of the game. In the growth phase, the first state visited in the roll-out is added to the tree, and its statistics are initialised.

Upper Confidence Bounds on Trees (UCT)

An extremely desirable property of any game-tree search algorithm is consistency, i.e., given enough time, the search algorithm will find the optimal values for all nodes of the tree, and can therefore select the optimal action at the root state. The UCT algorithm is a consistent version of Monte-Carlo tree search.

If all leaf value estimates were truly the optimal values, one could achieve consistency at the parent nodes by applying greedy action selection, which simply chooses the action with the highest value in each node. If all descendants of a given node have optimal value estimates, then greedy action selection produces optimal play from that node onwards, and therefore simulation will produce an optimal value estimate for that node. By induction, the value estimate for all nodes will eventually become optimal, and ultimately this procedure will select an optimal action at the root.

However, the value estimates are not usually optimal for two reasons: (i) the policy is stochastic, so there is some inherent randomness in the values, and (ii) the policy is imperfect. Thus, going with the action that has the highest value estimate can lead to suboptimal play, e.g., if the value of the optimal action was initially underestimated. Therefore, occasionally at least, one must choose actions that look suboptimal according to the current value estimates.

The problem of when and how to select optimal or suboptimal actions has been extensively studied in the simplest of all stochastic action selection problems. These problems are known as multi-armed bandit problems. 1 Each game ends after the very first action, with the player receiving a stochastic reward that depends only on the selected action. The challenge is to maximise the player's total expected reward, i.e., quickly find the action with the highest expected reward, without losing too much reward along the way. One simple, yet effective, strategy is to always select the action whose value estimate is the largest, with an optimistic adjustment that takes account of the uncertainty of the value estimate. This way, each action either results in an optimal action or in a reduction of the uncertainty associated with the value estimate of the chosen action. Thus, suboptimal actions cannot be chosen indefinitely.

The principle of always choosing the action with the highest optimistic value estimate is known as the "principle of optimism in the face of uncertainty" and was first proposed and studied by Lai and Robbins [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF]. A simple implementation of this idea, due to Auer et al. [START_REF] Auer | Finite time analysis of the multiarmed bandit problem[END_REF], is to compute an upper confidence bound (UCB) for each value estimate, using Hoeffding's tail inequality.

Applying this idea in an MCTS algorithm gives the Upper Confidence Bounds on Trees (UCT) algorithm due to Kocsis and Szepesvári [START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF], where Black's UCB score Z(s, a) of an action a in state s is obtained by

Z(s, a) = W (s, a) N (s, a) + B(s, a), B(s, a) = C log N (s) N (s, a) ,
where C > 0 is a tuning constant, N (s, a) is the number of simulations in which move a was selected from state s, W (s, a) is the total reward collected at terminal states during these simulations, N (s) = a N (s, a) is the number of simulations from state s, and B(s, a) is the exploration bonus. Each move is scored by optimistically biasing the sample mean, by adding an exploration bonus. 2 This bonus is largest for the actions that have been tried the least number of times, and are therefore the most uncertain. This encourages rarely explored moves to be tried more frequently.

Unlike many other MCTS methods, the UCT strategy is consistent provided that C is large enough [START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF]. Given enough simulations, the tree grows large enough that first the values of nodes close to the leaf nodes converge to the optimal values, eventually resulting in the convergence of all the values (with probability one). The convergence of the values will also result in the algorithm converging to the selection of an optimal action at the root node (also, with probability one). However, it may take a very long time for the values to converge. Furthermore, the UCT algorithm does not properly take into account the drift of the action-values, which can happen as the policy below a node changes. This can cause unnecessarily slow convergence, as pointed out by Coquelin and Munos [START_REF] Coquelin | Bandit algorithms for tree search[END_REF], who also proposed a correction to the basic UCT formula. Similar corrections have been proposed and analyzed by Bubeck et al. [START_REF] Bubeck | Online optimization in X-armed bandits[END_REF] in a single-agent setting, who shown theoretically that the corrected formula gives rise to near-optimal behavior if the reward function is sufficiently "smooth" in the "topology underlying the search tree". This analysis suggests that the UCT strategy will be most successful when the leaves of large subtrees share similar rewards. Intuitively, Monte-Carlo search methods work best when the estimated values from shallow searches are similar to the estimated values from deeper searches, in other words the mean reward of simulations is somewhat indicative of the optimal value, at all stages of the search.

Despite the shortcomings of UCT, the algorithm remains interesting due to its simplicity of implementation, extensibility and its empirical success in many domains (see Section 5).

b 3 b 1 b 2 a 1 a 3 a 1 b 1 a 1 a 1 a 1 a 1 a 1 a 1
Figure 5: Applying the RAVE algorithm to the search tree from Figure 4 to compute the root value of Black action a1. Using MCTS (Figure 4) there was only one simulation in which Black a1 was played immediately, giving a value of 0/1. Using RAVE, there are 9 simulations in which Black a1 was played at any time, giving a value of 7/9. The MC-RAVE algorithm simply combines these two values.

EXTENSIONS TO MCTS

In this section, we focus on several extensions to the basic MCTS algorithm, originally introduced in the Go program MoGo [23, ?], which have helped recent computer Go programs achieve human-master-level performance. The extensions help to focus the search more deeply, resist overexploration, and speed up the search by sharing the acquired knowledge (value estimates) between related moves.

Rapid Action-Value Estimation (RAVE)

The basic MCTS algorithm estimates the value of each state s and action a in the search tree separately, meaning that many separate simulations are required for each different state and action. However, in incremental games such as Go, the value of a move is often unaffected by moves played elsewhere on the board; in other words, the value of an action might not critically depend on the state in which it was played. Based on this observation, the all-moves-asfirst (AMAF) heuristic [START_REF] Brügmann | Monte-Carlo Go[END_REF] evaluates moves as follows. For each move a (where black moves and white moves are distinct), let Ñ (a) denote the number of simulations in which move a was played at any time, and let W (a) denote the total reward collected by Black in these simulations. Then, the AMAF value of a is simply W (a) Ñ (a) . The Rapid Action Value Estimate (RAVE) generalizes the AMAF idea to search trees. The basic idea of RAVE is to share action values among subtrees. For any state s, we can consider the subtree of nodes that is rooted at the node associated with s. The assumption made by RAVE is that the value of taking action a will be similar within all nodes of this subtree. Thus, the value of a is estimated from all simulations passing through s and subsequently involving a.

The assumption underlying RAVE gives rise to more data for each action (compared to MCTS), but that data might be misleading. There are many situations, for example during tactical battles, in which nearby changes can completely change the value of a move: sometimes rendering it redundant; sometimes making it even more vital. The MC-RAVE algorithm overcomes this issue by interpolating between the unbiased Monte-Carlo value estimates and the AMAF value estimate, so that the AMAF value receives increasingly less weight over time. In particular, the score of action a in state s is estimated by

Z(s, a) = (1 -β(s, a)) W (s, a) N (s, a) + β(s, a) W (s, a) Ñ (s, a) , (1)
where Ñ (s, a) is the AMAF visit count, W (s, a) is the corresponding total reward and β(s, a) is a weighting parameter that decays from 1 to 0 as the visit count N (s, a) increases. Details of the precise weighting schedule used in MoGo are described in [?].

Virtual Experience

Sometimes, prior action-value estimates are available, such as a heuristic function or learned value function. Even if these estimates are not high-quality, it can still be beneficial to use such knowledge to bias the search towards states and actions that are believed to have high value, at least initially. If the action-value estimates cannot be completely trusted, to keep consistency, the effect of the initial estimates should diminish over time. One way of achieving this aim in UCT is to use virtual-experience based initialization, as follows. For a node newly added to the tree, before using the update formula, for all actions a at node s, initialise the number of wins W (s, a) and the number of simulations N (s, a) with a pair of values W * (s, a), N * (s, a) whose ratio H(s, a) = W * (s, a)/N * (s, a) gives the desired prior value. Here, N * (s, a) can be viewed as a virtual count specifying one's initial confidence in the prior estimate in terms of the equivalent number of simulations. Thus, the prior knowledge is specified as a form of virtual experience, analogous to using a beta prior in a Bayesian formulation, a specific case of Bayesian smoothing. A similar approach can be used to initialise new nodes in the MC-RAVE algorithm. In MoGo, the prior value H(s, a) was originally learned using reinforcement learning and self-play, and N * (s, a) (and Ñ * (s, a) in the case of MC-RAVE) was simply set to a constant value [?].

The best recent results in MoGo were achieved by combining supervised learning with handcrafted prior knowledge. MoGo uses supervised estimates H(s, a) constructed from a database of expert plays via the help of association rule learning, a machine-learning algorithm that is often used to discover patterns or rules [START_REF] Bouzy | Bayesian generation and integration of k-nearest-neighbor patterns for 19x19 go[END_REF]. The basic idea is to estimate the prior value H(s, a) by the likelihood of an expert playing action a in the given state s. Due to the enormous number of states, the same state is not likely to be seen twice (except for special states, like states at the beginning of the game). Hence, one is forced to construct an estimate by making use of states similar, but not identical, to s. For this purpose, one can consider patterns p that match s when they are centered at the position where a would be played. For each such pattern, one can count how many times p is observed in a database of games. One can also count how many times the experts actually played at the pattern center amongst these occurrences. The ratio of these two counts gives an estimate, which we denote by H(s, a; p). It remains to specify the patterns used in the definition of H(s, a). A pattern p that is very specific (i.e., large) should give the least biased estimate. However, large patterns might be too rare to give reliable estimates. Thus, given s and a, it makes sense to find the largest pattern p * = p * (s, a) among those patterns that match s and a and which, relative to their size, generate sufficiently many matches in the database.Then, one can use H(s, a) = H(s, a; p * ). The likelihood estimate H(s, a) can then used as a prior estimate of the action-values. Alternatively, it can be combined directly with the score [START_REF]Special issue on Monte Carlo techniques and computer Go[END_REF].

Parallelism

Classical game-tree-search algorithms, such as minimax search with α -β pruning, are notoriously difficult to parallelize effectively. Fortunately, MCTS lends itself much more easily to parallelization; for example, MoGo was parallelized onto 800 cores of the Dutch Huygens supercomputer. On a shared memory, multi-core machine, each simulation can be executed by a different thread, and the estimated values of the nodes shared between all threads [START_REF] Gelly | Modification of UCT with patterns in Monte-Carlo Go[END_REF]. The implementation on message-passing machines is more difficult, because the separate game trees must be synchronised. A typical implementation averages the statistics across the corresponding nodes of the separate game trees, for some subset of nodes close to the root [START_REF] Bourki | Scalability and Parallelization of Monte-Carlo Tree Search[END_REF].

Although MCTS can benefit from parallel implementation, this benefit is not always as large as might be hoped. The performance of parallel MCTS, for a given number of simulations, is typically worse than running serial MCTS for an equivalent number of simulations. The underlying reason is that serial MCTS is able to grow the game tree selectively, based on the results of previous simulations; whereas parallel MCTS must blindly run multiple simulations, without taking account of the results of simultaneous simulations. In the limit of parallelisation, no game tree is constructed, and MCTS behaves just like naive Monte-Carlo simulation.

Roll-Outs

The performance of MCTS is highly dependent on the stochastic policy used during the roll-out phase. A carefully selected roll-out policy can significantly boost performance over a uniform random roll-out policy. Intuitively, the rollout policy should be made as strong as possible. However, if the roll-out policy becomes too deterministic, then the algorithm becomes sensitive to the errors that the roll-out policy makes (see Section 3.2). Therefore, improving the strength of the roll-out policy may in fact result in a reduction in the performance of the overall search. Furthermore, a more complex roll-out policy may execute more slowly, and may therefore degrade the overall performance of MCTS, even if it performs better on a per-simulation basis.

So far, three approaches have been taken to address this issue. The first approach, used in MoGo, is to hand-design a roll-out policy, which randomly selects its moves among a small subset recommended by expert patterns [START_REF] Gelly | Modification of UCT with patterns in Monte-Carlo Go[END_REF]. The second approach is similar, but uses supervised learning to weight the patterns, so as to match the distribution with which human experts select those patterns [?].

The third approach, known as simulation balancing, attempts to find a stochastic policy such that the policy's value function is close (in mean-squared error) to the optimal value function. (The value function of a stochastic policy at a state s is the expected reward of Black if the simulation starts from s and the policy is used all the way until the end of the game by both players.) This objective can be contrasted to the typical supervised learning procedure: minimizing the expected squared error between the policy's reward and the corresponding optimal values. The key difference is that this supervised learning objective penalizes the variance of the rewards, whereas simulation balancing does not. Penalizing the variance reduces the randomness of the policies, which, as argued previously in Section 3.2, may decrease the performance of Monte-Carlo simulation. In practice, since the optimal values are not known, they are approximated by deep search. Simulation balancing has been shown to outperform the supervised learning approach [?].

Discussion

Prior value estimates may often be inaccurate, for example due to lack of data or pattern biases in the supervised learning procedure. In addition, the AMAF value estimate used by MC-RAVE can often be misleading. In these cases, heuristic MC-RAVE will prioritize the wrong moves, and the best moves can effectively be pruned and not tried again for many simulations. There are no guarantees that these algorithms will help performance, but empirically, in the game of Go, these extensions help much more than they hurt. On average over many positions, they provide a very significant performance advantage.

The performance of MCTS is greatly improved by carefully balancing exploration with exploitation, for example by using the UCT algorithm. Perhaps surprisingly, this result does not appear to extend to MC-RAVE in the case of Go: the optimal exploration rate in MoGo was C = 0, i.e., greedy action selection with no explicit exploration. One possible explanation is the following. When using MC-RAVE, even if an action a is not selected immediately from position s, it will often be played at some later point in the simulation, meaning that the value estimates for all actions are continually updated, regardless of the initial move selection and so the basic premise of the classical multi-armed bandit setting, namely that actions do not provide information about each other, fails to hold. Also, for small numbers of simulations, it is most important to reduce the variance of the value estimate. The MC-RAVE algorithm quickly approximates the value of all actions, and therefore selecting a suboptimal action for exploration purposes may lose performance (because that simulation could have been spent on a more valuable part of the search tree) without gaining much additional information. For large numbers of simulations, it becomes more important to reduce the bias of the value estimate, which requires trying each action directly, and therefore requires some amount of explicit exploration. Asymptotically, the AMAF value estimates are ignored, β(s, a) → 0, and consistency can only be achieved by exploring suboptimal actions. However, due to the exponential growth of the search trees, the vast majority of states and actions are visited only a few times, and therefore the asymptotic behaviour hardly kicks in and it will be hard to observe any improvement for explicit exploration methods over the greedy C = 0 approach. This is especially true in Go, because the bias of the AMAF heuristic is believed to be low, and therefore the AMAF value estimates are rarely ignored in practice.

PERFORMANCE OF MCTS

We begin by discussing the performance of MCTS pro-grams in 9 × 9 Go. In 2007, MoGo won the first game against a professional player, Guo Juan (5 dan professional), in a blitz game (10 minutes per side). This feat was repeated in 2008, with longer time controls, against Catalin Taranu (5 dan professional). In 2009, Fuego became the first program to beat a top professional player, Zhou Junxun (9 dan professional). The complete game is shown in Figure 1.

We now turn to the performance of MCTS programs in the full size game of 19×19 Go. Before the advent of Monte-Carlo programs, the strongest classical Go programs, such as The Many Faces of Go, were ranked at 6 kyu on the Kiseido Go server (KGS). 3 At the time of writing, the highest ranked MCTS program on KGS, Zen, is 4 dan amateur on KGS, placing it within the top 5% of approximately 30,000 ranked human players on KGS. Figure 6 illustrates the rapid improvement of MCTS programs over recent years.

In 2008, MoGo won the first handicap game in 19 × 19 against a professional player, Kim Myungwan (8 dan professional); however, this was achieved with the maximum handicap of 9 stones. In the same year, Crazy Stone won two games against a professional player, Aoba Kaori (4 dan professional), with 8 and 7 handicap stones, respectively. In 2009, MoGo won a game against a top professional player, Zhou Junxun (9 dan professional), with 7 handicap stones; and a game against a 1 dan professional player with handicap 6. In 2010, Zen defeated Aoba Kaori with 6 handicap stones.

MCTS has been successfully applied to many other games, and is now the state of the art in the challenging games of Amazons, Lines of Action, Hex and Havannah [START_REF]Special issue on Monte Carlo techniques and computer Go[END_REF]. The generality of MCTS is demonstrated by its recent dominance in the general game playing competition [START_REF] Finnsson | Simulation-based approach to general game playing[END_REF]. The authors and their co-workers have applied MCTS successfully in partially observable domains, classical planning, feature selection and active learning (references available from the authors' homepages). In addition, MCTS proved effective in a wide range of applications including scheduling and resource allocation [START_REF] Cazenave | Monte-Carlo bus regulation[END_REF], natural language processing [START_REF] Chevelu | The true score of statistical paraphrase generation[END_REF], or biometrics [START_REF] Tanabe | A study on security evaluation methodology for image-based biometrics authentication systems[END_REF]. 4

CONCLUSION

This paper has presented the key components of Monte-Carlo tree search and several important extensions which led to the current high performance programs in the game of Go. These algorithms have led to a dramatic increase in the performance of computer Go programs, leading to the first programs to compete at human master level. The game of Go epitomizes the challenges faced by many real-world sequential decision-making problems: It has an enormous search space, a large branching factor, delayed consequences of actions, and an evaluation function that is difficult to construct by hand or learn from experience. Monte-Carlo tree search represents a new paradigm for planning in this challenging domain, which may prove to have implications well beyond the two-player games for which it was originally developed.

This work was supported in part by AICML, AITF (formerly iCore and AIF), NSERC and the PASCAL2 Network of Excellence under EC grant no. 216886 and the PASCAL Network of Excellence (IST 2002-506778). O. Teytaud is grateful to National

Figure 1 :

 1 Figure 1:The first victory of a computer program, Fuego (White) against a 9 dan professional Go player, Zhou Junxun (Black), in an even game.

Figure 2 :

 2 Figure 2: Performance ranks in Go, in increasing order of strength from left to right.

Figure 4 :

 4 Figure 4: Estimating values of a minimax game tree by Monte-Carlo tree search.

The name is due to Robbins[START_REF] Robbins | Some aspects of the sequential design of experiments[END_REF], who pictured a gambler who has the option to play any of a number of slot machines (one-armed bandits) with unknown reward distributions and who wishes to maximize his total expected gain.

This equation is given from Black's perspective. If White is to play then the exploration bonus is subtracted instead.

KGS ranks are computed from even games against ranked human opponents.

Further references are available from http://www. ualberta.ca/~szepesva/MCTS/.

Dates at which several strong MCTS programs on KGS achieved a given rank. Classical versions of these programs, before MCTS was introduced, are marked with an asterisk*.

Science Council (Taiwan) for grant NSC97-2221-E-024-011-MY2 and NSC 99-2923-E-024-003-MY3 and to European Program FP7 through the Mash project.


Dominique Guégan
email: dguegan@univ-paris1.fr.

Dr Bertrand K Hassani
email: bertrand.hassani@malix.univ-paris1.fr.

Operational risk: A Basel II++ step before Basel III

Keywords:

Following the Banking Committee on Banking Supervision, operational risk quantification is based on the Basel matrix which enables sorting incidents. In this paper we analyze these incidents in depth and propose strategies for carrying out the supervisory guidelines proposed by the regulators. The objectives are as follows:

• On the first hand, banks need to provide a univariate capital charge for each cell of the Basel matrix. That requires constructing Loss Distribution Functions (LDFs), which implies estimating a frequency and a severity distribution. We show that the choice of the theoretical distributions to build the LDFs has a tremendous impact on the capital charges, especially if we do not take into account extreme losses.

• On the other hand, banks also need to provide a global capital charge corresponding to the whole matrix. We highlight that a lack of consideration or a poor appreciation of the dependence structure may lead to incorrect capital charges.

• Finally, we draw the attention of regulators and managers to two crucial points:

1. The necessity of splitting information sets in two parts while adjusting the severity distribution. The first covering small and medium losses, and the latter containing extreme losses (this point implies problems of granularity mentioned in the last Basel II guidelines), 2. The choice of the risk measure which provides the capital amount. We emphasize that the expected shortfall measure enables a better anticipation of large incidents pertaining to operational risks.

Introduction

In 2001, the Basel Committee on Banking Supervision provided a set of principles [START_REF] Bcbs | Working paper on the regulatory treatment of operational risk[END_REF] for the effective management and supervision of operational risks, designed for banks and domestic authorities. According to these principles, banks could either use a basic, standard or advanced approach to calculate their capital charges. The last approach known as advanced measurement approach (AMA) requires banks to develop internal models.

However, at that time, operational risks management was a very young topic and due to its absence in the Basel I accords [START_REF] Bcbs | Basel committee: International convergence of capital measurement and capital standards[END_REF], the level of maturity was not the same as for credit risk.

Therefore, Basel II initial requirements were very brief. They bound banks and financial institutions to use internal and external data, scenarios and qualitative criteria. They required banks to compute capital charges on a yearly basis and at a "99.9% confidence level". Therefore, at this time domestic authorities had no real experience of what would be a good approach to model the operational risks.

It was only after banks initial attempt to comply with the regulatory requirements that the BCBS started to be more precise on the kind of models they where expecting ( [START_REF] Bcbs | International convergence of capital measurement and capital standards[END_REF][START_REF] Bcbs | Observed range of practice in key elements of advanced measurement approach (ama)[END_REF][START_REF] Bcbs | Basel iii: A global regulatory framework for more resilient banks and banking systems[END_REF]). New proposals have been done, they correspond to what we could refer to as Basel II++ principles which have to be monitored by the banks for the next few years. The purpose of this article is to analyse the effects of these Basel II principles, to discuss the strategy before the deployment of the next Basel system and to anticipate the applications of these new principles with respect to the data on which these principles have been applied. The results presented in this paper have been obtained using Caisse d'Epargne data sets (2006)(2007)(2008)(2009)(2010), except the results presented in Table 2, which have been obtained on a Banques Populaires data set (2008-2010) 1 .

Initial principles in Basel II proposals

In the second part of the 80's when the regulators decided to establish rules to strengthen the banking system there was nothing concerning operational risks. It was only in 2001 that supervisors and the banking industry recognized the importance of operational risk in shaping the risk profile of financial institutions. Thus, the Basel Committee on Banking Supervision in their first Pillar about minimum regulatory capital charge for risks, required banks to take into account operational risks. As a result the Risk Management Group of the Basel Committee introduced a new regulatory capital approach based on banks' internal risk estimates called the "Advanced Measurement Approach" (AMA). The principle of this regulatory capital charge for operational risks was based on the following definition of operational risk: "the risk of loss resulting from inadequate or failed internal processes, people and systems or from external events". This definition includes legal risks, but not the strategic, reputational or systemic risks. At the time, the biggest challenge in applying the recommended guidelines stood in collecting and analysing loss data sets, because this assumed efficient risk management devices and materials.

Collection system have been deployed in the past ten years. In this paper we will further discuss data collection (in particular the granularity issue) and organisation as part of calculating the minimum regulatory capital charge required from banks and insurance companies, in particular the problem of granularity.

The first Pillar proposal was established in close collaboration with the banking industry. It categorised operational risk exposures and losses into a series of standardised business lines and events types. Table 1 provides an example of the matrix on which the supervisor worked to provide the notorious capital requirement. This matrix was likely responsible for errors in the calculation of the capital requirement due to the excessive aggregation of the data collected. This was reflected in the guidelines for future Basel accords, and we will show in this paper the impact of the level of granularity of matrix and the importance of taking heed of this point.

We mentioned earlier data collection specific to AMA to evaluate capital charges, which lead to inquest another problem concerning the regulatory capital. The Committees's preliminary assessments of the possible level of operational risk regulatory capital was 20% of the current regulatory capital (CRM). Practitioners thought that a 20% figure should be lowered, and that 12% of minimum regulatory capital would provide a more reasonable cushion and produce required capital amounts more in line with the operational risks faced by large, complex banking organisations. However, it seems in reality that these first assesments (20% to 12%) were calibrated at a too low level. The first evaluation of operational risk capital requirements was used to define the Basic approach, and induced the weights of the standard approach. Since the banks' incentive to adopt the AMA was a 25% capital allocation reduction compared to the standard approach disregarding their risk profile, it produced a modelling bias. It could be argued that the capital reduction was driven by better risks management within the banks, which is not entirely false, nevertheless the inital lack of experience led to too low forfaitary capital charges which were used as a benchmark for the AMA. Besides, and we would like to emphasize this point, loss data sets (internal or external) are not used in the basic and the standard approach to compute capital requirements. The regulatory capital in those cases is evaluated as a fraction of the net banking income. Therefore, we cannot compare these approaches with the AMA. We

show with empirical studies the difficulty to assess a correct level of charges. Therefore, after suggesting higher risk levels for the basic and the standard approach, we provide conservative and accurate solutions to model operational risks. The choice of methodologies is crucial and we detail those evidences at different steps of the calibration process.

The basic tools: LDA and VaR

A traditional way to deal with operational risks is the Loss Distribution Approach (LDA) [START_REF] Frachot | Loss distribution approach for operational risk[END_REF].

This aims at building a Loss Distribution Function (LDF) ( [START_REF] Guégan | A modified panjer algorithm for operational risk capital computation[END_REF] for instance) G which is the mixture of a frequency distribution p(k) and a severity distribution F (x) (whose density is given by f ), thus

G = ∞ γ=1 p(k)F * γ (x), x > 0, G b,e = 0, x = 0, (1.1)
where * denotes the convolution operator and F * γ the γ-fold convolution of F with itself. We denote g the density of G, and

g = ∞ k=γ p(k)f * γ (x), x > 0. (1.2)
Experts working on operational risks agree on the fact that the frequency distribution has a negligible impact on the LDF's quantile which provides in fine the regulatory capital. However, the choice of the severity distribution has a tremendous impact on this because it is the most pertinent information in terms of level of loss. The capital charge pertaining to G is obtained, at the request of the regulators, through a 99.9% Value-at-Risk (VaR) -a quantile computed from this LDF. We recall now the definition of the VaR measure, Definition 1.1. Given a confidence level α ∈ [0, 1], the VaR associated to a random variable X is given by the smallest number x such that the probability that X exceeds x is not larger than

(1 -α) V aR (1-α)% = inf(x ∈ R : P (X > x) ≤ (1 -α)). (1.3)
Here, the random variable X is associated to a cell of the Basel matrix (Table 1). To compute P (X > x) we need to determine the LDF associated with this random variable, thus the choice of the severity distribution which constitutes this LDF will have a tremendous impact on the final capital allocation. The table presents very poor goodness-of-fit tests results. In this case it is not possible to state which distribution is better than the others. The fifth column presents the capital charges we would have using these distributions, and the sixth the Expected Shortfall. These results are compared to 95% confidence level risk measures.

For instance to model the severities of a sample representing the External Fraud event on the Retail Banking business line, we have fitted by maximum likelihood estimation and tested the following distributions (for which we provide the densities in appendix B): the lognormal distribution, the Weibull distribution, the Gumbel distribution, the Generalized Pareto distribution (GPD) [START_REF] Pickands | Statistical inference using extreme order statistics[END_REF][START_REF] Embrechts | Modelling Extremal Events: for Insurance and Finance[END_REF], the GB2 distribution ( [START_REF] Gupta | Handbook of Beta Distribution and Its Applications[END_REF], [START_REF] Rigby | Generalized additive models for location, scale and shape,(with discussion)[END_REF]), and the g-and-h distribution ( [START_REF] Hoaglin | Summarizing shape numerically: the g-and-h distributions[END_REF], [START_REF] Buch-Kroman | Comparison of tail performance of the champernowne transformed kernel density estimator, the generalized pareto distribution and the g-and-h distribution[END_REF]). For the choosen sample, we provide, for each distribution the corresponding capital requirement computed using the 95% and 99.9% Value-at-Risk (VaR) introduced in (1.3). The second column of Table 2 provides the result of an adequacy test based on the Kolmogorov-Smirnov distance to check the quality of the fit of these statistical distributions to the data sets. They all failed, thus statistically we cannot accept any of these distributions. Nevertheless if we continue the exercise 2 columms 3 and 5 contain the capital computed using the VaR for two values of α.

Colums 4 and 6 exhibit the capital requirements that the banks need if we use another measure named Expected Shortfall given by (3.1). Looking at these four columns we observe that the choice of the distribution has a tremendous impact on the capital allocation. Thus at this point, there is a trade-off between the choice of a distribution that minimises the capital allocation (here the Gumbel one), or a distribution which provides a more conservative capital (here the GB2). We also observe large differences with respect to the choice of the so-called risk measure.

Thus, besides the calibration problem, the choice of risk measure is crucial. We will now expand these points more in details.

In the first part of section 2, we will discuss estimation of the LDF for each cell of the matrix, and provide the corresponding regulatory capital with respect to the corresponding LDF and the chosen risk measure. In section 3 we introduce a dependence structure between the cells, and for the different risk measures we will produce several capital charges. Finally the last section concludes with some important remarks focusing on the impact of the distribution families, the parameter estimation procedures and the risk measures on the regulatory capital. To complete our analysis, Appendixes provide statistics of the data sets used (Appendix A), exact densities of the distribution considered in this paper (Appendix B) and a comparison of estimation methods for the GPD parameters (Appendix C).

Estimation of the severities in each cell: the importance of the tail distribution

Before providing a capital associated with the global matrix, we need to analyse the behavior of each cell. We need to know the correct distribution that characterizes each cell. It is now recognised that for a proper statistical adjustment of the severity distribution, we must take into account the existence of extreme values in the analysis of the loss data sets (Table 2). There are 2 To continue this exercise is not unrealistic as soon as severity distributions like the lognormal distribution is commonly used in banks to compute the LDF several approaches to consider which are all part of the extreme value theory [START_REF] Leadbetter | Extremal theory for stochastic processes[END_REF]. Following this theory in a recent paper, we have proposed a flexible approach [START_REF] Guégan | A efficient peak-over-threshold implementation for operational risk capital computation[END_REF] to model the severity distributions. Our approach is a mixture of two distributions: one characterizing the most important losses (the tail) using the Generalized Pareto Distribution (GPD), and the latter modelling the remaining data (the central part of the distribution or corpus). We used a GPD on the right tail for which we provided innovative theoretical and practical solutions, and fit a lognormal3 distribution on the remaining data via an EM algorithm. Figure 1 illustrates the approach. Then, to build the final LDF, we applied an adapted Monte Carlo algorithm. Once the threshold of the GPD has been found, the method chosen to estimate GPD's parameters tremendously impacts the VaR: it seems that the influence of the estimation procedure on the computation of the capital allocation has never been discussed before and we provide some details in Appendix C.

The estimation procedure for the GPD we selected in this paper is based on the maximization of the Anderson-Darling statistic [START_REF] Luceno | Fitting the generalized pareto distribution to data using maximum goodness-offit estimators[END_REF].

Thus, we define the severity distribution as a mixture of a lognormal distribution on the corpus, and a GPD on the right tail (cauda,) whose density f (x; u, β, ξ) is :

f (x; u, β, ξ, µ, σ) =      f (corpus) (x; µ, σ), if x < u f (cauda) = 1 1- u 0 f (center) (x;µ,σ)dx × f GP D (x; u, β, ξ)), if x ≥ u , ( 2.1)
where, µ and σ are the lognormal distribution parameters, and f GP D the density of the GPD given in Appendix B.

In Table 3, we provide the capital requirements computed using different distributions for the cell associated with the business line "Payment & Settlement" and the event type "Delivery, Execution and Process Management" for the year 2006. We observed that by using the lognormal distribution only provides a very less conservative regulatory capital than using the POT method we introduced above. Note that when we adjusted only a GPD on the data set, we did not obtain workable results because either the parameters could not be properly estimated, or we faced an infinite mean model (ξ > 1). for the year 2006, comparing different hypothesis for the severity distribution. We cannot provide a GPD estimation on the whole data set as the shape parameter is superior to 1, and therefore we face an infinite mean model.

POT method implementation

We also observed large amount differences with respect to the choice of the risk measure: the VaR or the ES. This is discussed in more detail below.

Capital charge associated with a coherent risk measure

The regulator imposed a confidence level of 99.9% for the capital charge, therefore if we use the VaR measure, we have α = 0.1% in (1.3). Nevertheless, using this risk measure, we face several problems, especially while computing a global capital charge. Indeed, the sum of the VaRs may be lower than the VaR of the sum i.e. the VaR is known not to be subadditive, and the result is questionnable as soon as several loss distributions are aggregated. On the other hand, this measure -by definition-does not take into account the large losses. However, the Conditional VAR (CVaR) or Expected Shortfall (ES) is a coherent measure [START_REF] Artzner | Coherent measures of risk[END_REF] and therefore it is more appropriate to work with it. We recall its definition:

Definition 3.1. For a given α in [0, 1], η the V aR (1-α)%
, and X a random variable which represents losses during a prespecified period (such as a day, a week, or some other chosen time period) then,

ES (1-α)% = E(X|X > η) (3.1)
The ES measure which is subadditive takes into account the information contained in the distribution tail contrary to the VaR measure. Therefore, some extremal event exposures are captured by the ES measure. However in practice the ES value may be much higher than the corresponding VaR value, therefore, a lower confidence level could be used when considering the ES measure As illustrated in Table 2, it might be judicious to use a GB2 distribution to model the severity and to compute a 95% ES than to use a lognormal distribution at a 99.9% VaR. Thus, we see that, to take into account very large losses, it could be more appropriate to associate at the same time the use of extreme distributions and the ES measure. In this case the result is closer to reality, and more effective to help banks understanding extremal events and by the way preventing them. In Tables 2 and3, we illustrate these facts. We observed a large difference between the capital computed with the VaR and the ES measures. Thus, a trade-off between a VaR at 99.9% and an ES at 95% should be considered .

In these two tables we have seen the impact of the choice of risk measure on the capital computation. Now this impact can also be illustrated if we study the composition of the matrix and its granularity. Indeed, until now we used collected data organised into the Basel Matrix [START_REF] Bcbs | Working paper on the regulatory treatment of operational risk[END_REF]. The first level of granularity is made up of 56 cases -8 business lines ("b") × 7 event types ("e") 4 .

Nevertheless, each event type might be further broken down into several elements. For example, the "external fraud" event may be shared in two items -"Theft and Fraud" and "Systems Security" (second level of granularity). In a third level, the element "Theft and Fraud" may be split in several components: "Theft/Robbery", "Forgery" and "Check kiting". After a deep analysis, we observe that the kind of losses expected from a fraud with a credit card does not correspond to losses caused by someone hacking the system for instance. Nevertheless these two different kinds of losses are in the same cell. Therefore, considering the largest level of granularity, we could face multimodal empirical distributions. Consequently, the methods used to model the losses depend on the choice of granularity of the Basel matrix. This choice might have a tremendous impact on capital requirement computations. Besides, there is a trade-off between the quantity of data and the robustness of the estimations. Indeed, if the quantity of data is not sufficient, we cannot go to a more granular level; on the other hand the empirical distribution is therefore an aggregate of various types of data and the estimation of this last empirical distribution can be source of unusable results.

For the moment, we cannot empirically illustrate these remarks because we do not have the appropriate information set. Nevertheless it seems reasonable, in order to be close to reality, to introduce the computation of the distributions associated to the second or even third level of data granularity in order not to bias the LDF, as long as this information exists.

Influence of the dependence structure between the cells on the regulatory capital computation

Banks need to have in fine an amount calculated using the global matrix. This means that, as soon as the LDFs have been determined for each cell, the next question is the best way to combine these distributions to provide a global regulatory capital i.e. corresponding to the whole matrix.

Traditionally the experts computed the global capital requirement summing the capital calculated in each cell. This procedure does not take into account the true dependence which exists within the cells. One way to bypass this problem is to use a copula distribution which is a multivariate distribution permitting to link a huge number of distributions. During recent years some experts used the Gaussian copula to take these dependences into account, claiming inability to perform calculations using other copulas in high dimensions. The well-known Gaussian structure is not adapted to loss data sets (indeed, the Gaussian structure is elliptical, and does not capture tail dependence), and since 2005 it is now possible to work with copulas in high dimensions using nested copulas or vines [START_REF] Aas | Pair copula constructions of multiple dependence[END_REF]. Recently, we used this last methodology and adapted it to compute the capital requirement associated with operational risks in high dimensions [START_REF] Guégan | n-dimensional copula contributions to multivariate operational risk capital computations[END_REF].

Extending this work the main improvements for practitioners are the following:

• Firstly, this methodology enables the use of numerous classes of copulas without restricting to the elliptic domain. One can consider copulas which focus on information contained in the tails, where we find the large losses.

• Secondly, this approach allows several combinations of margins (corresponding to the dis- tributions computed for each cell) to derive robust adjustments in the statistical sense.

• Thirdly, even working in the highest dimension, the procedure is easy to implement and is not too time consuming.

• Finally, this method complies with the lastest Basel Committee [START_REF] Bcbs | Basel iii: A global regulatory framework for more resilient banks and banking systems[END_REF] requirements.

Below, the results obtained considering several cells of the Basel matrix 5 are provided. In Table 4 we introduce some notations corresponding to the losses we have studied. ) and (F 3 , F 6 , F 7 , F 10 ) as single data sets. In this case, our aggregation is "Business Line" oriented (Table 1).

BUSINESS

In a first exercise, we show how to compute the amount corresponding to these four cells. The diagram is provided in Figure 2. We begin by estimating the margins associated with the cells B 1 , B 2 , B 3 and B 4 . Thus, in a first step, we link the couples (B 1 , B 2 ), (B 1 , B 4 ) and (B 3 , B 4 ) with a copula whose parameter is estimated by maximum likelihood (and sense checked using the Kendall τ ). In a second step we link the copulas previously obtained by other copulas and so on. The choice of the cells to find the copula results from a sharp analysis of the data sets (cells). Nevertheless, some statistical studies enabling the decision of which links are appropriate can be found in ( [START_REF] Guégan | New prospects on vines[END_REF] and [START_REF] Guégan | n-dimensional copula contributions to multivariate operational risk capital computations[END_REF]).

5 Nevertheless the complete Basel matrix could contain more than 250 cells, and thus more research will be necessary to work with such a large matrix, mainly to limit the time of computation. Recent improvements using parallel computing, seem to provide interesting solutions to achieve this purpose [START_REF] Brechmann | Truncated regular vines in high dimensions with applications to financial data[END_REF]. In Table 5 we provide the amount computed using VaR and ES measures. The results given in the first line correspond to the global amounts obtained summing the VaR provided by the four margins B 1 , ..., B 4 , considering different distributions to model the severities: 1 corresponds to a non parametric estimation procedure, 2 corresponds to the lognormal distribution estimated and 3 corresponds to the Gumbel adjustment. In the second line we provide the results obtained linking the marginal distributions with the Gumbel copula with a parameter θ = 5.34 obtained applying the previous vine methodology presented above; 1, 2 and 3 correspond to the same distributions for the margins as before. Looking at the third column we observe that we do not have the same amount if we sum the four cells (methodology based on a univariate approach) or if we use a copula methodology. The capital charges are very similar, but bigger in the first case.

C 12 (B 1 , B 2 ) C 14 (B 1 , B 4 ) C 34 (B 3 , B 4 ) B 2 B 1 B 4 B 3
As a result, not taking into account the dependencies at all may lead to over conservative capital charges, even more conservative than using an extreme value copula (for instance a Gumbel one). The similar results between the two aggregation methodologies is a coincidence due to the fact that a simple sum of high quantiles (VaR) intuitively implies a strong dependence of large losses and the Gumbel copula we obtained mimics this behaviour. If we compare the third and the fourth column we observe that the capital charges are always bigger using the ES measure:

this confirms comments made previously. When a Gumbel distribution is used on the margins, the two methods are competitive, indeed, the results are nearly similar. The use of lognormal distribution provides more conservative results. The use of nonparametric modelling provides a value between the two previous situations. It seems to us that obtaining a very good fit on the margins is conducive with providing a realistic amount of capital. The modelling of the margins can be more influential than the fit of the copula, nevertheless, using upper tail dependence copula structures allows a more conservative capital charge for banks. the lognormal approach and 3 the Gumbel one.) and two classes of dependence. Univariate corresponds to the VaRs sum of each LDF. The alternative corresponds to an aggregation using a Gumbel copula.

C 1234 (B 1 ,B 2 ,B
We now propose another exercise. In Table 1 we consider the cell F 9 corresponding to Business

Disruption & System Failure events in the Retail Banking business unit and the distribution associated to the cell F 6 characterizing the same events in the Payment & Settlement business unit. For the distribution F 9 we estimate a Gumbel distribution or a lognormal distribution, for the distribution F 6 we estimate a Generalized Pareto distribution (GPD) or a lognormal distribution. Tables 6 and7 provide the capital values when we link these two distributions with a Gumbel copula on one hand and with a Clayton copula on another hand. In columns 4 and 5

we provide the capital computed using the VaR and the ES measures respectively. Columns 2 and 3 gives the amount corresponding to each cell obtained by projection from the fourth column.

The results of these tables show that depending on the way we model the margins, we have tremendous differences between the VaRs. considering three classes of severities (1 denotes the non parametric approach of the LDF, 2 the lognormal approach and 3 the Gumbel one.).

measurement, management and control of operational risks. As we had the opportunity to experiment the methods suggested in literature using real data sets, we found various drawbacks and pitfalls, and we proposed solutions to bypass them.

We suggested the use of a Peak-over-Threshold method to thicken the right tail of the loss distribution function. Presenting this solution, we suggested an efficient way to obtain generalized Pareto distribution parameters which is accurate regarding goodness-of-fit tests, and therefore compliant regarding the regulator. Furthermore, our methods have shown conservative results

and quantitatively supported the idea that some data sets might be badly built.

We provided an innovative solution to compute aggregated risk measures (VaR and ES), dealing with dependences between Basel categories. This solution is based on nested structures and vine architectures. Carrying out this methodology, we were able to take into account specific dependences (upper tail etc.) between many margins with Archimedean and extreme value copulas.

We also studied the sensitivity of multivariate VaRs to modeled LDFs (margins), to dependence architectures and to copulas parameters.

In addition of these results, we observed that estimating dynamically the parameter of the de-pendence structure creates important variations in the values of the Gumbel copula parameter.

We illustrated this fact in Table 9. We computed the parameter of the Gumbel copula linking the LDFs of the cells F 9 and F 6 . This parameter θ varied with respect to the information set used for its estimation. The parameters' value obtained using the year 2006, was different when we used the year 2007 or the year 2008, or the whole sample. We noticed that the upper tail dependence was larger when we used this last data set. This will have an impact on the computation of capital requirements. Thus, with the information set we use, the capital requirement appeared to be more or less conservative, and notion of dynamics inside the data needs to be taken into account. Therefore, we suggest to work dynamically and therefore measure the impact of the time passing on the distribution shapes. This idea led us to challenge the 5 years data sets required by the authorities. Indeed, these data sets may include outdated data -for example, a incident occurred in a department that does not exist anymore -or not old enough and some long memory process should be involved.

Last but not least, we suggested to compute capital charges considering another risk measure than the VaR measure, say the expected shortfall. This measure is coherent and also take into account the whole information contained in the tail. Computing a Capital allocation from a 99.9% ES is not realistic as it appears to be too conservative, but a lower critical threshold could be considered. For example one could consider a 95% ES instead of a 99.9% VaR (

B Appendix: Distributions for the severities

We provide the densities of the main severity distributions we used along this paper.

• lognormal distribution:

f b,e (x; µ, σ) = 1 xσ √ 2π e -(log(x)-µ) 2 2σ 2 , (B.1) for x > 0, µ ∈ R, σ ∈ R + * .
• Weibull distribution: • GB2 distribution ( [START_REF] Gupta | Handbook of Beta Distribution and Its Applications[END_REF], [START_REF] Rigby | Generalized additive models for location, scale and shape,(with discussion)[END_REF]):

f b,e (x; α, β, p, q) = αx αp-1

β αp B(p, q) 1 + x β p+q (B.5)
where α, β, p, q, x >, B(u, v) = Γ(u)Γ(v)Γ(u + v) is the Beta function, and Γ(.) is the Gamma function.

• g-and-h distribution ( [START_REF] Hoaglin | Summarizing shape numerically: the g-and-h distributions[END_REF], [START_REF] Buch-Kroman | Comparison of tail performance of the champernowne transformed kernel density estimator, the generalized pareto distribution and the g-and-h distribution[END_REF]):

f b,e (x; g, h) = exp ((g * x)-1) * exp when g = 0 and h = 0, the g-and-h distribution reduces to a standard normal distribution.

C Appendix: Influence of estimation methods on the amount of regulatory capital

We show the influence of the estimation procedures of GPD's parameters used in section 2 on capital requirements. Assuming a bootstrap method to estimate the threshold ( [START_REF] Hall | Using the bootstrap to estimate mean squared error and select smoothing parameter in nonparametric problems[END_REF], [START_REF] Danielsson | Using a bootstrap method to choose the sample fraction in tail index estimation[END_REF]), we estimate the remaining ξ and β parameters of the GPDs defined in (2.1) using the method introduced by [START_REF] Luceno | Fitting the generalized pareto distribution to data using maximum goodness-offit estimators[END_REF], denoting this method M1. We also consider three other alternative estimation methods to estimate these parameters in order to check their impact on VaR computations.

These ones are respectively the Pickands method (M2) [START_REF] Pickands | Statistical inference using extreme order statistics[END_REF], the Hill method (M3) [START_REF] Hill | A simple general approach to inference about the tail of a distribution[END_REF], and the Maximum Likelihood method (M4). We provide in Table 11 the estimations of GDPs parameters (with their standard deviation in brackets) obtained for both sets, using these four methods and the corresponding capital charges.

Note that a shape parameter ξ > 1 in (

Figure 1 :

 1 Figure 1: Method Illustration: This figure presents the histogram (in grey) of the Historical LDF. The black line corresponds to a LDF mixing a Poisson and a lognormal distribution. The 99.9% quantile represnting the VaR is pointed out by ∆. The dash line represents a LDF mixing a Poisson distribution and a multiple pattern severity (lognormal-GPD). + indicates the location of the VaR. The right graph focuses on the right tail of the LDFs described above. This figure highlights the fact that this method enables thickening up the right tail of the LDF.

11

  Documents de Travail du Centre d'Economie de la Sorbonne -2011.53 (Version révisée) compared to the VaR measure.

13

  Documents de Travail du Centre d'Economie de la Sorbonne -2011.53 (Version révisée)

Figure 2 : 4 -

 24 Figure 2: 4-dimensional vine estimation to obtain the dependence structure for the whole Basel Matrix.

Table 9 :

 9 Parameter estimation of Gumbel copulas estimated on F 9 and F 6 for each year 2006, 2007 and 2008 (second column). These parameters are compared to a Gumbel copula parameter estimated on the entire time series (third column). The corresponding standard deviation are provided in brackets.

•

  x > 0, β > 0, ξ > 0. 23 Documents de Travail du Centre d'Economie de la Sorbonne -2011.53 (Version révisée) Gumbel distribution: f b,e (x; u, β) u ∈ R and β > 0.• Generalized Pareto distribution (GPD) ([START_REF] Pickands | Statistical inference using extreme order statistics[END_REF][START_REF] Embrechts | Modelling Extremal Events: for Insurance and Finance[END_REF]):f b,e (x; u, β, ξ) β > 0 and ξ = 0 (or f b,e (x; u, β, ξ) = 1 β -(x-ξ) β if u = 0).

24

  Documents de Travail du Centre d'Economie de la Sorbonne -2011.53 (Version révisée)

4

  Documents

	(7)Execution, Delivery	& Process Management							F7
	(6) Business Disruption	& System Failures					F9		F6
	(5) Damage to Physical Assets						F5
	(4) Clients, Products	& Business Practices				F1	F2		F3			F4
	(3) Employment Practices &	Workplace Safety
	(2) External Fraud						F8		F10
	(1) Internal Fraud
	BUSINESS LINES	LEVEL 1	(1) Corporate Finance	(including Municipal/Gov.t	Finance & merchant banking)	(2) Trading & Sales	(3) Retail Banking	(4) Commercial Banking	(5) Payment & Settlement	(6) Agency Services & Custody	(7) Asset Management	(8) Retail Brokerage
	BUSINESS	UNITS		INVESTMENT BANKING				BANKING			OTHERS

de Travail du Centre d'Economie de la Sorbonne -2011.53 (Version révisée)

Table 1 :

 1 Basel Matrix for operational risks: each cell represents Business line/event types classification. F

i , i ∈

[START_REF] Aas | Pair copula constructions of multiple dependence[END_REF][START_REF] Danielsson | Using a bootstrap method to choose the sample fraction in tail index estimation[END_REF]

denotes the distribution associated to each cell for which data is available. 5 Documents de Travail du Centre d'Economie de la Sorbonne -2011.53 (Version révisée)

Table 2 :

 2 Several theoretical distributions have been fitted from a data set representing the External Fraud events of the Retail Banking business line of the Banques Populaire perimeter.

	Severity distribution K-S test VaR (95%)	ES (95%)	VaR (99.9%)	ES (99.9%)
	Lognormal	<2.2 e-16 6 448 883	7 531 208	13 354 724	17 863 146
	Weibull	<2.2 e-16 4 081 999	4 204 917	4 530 362	4 631 586
	GPD	<2.2 e-16 33 512 000 192 902 521 1 009 472 708 4 865 819 191
	Gumbel	<2.2 e-16 4 247 871	4 336 857	4 597 061	4 669 047
	GB2	<2.2 e-16 9 321 772	19 497 566	76 326 374	253 422 675
	g-and-h	<2.2 e-16 6 030 146	6 289 353	6 940 614	7 231 981

Table 3 :

 3 We provide risk measures on the data set which represents the severity of the business line "Payment & Settlement" and the event type "Delivery, Execution and Process Management"

	Severity distribution VaR (95%) ES (95%) VaR (99.9%) ES (99.9%)
	Lognormal	305 303	336 455	463 192	533 160
	GPD	∞	∞	∞	∞
	POT	1 388 655 3 070 808	15 627 945	30 166 707

Table 4 :

 4 Restricted Basel Matrix used to compute operational risk global capital allocation. B 1 ,

		BUSINESS LINES	Loss Distributions
	UNITS	LEVEL 1
	INVESTMENT BANKING	(2) Trading & Sales	B 1
	BANKING	(3) Retail Banking	B 2
		(5) Payment & Settlement	B 3
	OTHERS	(8) Retail Brokerage	B 4

B 2 , B 3 , B 4 are the four loss distributions used in the vine methodology. B 2 and B 3 are built considering respectively (F 2 , F 5 , F 8 , F 9

  C 1234 (C 124 , C 134 ) C 124 (C 12 , C 14 ) C 134 (C 14 , C 34 )

14 Documents de Travail du Centre d'Economie de la Sorbonne -2011.53 (Version révisée)

Table 5 :

 5 This table provides the capital allocation (VaR) and the ES for the whole data set, considering three classes of severities (1 denotes the non parametric approach of the LDF, 2

	3 ,B 4 ) Margins	VaR	ES
		1	68 468 561 71 030 541
	Univariate	2	76 817 362 94 196 483
		3	48 113 918 48 244 680
		1	68 517 234 71 028 526
	Gumbel Copula	2	76 564 982 93 187 912
		3	48 112 494 48 241 814

Table 8 :

 8 For example, we would have a VaR equal to 117 207 This table provides the VaRs and ES associated with each LDF of the set LDF 2 , LDF 5 , LDF 8 and LDF 9 when we decompose the dependence structure of the 4-dimensional set C 2589 ,

	Approach	LDF	LDF 2	LDF 5	LDF 8	LDF 9	VaR	ES
		1	19 650 986 3 182 731 14 212 411 2 241 011 39 287 139 40 899 526
	Univariate	2	6 240 984 2 151 627 11 676 534 4 049 831 24 118 976 32 957 873
		3	13 599 313 2 478 087 8 599 313	1 087 410 25 764 123 25 887 436
		1	20 578 056 3 300 471 15 191 828 2 386 106 41 456 461 43 024 128
	Gumbel Copula	2	10 732 933 2 310 337 29 525 155 13 608 000 56 176 425 79 500 929
		3	13 617 419 2 486 453 8 603 916	1 095 587 25 803 375 25 927 487

Table 2 )

 2 as we illustrate in the previous exercises.

20 Documents de Travail du Centre d'Economie de la Sorbonne -2011.53 (Version révisée) A

Appendix: Distributions statistics

  Next table provides the four first moments of the empirical severities corresponding to the cells of the Basel matrix (Table1)used in this paper.

	Distributions	Mean	Variance	Skewness Kurtosis
	F 1	195.37	292732.86	7.31	71.69
	F 2	1522.83 372183311.54	27.57	910.13
	F 3	175.42	3804557.63	30.03	956.75
	F 4	1805.81 93274002.03	18.74	457.58
	F 5	1824.95 189175093.33	17.79	354.00
	F 6	1200.08 438224165.80	23.69	563.48
	F 7	800.14	24268504.39	10.88	139.39
	F 8	1779	1602373386	19.27	435.88
	F 9	1824.95 189175093.3	17.79	354.00
	F 10	12104	519962084.2	108.03	11806.23

Table 10 :

 10 Statistics of the data sets used. The distributions are right skewed and present large kurtosis.

Table 11 :

 11 2.1) induce an infinite mean model which naturally provides very high VaRs. Nevertheless, non-parametric estimator such as Pickands might provide this kind of value and by the way unusable models. We provide risk measures on the data set which represents the severity of the business line "Payment & Settlement" and the event type "Delivery, Execution and Process Management" for the year 2006, given estimations of the GPD's parameters ξ and β (Appendix B) using four methods for û = 179. M1 is the method introduced by Luceno[START_REF] Luceno | Fitting the generalized pareto distribution to data using maximum goodness-offit estimators[END_REF], M2 is the Pickands method, M3 is the Hill method, and M4 is the Maximum Likelihood method. We provide in brackets the standard deviations computed by bootstrapping. The third column gives the 99.9% VaR (regulatory capital allocation) pertaining to these estimates (µ = 3.593098, σ = 1.510882). The fourth column presents the corresponding expected shortfall capital value.

	Method	β	ξ	VaR	ES
	M1	932.854	0.767	15 700 112	34 215 896
		(83.71) (0.101)
	M2	682.615	1.144	538 480 990	∞
		(160.70) (0.266)
	M3	1007	0.66	5 725 341	14 780 214
		(214.36) (0.228)
	M4	904.087	0.827	27 944 558 125 019 034
		(92.31) (0.097)

25 Documents de Travail du Centre d'Economie de la Sorbonne -2011.53 (Version révisée)

The data sets used in this paper were sampled from Bertrand HASSANI's PhD thesis financed by BPCE. 3 Documents de Travail du Centre d'Economie de la Sorbonne -2011.53 (Version révisée)

Documents de Travail du Centre d'Economie de la Sorbonne -2011.53 (Version révisée)

The lognormal assumption was the best on our data sets, but one can fit any other distributions.

The business lines are corporate finance, trading & sales, retail banking, commercial banking, payment and settlement, agency services, asset management and retail brokerage. The event types are internal fraud, external fraud, employment practices & workplace safety, clients, products & business practices, damage to physical assets, business disruption & system failures and execution, delivery & process management.

a VaR equal to 2 037 655 euros if F 9 is modeled with a lognormal distribution and F 6 with a Gumbel one. Depending on the way we model the LDFs, the aggregated VaR may be multiplied by 57.52. The same behavior is observable when we project the corresponding values on the cells. For example, the multivariate VaR projection on F 9 is e 2 655 055 if F 6 is modeled using a lognormal distribution, and is equal to e 15 405 192 if F 6 is modeled using a GPD distribution.

The peak for the VaR observed in that latter case is due to the capture of extreme events through the choice of the margins: the Gumbel one. Finally, using at the same time copula and severity distributions, which take into account information in the tail, provides very accurate results.

Indeed, when we model F 6 using a GPD associated with a Gumbel copula, we provide a larger VaR than with the Clayton one. The differences are observed comparing the amounts e 105 422 356 with e 103 249 260 on the one hand, and e 117 207 402 with e 107 807 238 on the other.

In Table 6 we see that the capital requirements obtained using a Gumbel copula are bigger than those obtained with a Clayton one, thus the choice of the dependence structure also has an impact on the computation of the capital charges. Now, if we use the VaR measure the difference is not significant for a bank (columns 4 in Tables 6 and7), but if we compare the results obtained with the ES measure (columns 5 in Tables 6 and7) the difference is tremendous (up to almost a billion euros). Nevertheless, choosing the ES measure at a 99.9% confidence level induces a much larger capital amount considering an upper tail depencence structure (Gumbel copula) than an lower tail dependence (Clayton copula).

Model

Gumbel For instance, "Gumbel-GPD" means that we have chosen a Gumbel distribution to model F 9

and a mix of a lognormal and a GPD to model F 6 .

Finally, another exercise allows us to see the influence of the dependence structure on the cells for which we need to know the capital allocation. Applying a vine approach, we obtained a Gumbel copula to model the dependence between several LDFs. Computing the corresponding multivariate VaR, we derived a global capital charge. In Table 11, we projected from the multivariate VaR given in column 7, the amount corresponding to each cell (axis). For example, for the second line corresponding to the "Retail Banking", we can provide the amounts pertaining independently to the "External Fraud", the "Clients, Products & Business Practices", the "Damage to Physical Assets" and the "Business Disruption & System Failures" event types (Table 1 line 3, column 2, 5, 8, 9). Our approach is interesting because it provides the capital for each cell through the dependence structure between the cells. This approach is totally different from the approach mainly used by practitioners who directly compute the capital associated with each cell without taking into account the information given by any other cell.

Table 11 highlights the fact that an upper tail dependence structure (line 3) always provides larger capital charges than the sum of the univariate VaRs. We can also say that the larger the tail of the theoretical distribution, the larger the gap between the ES and the VaR.

Conclusion: New Proposals

In this paper, we discussed a range of options for assessing Basel Pillar 1's capital charges for operational risk. We have expanded them and increased both reliability and precision in our