Carlos Sarraute
email: carlos@coresecurity.com

Olivier Buffet
email: buffet@loria.fr

Jörg Hoffmann
email: hoffmann@cs.uni-saarland.de

POMDPs Make Better Hackers: Accounting for Uncertainty in Penetration Testing

Penetration Testing is a methodology for assessing network security, by generating and executing possible hacking attacks. Doing so automatically allows for regular and systematic testing. A key question is how to generate the attacks. This is naturally formulated as planning under uncertainty, i.e., under incomplete knowledge about the network configuration. Previous work uses classical planning, and requires costly pre-processes reducing this uncertainty by extensive application of scanning methods. By contrast, we herein model the attack planning problem in terms of partially observable Markov decision processes (POMDP). This allows to reason about the knowledge available, and to intelligently employ scanning actions as part of the attack. As one would expect, this accurate solution does not scale. We devise a method that relies on POMDPs to find good attacks on individual machines, which are then composed into an attack on the network as a whole. This decomposition exploits network structure to the extent possible, making targeted approximations (only) where needed. Evaluating this method on a suitably adapted industrial test suite, we demonstrate its effectiveness in both runtime and solution quality.

Introduction

Penetration Testing (short pentesting) is a methodology for assessing network security, by generating and executing possible attacks exploiting known vulnerabilities of operating systems and applications (e.g., [START_REF] Arce | Why attacking systems is a good idea[END_REF]). Doing so automatically allows for regular and systematic testing without a prohibitive amount of human labor, and makes pentesting more accessible to non-experts. A key question is how to automatically generate the attacks.

A natural way to address this issue is as an attack planning problem. This is known in the AI Planning community as the "Cyber Security" domain [START_REF] Boddy | Course of action generation for cyber security using classical planning[END_REF]. Independently (though considerably later), the approach was put forward also by Core Security [START_REF] Lucangeli | Attack planning in the real world[END_REF], a company from the pentesting industry. In that form, attack planning is very technical, addressing the low-level system configuration details that are relevant to vulnerabilities. Herein, we are concerned exclusively with this setting. We consider regular automatic pentesting as done in Core Security's "Core Insight Enterprise" tool. We will use the term "attack planning" in that sense. [START_REF] Lucangeli | Attack planning in the real world[END_REF] encode attack planning into PDDL, and use off-the-shelf planners. This already is useful-in fact, it is currently employed commercially in Core Insight Enterprise, using a variant of Metric-FF (Hoffmann 2003). However, the approach is limited by its inability to handle uncertainty. The pentesting tool cannot be upto-date regarding all the details of the configuration of every machine in the network, maintained by individual users.

Core Insight Enterprise currently addresses this by extensive use of scanning methods as a pre-process to planning, which then considers only exploits, i.e., hacking actions modifying the system state. The drawbacks of this are that (a) this pre-process incurs significant costs in terms of running time and network traffic, and (b) even so, since scans are not perfect, a residual uncertainty remains (Metric-FF is run based on the configuration that appears to be most likely). Prior work [START_REF] Sarraute | An algorithm to find optimal attack paths in nondeterministic scenarios[END_REF] has addressed (b) by associating each exploit with a success probability. This is unable to model dependencies between the exploits, and it still requires extensive scanning (to obtain realistic success probabilities) so does not solve (a). Herein, we provide the first solution able to address both (a) and (b), intelligently mixing scans with exploits like a real hacker would. The basic insight is that penetration testing can be naturally modeled in terms of solving a POMDP.

We encode the incomplete knowledge as an uncertainty of state, thus modeling the possible network configurations in terms of a probability distribution. Scans and exploits are deterministic in that their outcome depends only on the state they are executed in. Negative rewards encode the cost (the duration) of scans and exploits; positive rewards encode the value of targets attained. The model incorporates firewalls, detrimental side-effects of exploits (crashing programs or entire machines), and dependencies between exploits relying on similar vulnerabilities.

POMDP solvers fail to scale to large networks. This is not surprising-even the input model grows exponentially in the number of machines. We show how to address this based on exploiting network structure. We view networks as graphs whose vertices are fully-connected subnetworks, and whose arcs encode the connections between these, filtered by firewalls. We decompose this graph into biconnected compo-nents. We approximate the attacks on these components by combining attacks on individual subnetworks. We approximate the latter by combining attacks on individual machines. The approximations are conservative, i.e., they never overestimate the value of the policy returned. Attacks on individual machines are modeled and solved as POMDPs, and the solutions are propagated back up. We evaluate this approach based on the test suite of Core Insight Enterprise, showing that, compared to a global POMDP model, it vastly improves runtime at a small cost in attack quality.

We next discuss some preliminaries. We then describe our POMDP model, our decomposition algorithm, and our experimental findings, before concluding the paper.

Preliminaries

We fill in some details on network structure and penetration testing. We give a brief background on POMDPs.

Network Structure

Networks can be viewed as directed graphs whose vertices are given by the set M of machines, and whose arcs are connections between pairs of m ∈ M . However, in practice, these network graphs have a particular structure. They tend to consist of subnetworks, i.e., clusters N of machines where every m ∈ N is directly connected to every m ′ ∈ N . By contrast, not every subnetwork N is connected to every other subnetwork N ′ , and typically, if such a connection does exist, then it is filtered by a firewall.

From the perspective of an attacker, the firewalls filter the connections and thus limit the attacks that can be executed when trying to hack into a subnetwork N ′ from another subnetwork N . On the other hand, once the hacker managed to get into a subnetwork N , access to all machines within N is easy. Thus a natural representation of the network, from an attack planning point of view, is that of a graph whose vertices are subnetworks, and whose arcs are annotated with firewalls F . We herein refer to this graph as the logical network LN , and we denote its arcs with N F -→ N ′ . We formalize firewalls as sets of rules describing which kinds of communication (e.g., ports) are disallowed. Thus smaller sets correspond to "weaker" firewalls, and the empty firewall blocks no communication at all.

We remark that, in our POMDP model, we do not provide for privilege escalation, or obtaining passwords. This can instead be modeled at the level of LN . Different privilege levels on the same machine m can be encoded via different copies of m. If controlling m allows the retrieval of passwords, then m can be connected via empty firewalls to the machines m ′ who can be accessed by using these passwords, more precisely to high-privilege copies of these m ′ .

Penetration Testing

Uncertainty in pentesting arises because it is impossible to keep track of all the configuration details of individual machines, i.e., exactly which versions of which programs are installed etc. However, it is safe to assume that the pentesting tool knows the structure of the network, i.e., the graph LN and the filtering done by each firewall: changes to this are infrequent and can easily be registered.

The objective of pentesting is to gain control over certain machines (with critical content) in the network. At any point in time, each machine has a unique status. A controlled machine m has already been hacked into. A reached machine m is connected to a controlled machine, i.e., either m is in a subnetwork N one of whose machines is controlled, or m is in a subnetwork N ′ with a LN arc N F -→ N ′ where one of the machines in N is controlled. All other machines are not reached. The algorithm starts with one controlled machine, denoted here by * .1 We will use the following (small but real-life) situation as a running example:

Example 1 The attacker has already hacked into a machine m ′ , and now wishes to attack a machine m within the same subnetwork. The attacker knows two exploits: SA, the "Symantec Rtvscan buffer overflow exploit"; and CAU, the "CA Unicenter message queuing exploit". SA targets a particular version of "Symantec Antivirus", that usually listens on port 2967. CAU targets a particular version of "CA Unicenter", that usually listens on port 6668. Both work only if a protection mechanism called DEP ("Data Execution Prevention") is disabled.

If SA fails, then it is likely that CAU will fail as well (because DEP is enabled). The attacker is then better off trying something else. Achieving such behavior requires the attack plan to observe the outcomes of actions, and to react accordingly. Classical planning (which assumes perfect world knowledge at planning time) cannot accomplish this.

Furthermore, port scans-observation actions testing whether or not a particular port is open-should be used only if one actually intends to execute a relevant exploit.

Here, if we start with SA, we should scan only port 2967. We accomplish such behavior through the use of POMDPs. By contrast, to reduce uncertainty, classical planning requires a pre-process executing all possible scans. In this example, there are only two-ports 2967 and 6668-however in general there are many, causing significant network traffic and waiting time.

POMDPs

POMDPs are usually defined (e.g., [START_REF] Monahan | A survey of partially observable Markov decision processes[END_REF][START_REF] Kaelbling | Planning and acting in partially observable stochastic domains[END_REF]) by a tuple S, A, O, T, O, r, b 0 . If the system is in state s ∈ S (the state space), and the agent performs an action a ∈ A (the action space), then that results in (1) a transition to a state s ′ according to the transition function T (s, a, s ′ ) = P r(s ′ |s, a), (2) an observation o ∈ O (the observation space) according to the observation function O(s ′ , a, o) = P r(o|s ′ , a) and (3) a scalar reward r(s, a, s ′ ). b 0 , the initial belief, is a probability distribution over S.

The agent must find a decision policy π choosing, at each step, the best action based on its past observations and actions so as to maximize its future gain, which we measure here through the total accumulated reward. The expected value of an optimal policy is denoted with V * .

The agent typically reasons about the hidden state of the system using a belief state b, a probability distribution over S. For our experiments we use SARSOP [START_REF] Kurniawati | SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces[END_REF], a state of the art point-based algorithm, i.e., an algorithm approximating the value function as the upper envelope of a set of hyperplanes, corresponding to a selection of particular belief states (referred to as "points").

POMDP Model

A preliminary version of our POMDP model appeared at the SecArt'11 workshop [START_REF] Sarraute | Penetration testing == POMDP solving[END_REF]. The reader may refer to that paper for a more detailed example listing complete transition and observation models for some actions, and exemplifying the evolution of belief states when applying these actions. In what follows, we keep the description brief in the interest of space.

States

Several aspects of the problem-notably the network structure and the firewall filtering rules-are known and static. POMDP variables encoding these aspects can be compiled out in a pre-process, and are not included in our model.

The states capture the status of each machine (controlled/reached/not reached). For non-controlled machines, they also specify the software configuration (operating system, servers, open ports, . . . ). We specify the vulnerable programs, as well as programs that can provide information about these (e.g., the protection mechanism "DEP" in our running example is relevant to both exploits). The states also indicate whether a given machine or program has crashed.

Finally, we introduce one special terminal state into the POMDP model (of the entire network, not of individual machines). That state corresponds to giving up the attack, when for every available action (if any) the potential benefit is not worth the action's cost. Example 2 The states describe the attacked machine m. For simplicity, we assume that the exploits here do not risk crashing the machine (see also next sub-section). Apart from the terminal state and the state representing that m is controlled, the states specify which programs ("SA" or "CAU") are present, whether they are vulnerable, and whether "DEP" is enabled. Each application is listening on a different port, so a port is open iff the respective application is present, and we do not need to model ports separately. Thus we have a total of 20 states: In short, the states for each machine m essentially are tuples of status values for each relevant program. Global system states then are tuples of these machines-states, with one entry for each m ∈ M . The state space enumerates these tuples. In other words, the state space is factored in a natural way, by programs and machines. An obvious option is, thus, to model and solve the problem using factored POMDPs (e.g., [START_REF] Hansen | Dynamic programming for POMDPs using a factored state representation[END_REF]). We did not try this yet; our POMDP model generator internally enumerates the states, and feeds the ground model to SARSOP. 2The factored nature of our problem also implies that the state space is huge. In a realistic setting, the set C of possible configuration tuples for each machine m ∈ M is very large, yielding an enormous state space

|S| = O(|C| |M | ).
In practice, we will run POMDPs only on single machines, i.e., |M | = 1.

Actions

To reach the terminal state, we need a terminate action indicating that one gives up on the attack.

There are two main types of actions, scans and exploits, which both have to be targeted at reachable machines. Scans can be OS detection actions or port scans. In most cases, they have no effect on the state of the target machine. Their purpose is to gain knowledge about a machine's configuration, by an observation that typically allows to prune some states from the belief (e.g., observing that the OS must be some Windows XP version). Exploits make use of a vulnerability-if present-to gain control over a machine. The outcome of the exploit is observed by the attacker, so a failed exploit may, like a scan, yield information about the configuration (e.g., that a protection mechanism is likely to be running). For a minority of exploits, a failed attempt crashes the machine.

For all actions, the outcome is deterministic: which observation is returned, and whether an exploit succeeds/fails/crashes, is uniquely determined by the target machine's configuration. The outcomes of actions also depend on what firewall (if any) stands between the pentester and the target. If the firewall filters out the relevant port, then the action is unusable: its transition model leaves the state unchanged, and no observation is returned. For example, if a firewall F filters out port 2967, then m_scan_port_2967 and m_exploit_SA are unusable through F , but can be employed as soon as a machine behind F is under control.

Rewards

No reward is obtained when using the terminate action or when in the terminal state.

The instant reward of any scan/exploit action depends on the transition it induces in the present state. Our simple model is to additively decompose the instant reward r(s, a, s ′ ) into r(s, a, s ′ ) = r e (s, a, s ′ ) + r t (a) + r d (a).

Here, (i) r e (s, a, s ′ ) is the value of the attacked machine in case the transition (s, a, s ′ ) corresponds to a successful exploit, and is 0 for all other transitions; (ii) r t (a) is a cost that depends on the action's duration; and (iii) r d (a) is a cost that reflects the risk of detection when using this action. (iii) is orthogonal to the risk of crashing a program/machine, which as described we model as a possible outcome of exploits. Note that (ii) and (iii) may be correlated; however, there is no 1-to-1 correspondence between the duration and detection risk of an exploit, so it makes sense to be able to distinguish these two. Finally, note that (i) results in summing up rewards for successful exploits on different machines. That is not a limiting assumption: one can reward breaking into [m 1 OR m 2 ] by introducing a new virtual machine, accessible at no cost from each of m 1 and m 2 . Example 4 In our example, we set r e = 100 in case of success, 0 otherwise; r t = -10 for all actions; and r d = 0 (no risk of detection). We will see below what effect these settings have on an optimal policy. Since all actions are deterministic, there is no point in repeating them on the same target through the same firewallthis will not produce new effects or bring any new information. In particular, positive rewards cannot be received multiple times. Thus cyclic behaviors incur infinite negative costs. This implies that the expected reward of an optimal policy is finite even without discounting. 3

Designing the Initial Belief

Penetration testing is done at regular time intervals. The initial belief-our knowledge of the network when we start the pentesting-depends on (a) what was known at the end of the previous pentest, and on (b) what may have changed since then. We assume for simplicity that knowledge (a) is perfect, i.e., each machine m at time 0 (the last pentest) is assigned one concrete configuration I(m). We then compute the initial belief as a function b 0 (I, T ) where T is the number of days elapsed since the last pentest. The uncertainty in this belief arises from not knowing which software updates were applied. We assume that the updates are made independently on each machine (simplifying, but reasonable given that updates are controlled by individual users).

A simple model of updates [START_REF] Sarraute | Penetration testing == POMDP solving[END_REF] Here, we use this simple model as the basic building block in a method taking into account that version x of program A may need version y or z of program B. We assume that programs are organized in a hierarchical manner, the operating system being at the root of a directed acyclic graph, and a program having as its parents the programs it directly depends on. This yields a Dynamic Bayesian Network, where each conditional probability distribution is derived from a Markov chain P r(X t = x ′ |X t-1 = x) filtered by a compatibility function δ(X = x, parent 1 (X) = x 1 , . . . , parent k (X) = x k ), that returns 1 iff the value of X is compatible with the parent versions, 0 otherwise. This model of updates is reasonable, but of course still not realistic; future work needs to investigate such models in detail.

We now illustrate how reasoning with the probabilities of the initial belief results in the desired intelligent behavior. Example 6 Say we compute the initial belief b 0 (I, T ) as in Example 5. Since the weight of states 12-20 is high in b 0 , if m_exploit_SA fails, then the success probability of m_exploit_CAU is reduced to the point of not being worth the effort anymore, and the attacker (the optimal policy) gives up, i.e., would try a different attack not prevented by DEP. Namely, consider P r(CAU + |2967 + ), i.e., the probability of m_exploit_CAU succeeding, after observing that port 2967 is open. This corresponds to the weight of (A) states 8 and 11 in Example 2, within the states (B) 6-11 plus 15-20. That weight (A/B) is about 20%. Thus the expected value of m_exploit_CAU in this situation is about 100 * 0.2 [success reward] -10 [action cost] = 10, cf. Example 4, so the action is worthwhile. By contrast, say that m_exploit_SA has been tried and failed. Then (A) is reduced to state 8 only, while (B) still contains (in particular) all the DEP states 15-20. The latter states have a lot of weight, and thus P r(CAU + |2967 + ,SA -) is only about 5%. Given this, the expected value of m_exploit_CAU is negative, and it is better to apply terminate instead.

C5 C2 C3 C4 C6 C7 * C1 * C2 C3 N2 N1 N3 C 1 F 1 3 F * 1 F * 3 F 1 2 F 3 2 C 3 N 1 m m ′ k . . . m ′ 1 F 1 3 F 1 3 F 1 3 ∅ ∅ N 3 (a)

4AL Decomposition Algorithm

As hinted, POMDPs do not scale to large networks (cf. the experiments in the next section). We now present an approach using decomposition and approximation to overcome this problem, relying on POMDPs only to attack individual machines. The approach is called 4AL since it addresses network attack at 4 different levels of abstraction. 4AL is a POMDP solver specialized to attack planning as addressed here. Its input are the logical network LN and POMDP models encoding attacks on individual machines. Its output is a policy (an attack) for the global POMDP encoding LN , as well as an approximation of the value of the global value function. We next overview the algorithm, then fill in some technical details. To simplify the presentation, we will focus on the approximation of the value function, and outline only briefly how to construct the policy.

4AL Overview and Basic Properties

The four levels of 4AL are: (1) Decomposing the Network, (2) Attacking Components, (3) Attacking Subnetworks, and (4) Attacking Individual Machines. We outline these levels in turn before providing technical details. Figure 2 provides illustrations.

• Level 1: Decompose the logical network LN into a tree of biconnected components, rooted at * . In reverse topological order, call Level 2 on each component; propagate the outcomes upwards in the tree.

Every graph decomposes into a unique tree of biconnected components [START_REF] Hopcroft | Algorithm 447: efficient algorithms for graph manipulation[END_REF]. A biconnected component is a sub-graph that remains connected when removing any one vertex. In pentesting, intuitively this means that there is more than one possibility (more than one path) to attack the subnetworks within the component, requiring to reason about the component as a whole (which is the job of Level 2). By contrast, if removing subnetwork X (e.g., N 2 in Figure 2 (b)) makes the graph fall apart into two separate sub-graphs (C 2 vs. the rest of LN , compare also Figure 2 (a)), then all attacks from * to one of these subgraphs (C 2 here) must first traverse X (N 2 here). Thus the overall expected value of the attack can be computed by (1) computing the value of attacking that sub-graph (C 2 ) alone, and (2) adding the result as a pivoting reward to the reward of breaking into X (N 2 ). In other words, we "propagate the outcomes upwards" in the tree displayed in Figure 2 (a).

It is important to note that this tree decomposition will typically result in a huge reduction of complexity. Biconnected components in LN arise only from clusters of more than 2 subnetworks sharing a common (physical) firewall machine. Such clusters tend to be small. In the real-world test scenario used by Core Security and in our experiment here, there is only one cluster, of size 3. In case there are no clusters at all, LN is a tree and 4AL Level 2 trivializes completely.

• Level 2: Given component C, consider, for each rewarded subnetwork N ∈ C, all paths P in C that reach N . Backwards along each P , call Level 3 on each subnetwork and associated firewall. Choose the best path for each N . Aggregate these path values over all N , by summing up but disregarding rewards that were already accounted for by a previous path in the sum.

In case a biconnected component C contains more than one subnetwork, to obtain the best attack on C, in general we have no choice but to encode the entire component as a POMDP. Since that is not feasible, Level 2 considers individual "attack paths" within C. Any single path P is equivalent to a sequence of attacks on individual subnetworks; these attacks are evaluated using Level 3. We consider the rewarded vertices N in separation, enumerating the attack paths and choosing a best one. The values of the best paths are aggregated over all N in a conservative (pessimistic) manner, by accounting for each reward at most once. A strict under-estimation occurs in case the best paths for some rewarded vertices are not disjoint: then these attacks share some of their cost, so a combined attack has a higher expected reward than the sum of independent attacks.

In Figure 2 (b), N 2 and N 3 have a pivoting reward because they allow to reach the components C 2 and C 3 respectively. If the best paths for both N 2 and N 3 go via N 1 (because the firewall F * 3 is very strict), then these paths are not disjoint, duplicating the effort for breaking into N 1 .

Obviously, enumerating attack paths within C is exponential in the size of C. This is the only point in 4AL-apart of course from calls to the POMDP solver-that has worst-case exponential runtime. In practice, biconnected components

-→ N 1 F1 -→ N 2 . . . F k-1 ---→ N k = N where N 1 , . . . , N k ∈ C and N 1 ∈ C * do
/ * Propagate rewards along P , calling Level 3 for attack on each subnetwork. * / 5 R(P ) ← 0; Input: Firewall F , machine m, reward R.

6 for i = k, ..., 1 do 7 R(P ) ← Level3(N i , F i-1 , pr(N i ), R(P )); 8 P (N ) ← arg max(R(P (N )), R(P )); 9 R ← R + R(P (N ));
Output: Approximation V of expected value V * of attacking m through F , given m is reached and the current reward of breaking it is R.

1 if (m, F, R) is cached then 2 return V (m, F, R) 3 M ←createPOMDP(m, F, R); 4 V ←solvePOMDP(M ); 5 Cache (m, F, R) with V ; 6 return V Figure 3: 4AL algorithm, pseudo-code.
are typically small, cf. the above.

• Level 3: Given a subnetwork N and a firewall F through which to attack N , for each machine m ∈ N approximate the reward obtained when attacking m first. For this, modify m's reward to take into account that, after breaking m, we are behind F : call Level 4 to obtain the values of all m ′ = m with an empty firewall; then add these values, plus any pivoting reward, to the reward of m and call Level 4 on this modified m with firewall F . Maximize the resulting value over all m ∈ N .

Consider Figure 2 (c). When attacking N (here, N 3 ) from some machine behind the firewall F (here, F 1

3 ), we have to choose which machine inside N to attack. Given we commit to one such choice m, the attack problem becomes that of breaking into m and afterwards exploiting the direct connection to any m = m ′ ∈ N , and any descendant network (here, C 3 ) we can now pivot to. As described, that can be dealt with by combining attacks on individual machines with modified rewards. (The pivoting reward for descendant networks is computed beforehand by Levels 1 and 2.)

Like Level 2, Level 3 makes a conservative approximation. It fixes a choice of which m ∈ N to attack. By contrast, the best strategy may be to switch between different m ∈ N depending on the success of the attack so far. For example, if one exploit is very likely to succeed, then it may pay off to try this on all m first, before trying anything else.

• Level 4: Given a machine m and a firewall F , model the single-machine attack planning problem as a POMDP, and run an off-the-shelf POMDP solver. Cache known results to avoid duplicate effort.

This last step should be self-explanatory. The POMDP model is created as described earlier. Note that Level 3 may, during the execution of 4AL, call the same machine with the same firewall more than once. For example, in Figure 2 (c), when we switch to attacking m ′ 1 instead of m, the call of Level 4 with m ′ k and an empty firewall is repeated. Summing up, 4AL has low-order polynomial runtime except for the enumeration of paths within biconnected components (Level 2), and solving single-machine POMDPs (Level 4). The decomposition at Level 1 incurs no information loss. Levels 2 and 3 make conservative approximations, so, if the POMDP solutions are conservative (e.g., optimal), then the overall outcome of 4AL is conservative as well.

Technicalities

To provide a more detailed understanding of 4AL, we now discuss pseudo-code for the algorithm, provided in Figure 3. Consider first Algorithm 1. It should be clear how the overall structure of the algorithm corresponds to our previous discussion. It calls the linear-time algorithm by [START_REF] Hopcroft | Algorithm 447: efficient algorithms for graph manipulation[END_REF] (hereafter, HT) to find the decomposition. The loop i = k, . . . , 1 processes the components in reverse topological order. The pivoting reward function pr encodes the propagation of rewards upwards in the tree; this should be self-explanatory apart for the expression "the parent" of C i in LN . The latter relies on the fact that, after "clean-up" (line 2), each component has exactly one such parent.

To explain the clean-up, note first that HT works on undirected graphs; when applying it, we ignore the direction of the arcs in LN . The outcome is an undirected tree of biconnected components, where the cut vertices-those vertices removing which makes the graph break apart-are shared between several components. In Figure 2 (b), e.g., N 2 prior to the clean-up belongs to both, C 1 and C 2 . The clean-up sets the root of the tree to * , and assigns each cut-vertex to the component closest to * (e.g., N 2 is assigned to C 1 ); * itself is turned into a separate component. Re-introducing the direction of arcs in LN , we then prune vertices not reachable from * . Next, we remove arcs that cannot participate in any non-redundant attack path starting in * . Since moving towards * in the decomposition tree necessarily leads any attack back to a vertex it has visited (broken into) already, after such removal the arcs between components form a directed tree as in Figure 2 (a). Each non-root component C i (e.g., C 3 ) has exactly one parent component C in the cleaned-up tree (e.g., C 1 ). The respective subnetwork N ∈ C (e.g., N 3 ) is a cut vertex in LN . Thus, as claimed above, N is the only vertex, in LN , that connects into C i .

Obviously, all attacks on C i must pass through its parent N . Further, the vertices and arcs removed by clean-up cannot be part of an optimal attack. Thus Level 1 is loss-free. To state this-and the other properties of 4AL-formally, we need some notations. We will use V * to denote the real (optimal) expected value of an attack, and V to denote the 4AL approximation. The attacked object is given as the argument. For example, V * (LN ) is the expected value of attacking LN ; V (C, pr) is the outcome of running 4AL Level 2 on component C and pivoting reward function pr.

Proposition 1 Let LN be a logical network. Say that, for all calls to 4AL Level 2 made by 4AL Level 1 when run on LN , we have V (C, pr) = V * (C, pr). Then V (LN ) = V * (LN ). If V (C, pr) ≤ V * (C, pr) for all calls to 4AL Level 2, then V (LN ) ≤ V * (LN ).

Consider now Algorithm 2. Our previous description was imprecise in omitting the additional algorithm argument pr. This integrates with the algorithm by being passed on, for every subnetwork on the paths we consider (line 7), to Algorithm 3 which adds it to the reward obtained for hacking into that subnetwork (Algorithm 3 line 4).

R aggregates the values (lines 1, 9), over all rewarded subnetworks N . This aggregation is made conservative by removing all rewards-pivoting rewards as well as the own rewards of the individual machines involved-that have already been accounted for (line 10). ). The calls to Level 3 (line 7) comprise the network N i to be hacked into, the firewall F i-1 that must be traversed for doing so, the pivoting reward of N i , as well as the ongoing path reward R(P ) which gets propagated backwards along the path. Clearly, this is equivalent to the sequence of attacks required to execute P , and harvesting all pivoting rewards associated with such an attack. Thus, with the conservativeness of the aggregation across the subnetworks N , we get:

Proposition 2 Let C be a biconnected component, and let pr be a pivoting reward function. Say that, for all calls to 4AL Level 3 made by 4AL Level 2 when run on (C, pr), we have V (F, N, pR, pathR) ≤ V * (F, N, pR, pathR). Then V (C, pr) ≤ V * (C, pr).

Algorithms 3 and 4 should be self-explanatory, given our previous discussion. Just note that the pivoting reward pR is represented by the arc from m to C 3 in Figure 2 (c), which is accounted for by simply adding it to the value of m (Algorithm 3 line 4). The path reward pathR (not illustrated in Figure 2 (c)) is also added to the value of m (Algorithm 3 line 4). Max'ing over attacks on the individual machines m is, obviously, a conservative approximation because attack strategies are free to choose m. Thus: Proposition 3 Let F be a firewall, let N be a subnetwork, let pR be a pivoting reward, and let pathR be a path reward. Say that, for all calls to 4AL Level 4 made by 4AL Level 3 when run on (F, N, pR, pathR), we have

V (F, m, R) ≤ V * (F, m, R). Then V (F, N, pR, pathR) ≤ V * (F, N, pR, pathR).

Policy Construction

At Level 1, the global policy is constructed from the Level 2 policies simply by following the tree decomposition: starting at the tree root, we execute the Level 2 policies for all reached components (in any order); once a hack into a component succeeds, the respective children components become reached. At Level 2, i.e., within a bi-connected component C, the policy corresponds to the set of paths P considered by Algorithm 2. Each P is processed in turn. For each node N in P (until failure to enter that subnetwork), we call the corresponding Level 3 policy.

At Level 3, i.e., considering a single subnetwork N , our policy simply attacks the machine m ∈ N that yielded the maximum in Algorithm 3. The policy first attacks m through the firewall, using the respective Level 4 policy. In case the attack succeeds, the policy attacks the remaining machines m ′ ∈ N in any order (i.e., for each m ′ , we perform the associated Level 4 policy until termination). At Level 4, the policy is the POMDP policy returned by our POMDP solver.

Experiments

We evaluated 4AL against the "global" POMDP model, encoding the entire attack problem into a single POMDP. The experiments are run on a machine with an Intel Core2 Duo CPU at 2.2 GHz and 3 GB of RAM. The 4AL algorithm is implemented in Python. To solve and evaluate the POMDPs generated by Level 4, we use the APPL toolkit. 4

Test Scenario

Our test scenario is based on the network structure shown in Figure 5. The attack begins from the Internet ( * is the cloud in the top left corner). The network consists of three areas-Exposed, Sensitive, User-separated by firewalls. Internally, each of Exposed and Sensitive is fully connected (i.e., these areas are subnetworks), whereas User consists of a tree of subnetworks separated by empty firewalls. Only two machines are rewarded, one in Sensitive (reward 9000) and one in a leaf subnetwork of User (reward 5000). The cost of port scans and exploits is 10, the cost of OS detection is 50. We allow to scale the number of machines |M | by distributing, of every 40 machines, the first one to Exposed, the second one to Sensitive, and the remaining 38 to User. The exploits are taken from Core Security's database. The number of exploits |E| is scaled by distributing these over 13 templates, and assigning to each machine m one such template as I(m) (the known configuration at the time of the last pentest). The initial belief b 0 (I, T ), where T is the time elapsed since the last pentest, is then generated as outlined.

The fixed parameters here (rewards, action costs, distribution of machines over areas, number of templates) are estimated based on practical experiences at Core Security. The network structure and exploits are realistic, and are used for industrial testing in that company. The main weakness of 4 APPL 0.93 at http://bigbird.comp.nus.edu.sg/pmwiki/farm/appl/ the scenario lies in the approximation of software updates underlying b 0 (I, T ). Altogether, the scenario is still simplified, but is natural and does approach the complexity of real-world penetration testing.

For lack of space, in what follows we scale only |M | and |E|, fixing |T | = 50. The latter is realistic but challenging: pentesting is typically performed about once a month; smaller T are easier to solve as there is less uncertainty. The scaling behavior over |M | clearly reflects the fact that 4AL is polynomial in that parameter, except for the size of biconnected components (which is 3 here). Scaling E yields more challenging single-machine POMDPs, resulting in a sometimes steep growth of runtime. However, even with |M | and |E| both around 100, which is a realistic size in practice, the runtime is always below 37 seconds.

Approximation Loss

Scaling Up

Conclusion

We have devised a POMDP model of penetration testing that allows to naturally represent many of the features of this application, in particular incomplete knowledge about the network configuration, as well as dependencies between different attack possibilities, and firewalls. Unlike any previous methods, the approach is able to intelligently mix scans with An important open question is to what extent our POMDP+decomposition approach is more cost-effective than the classical planning solution currently employed by Core Security. Our next step will be to answer this question experimentally, comparing the attack quality of 4AL against that of the policy that runs extensive scans and then attaches FF's plan for the most probable configuration.

4AL is a domain-specific algorithm and, as such, does not contribute to the solution of POMDPs in general. At a high level of abstraction, its idea can be understood as imposing a template on the policy constructed, thus restricting the space of policies explored (and employing special-purpose algorithms within each part of the template). In this, the approach is somewhat similar to known POMDP decomposition approaches (e.g., [START_REF] Pineau | Policycontingent abstraction for robust robot control[END_REF][START_REF] Müller | HTN-style planning in relational POMDPs using first-order FSCs[END_REF]. It remains to be seen whether this connection can turn out fruitful for either future work on attack planning, or POMDP solving more generally.

The main directions for future work are to devise more accurate models of software updates (hence obtaining more realistic designs of the initial belief); to tailor POMDP solvers to this particular kind of problem, which has certain special features, in particular the absence of non-deterministic actions and that some of the uncertain parts of the state (e.g. the operating systems) are static; and to drive the industrial application of this technology. We hope that these will inspire other researchers as well.

  LN as tree of components C. (b) Paths for attacking C 1 .(c) Attacking N 3 from N 1 , using m first.

Figure 2 :

 2 Figure 2: Illustration of Levels 1, 2, and 3 (from left to right) of the 4AL algorithm.

Algorithm 1 :

 1 Level 1 (Decomposing the Network) Input: LN : Logical Network. Output: Approximation V of expected value V * of attacking LN from controlled machine * . / * Decompose LN into tree DLN of biconnected components, rooted at * ; see text for ''clean-up''. * / 1 DLN ←HopcroftTarjan(LN ); 2 Set tree root to * and clean-up LN and DLN ; 3 C 1 , . . . , C k ← a topological ordering of DLN ; 4 Intitialize pivoting reward pr(N ) for all N ∈ LN to 0; 5 for i = k, ..., 1 do / * Call Level 2 to attack each component. * / 6 V (C i ) ←Level2(C i , pr); / * Propagate expected reward. * / 7 N ← the parent of C i in LN ; 8 pr(N ) ← pr(N ) + V (C i ); 9 return pr( * ) Algorithm 2: Level 2 (Attacking Components) Input: Biconnected component C, reward function pr. Output: Approximation V of expected value V * of attacking C, given its parent is controlled and its pivoting rewards are pr. 1 R ← 0; / * Account for each rewarded vertex N . * / 2 while ∃N ∈ C s.t. r(N ) > 0 or pr(N ) > 0 do 3 P ← ; R(P ) ← 0; P (N ) ← P ; / * Maximize over all simple paths (no repeated vertices) from an entry vertex to N . * / 4 foreach simple path P of the form

F0

  10 r(N i ), pr(N i ) ← 0 for all vertices N i on P (N ); 11 return R Algorithm 3: Level 3 (Attacking Subnetworks) Input: Firewall F , subnetwork N , rewards pR, pathR. Output: Approximation V of expected value V * of attacking N through F , given F is reached, N 's pivoting reward is pR, and the path reward behind N is pathR. 1 R ← 0; / * Maximize over reward obtained when hacking first into a particular machine m ∈ N . * / 2 foreach m ∈ N do 3 R(m) ← r(m); / * After breaking m, we can pivot behind N , and reach all m = m ′ ∈ N without F . * / 4 R(m) ← R(m) + pR + pathR; 5 foreach m = m ′ ∈ N do 6 R(m) ← R(m)+Level4(m ′ , ∅, r(m ′ )); 7 R ← max(R, Level4(m, F, R(m))); 8 return R Algorithm 4: Level 4 (Attacking Individual Machines)

  Regarding the individual machines, Algorithm 2 uses the shorthands (a) r(N ) > 0 (line 2) and (b) r(N ) ← 0 (line 10); (a) means that there exists m ∈ N so that r(m) > 0; (b) means that r(m) ← 0 for all m ∈ N . Regarding pivoting rewards, note that line 10 of Algorithm 2 modifies the function pr maintained by Algorithm 1. This does not lead to conflicts because, at the time when Algorithm 1 calls Algorithm 2 on component C, all descendants of C in LN have already been processed, and thus in particular Algorithm 1 will make no further updates to the value of pr(N ), for any N ∈ C. By C * (line 4) we denote the set {N ∈ C | ∃N ′ ∈ LN, N ′ ∈ C : (N ′ , N ) ∈ LN } of subnetworks that serve as an entry into C (e.g., N 1 and N 3 for C 1 in Figure 2 (b)). Note in line 4 that the path P starts with a firewall F 0 . To understand this, consider the situation addressed. The algorithm assumes that the parent N of C ( * , for component C 1 in Figure 2 (b)) is under control. But then, to break into C, we still need to traverse an arc from N into C. F 0 is the firewall on the arc chosen by P (F * 1 or F * 3 in Figure 2 (b)

Figure 5 :

 5 Figure 5: Network structure in our test suite.

Figure 4

 4 Figure 4 (a) shows the relative loss of quality when running 4AL instead of a global POMDP solution, for values of |E| and |M | where the latter is feasible. We show quality(global -POMDP )quality(4AL) in percent of quality(global -POMDP ). Policy quality here is estimated by running 2000 simulations. That measurement incurs a variance, which is almost stronger than the very small quality advantage of the global POMDP solution. The maximal loss for any combination of |E| and |M | is 14.1% (at |E| = 7, |M | = 6), the average loss over all combinations is 1.96%. The average loss grows monotonically over |M |, from -1.14% for |M | = 1 to 4.37% for |M | = 6. Over |E|, the behavior is less regular; the maximum average loss, 5.4%, is obtained when fixing |E| = 5.

Figure 4

 4 Figure 4 (b) shows the runtime of 4AL when scaling up to much larger values of |E| and |M |.The scaling behavior over |M | clearly reflects the fact that 4AL is polynomial in that parameter, except for the size of biconnected components (which is 3 here). Scaling E yields more challenging single-machine POMDPs, resulting in a sometimes steep growth of runtime. However, even with |M | and |E| both around 100, which is a realistic size in practice, the runtime is always below 37 seconds.

Figure 4 :

 4 Figure 4: Empirical results for 4AL compared to a global POMDP model. exploits. While this accurate solution does not scale, large networks can be tackled by a decomposition algorithm. Our present empirical results suggest that this is accomplished at a small loss in quality relative to a global POMDP solution.An important open question is to what extent our POMDP+decomposition approach is more cost-effective than the classical planning solution currently employed by Core Security. Our next step will be to answer this question experimentally, comparing the attack quality of 4AL against that of the policy that runs extensive scans and then attaches FF's plan for the most probable configuration.4AL is a domain-specific algorithm and, as such, does not contribute to the solution of POMDPs in general. At a high level of abstraction, its idea can be understood as imposing a template on the policy constructed, thus restricting the space of policies explored (and employing special-purpose algorithms within each part of the template). In this, the approach is somewhat similar to known POMDP decomposition approaches (e.g.,[START_REF] Pineau | Policycontingent abstraction for robust robot control[END_REF][START_REF] Müller | HTN-style planning in relational POMDPs using first-order FSCs[END_REF]. It remains to be seen whether this connection can turn out fruitful for either future work on attack planning, or POMDP solving more generally.The main directions for future work are to devise more accurate models of software updates (hence obtaining more realistic designs of the initial belief); to tailor POMDP solvers to this particular kind of problem, which has certain special features, in particular the absence of non-deterministic actions and that some of the uncertain parts of the state (e.g. the operating systems) are static; and to drive the industrial application of this technology. We hope that these will inspire other researchers as well.

  Example 3 In our example, there are five possible actions: The POMDP model specifies, for each state in Example 2, the outcome of each action. For example, m_exploit_SA succeeds if and only if SA is present and vulnerable, and DEP is disabled. Hence, when applied to either of the states 9, 10, or 11, m_exploit_SA results in state 2, and returns the observation succeeded. Applied to any other state, m_exploit_SA leaves the state unchanged, and the observation is failed.

	m_exploit_SA
	m_exploit_CAU
	m_scan_port_2967
	m_scan_port_6668
	terminate

  encodes the uncertain evolution of each program independently, in terms of a Markov chain. The states The three independent Markov chains used to model the update mechanism in our example network. in each chain correspond to the different versions of the program, and the transitions model the possible program updates (with estimated probabilities that these updates will be made). The initial belief then is the distribution resulting from this chain after T steps.Example 5 In our running example, the three components in the single machine are DEP, CAU and SA. They are updated via three independent Markov chains, each with two states, as illustrated in Figure1. The probabilities indicate how likely the machine is to transition from one state to another during one day. Say we set T = 30, and run the Markov chains on the configuration I in which m has DEP disabled, and both SA and CAU are vulnerable to the attacker's exploit. In the resulting initial belief b 0 (I, T ), DEP is likely to be enabled; the weight of states 12-20 in Example 2 is high in b 0 (> 70%).

	.0452		.015		.012
	no DEP	DEP	SA vul	SA	CAU vul	CAU
	0		.003		.002
	.9548	1	.985	.997	.988	.998
	Figure 1:

For simplicity, we will notate * as a separate vertex in LN . If * is part of a subnetwork N , this means to turn N \ { * } into a separate vertex in LN , connected to * via the empty firewall.

Note that this approach enables certain non-trivial optimizations: some of the states in Example 2 could be merged. If DEP is enabled, then it does not matter whether or not CAU/SA are vulnerable. For brevity, we do not discuss this in detail here.

In fact, the problem falls into the class of Stochastic Shortest Path Problems[START_REF] Bertsekas | Neurodynamic Programming[END_REF].

Acknowledgments. Work performed while Jörg Hoffmann was employed by INRIA, Nancy, France.


Mauricio Araya-López

Vincent Thomas

Olivier Buffet

Near-Optimal BRL using Optimistic Local Transitions

Model-based Bayesian Reinforcement Learning (BRL) allows a sound formalization of the problem of acting optimally while facing an unknown environment, i.e., avoiding the exploration-exploitation dilemma. However, algorithms explicitly addressing BRL suffer from such a combinatorial explosion that a large body of work relies on heuristic algorithms. This paper introduces bolt, a simple and (almost) deterministic heuristic algorithm for BRL which is optimistic about the transition function. We analyze bolt's sample complexity, and show that under certain parameters, the algorithm is nearoptimal in the Bayesian sense with high probability. Then, experimental results highlight the key differences of this method compared to previous work.

Introduction

Acting in an unknown environment requires trading off exploration (acting so as to acquire knowledge) and exploitation (acting so as to maximize expected return). Model-Based Bayesian Reinforcement Learning (BRL) algorithms achieve this while maintaining and using a probability distribution over possible models (which requires expert knowledge under the form of a prior).These algorithms typically fall within one of the three following classes [START_REF] Asmuth | A Bayesian sampling approach to exploration in reinforcement learning[END_REF].

Belief-lookahead approaches try to optimally trade off exploration and exploitation by reformulating RL as the problem of solving a POMDP where the state is a pair ω = (s, b), s being the observed state and b the distribution over the possible models; yet, this problem is intractable, allowing only computationally expensive approximate solutions [START_REF] Poupart | An analytic solution to discrete Bayesian reinforcement learning[END_REF].

Optimistic approaches propose exploration mechanisms that explicitly attempt to reduce the model uncertainty [START_REF] Brafman | R-max -a general polynomial time algorithm for near-optimal reinforcement learning[END_REF][START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF][START_REF] Sorg | Variance-based rewards for approximate Bayesian reinforcement learning[END_REF][START_REF] Asmuth | A Bayesian sampling approach to exploration in reinforcement learning[END_REF] by relying on the principle of "optimism in the face of uncertainty".

Undirected approaches, such as ǫ-greedy or Boltzmann exploration strategies [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF], perform exploration actions independent of the current knowledge about the environment.

We focus here on optimistic approaches and, as most research in the field and without loss of generality, we consider uncertainty on the transition function, assuming a known reward function. For some algorithms, recent work proves that they are either PAC-MDP [START_REF] Strehl | Reinforcement learning in finite MDPs: PAC analysis[END_REF]-with high probability they often act as an optimal policy would do (if the MDP model were known)-or PAC-BAMDP [START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF]-with high probability they often act as an ideal belief-lookahead algorithm would do.

This paper first presents background on model-based BRL in Section 2, and on PAC-MDP and PAC-BAMDP analysis in Section 3. Then, Section 4 introduces a novel algorithm, bolt, which, (1) as boss [START_REF] Asmuth | A Bayesian sampling approach to exploration in reinforcement learning[END_REF], is optimistic about the transition model-which is intuitively appealing since the uncertainty is about the model-and, (2) as beb [START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF], is (almost) deterministic-which leads to a better control over this approach. We then prove in Section 5 that bolt is PAC-BAMDP for infinite horizons, by generalizing previous results known for beb for finite horizon. Experiments in Section 6 then give some insight as to the practical behavior of these algorithms, showing in particular that bolt seems less sensitive to parameter tuning than beb.

Background

Reinforcement Learning

A Markov Decision Process (MDP) [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF] is defined by a tuple S, A, T, R where S is a finite set of states, A is a finite set of actions, the transition function T is the probability to transition from state s to state s ′ when some action a is performed: T (s, a, s ′ ) = P r(s ′ |s, a), and R(s, a, s ′ ) is the instant scalar reward obtained during this transition. Reinforcement Learning (RL) [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF] is the problem of finding an optimal decision policya mapping π : S → A-when the model (T without R in our case) is unknown but while interacting with the system. A typical performance criterion is the expected discounted return

V π µ (s) = E π ∞ t=0 γ t R(s t , a t , s t+1 ) | s 0 = s, T = µ ,
where µ ∈ M is the unknown model and γ ∈ [0, 1] is a discount factor. Under an optimal policy, this state value function verifies the Bellman optimality equation (for all s ∈ S):

V * µ (s) = max a∈A s ′ ∈S T (s, a, s ′ ) R(s, a, s ′ ) + γV * µ (s ′ ) ,
and computing this optimal value function allows to derive an optimal policy by behaving in a greedy manner, i.e., by picking actions in arg max a∈A Q * µ (s, a), where the state-action value function Q * µ is defined as

Q * µ (s, a) = s ′ ∈S T (s, a, s ′ ) R(s, a, s ′ ) + γV * µ (s ′ ) .
Typical RL algorithms either (i) directly estimate the optimal state-action value function Q * µ (model-free RL), or (ii) learn T to compute V * µ or Q * µ (model-based RL). Yet, in both cases, a major difficulty is to pick actions so as to trade off exploitation of the current knowledge and exploration to acquire more knowledge.

Model-based Bayesian RL

We consider here model-based Bayesian Reinforcement Learning [START_REF] Strens | A Bayesian framework for reinforcement learning[END_REF], i.e., model-based RL where the knowledge about the model is represented using a probability distribution b over all possible transition models. An initial prior distribution b 0 = P r(µ) has to be specified, which is then updated using Bayes rule. At time t the posterior b t depends on the initial distribution b 0 and the state-action history so far h t = s 0 , a 0 , • • • , s t-1 , a t-1 , s t . This update can be applied sequentially due to the Markov assumption, i.e., at time t + 1 we only need b t and the triplet (s t , a t , s t+1 ) to compute the new distribution:

b t+1 = P r(µ|h t+1 , b 0 ) = P r(µ|s t , a t , s t+1 , b t ). (1)
The distribution b t is known as the belief over the model, and summarizes the information that we have gathered about the model at the current time step.

If we consider the belief as part of the state, the resulting belief-MDP can be solved optimally in theory. Remarkably, modelling RL problems as belief-MDPs provides a sound way of dealing with the explorationexploitation dilemma, because both objectives are naturally included in the same optimization criterion.

The belief-state can thus be written as ω = (s, b), which defines a Bayes-Adaptive MDP (BAMDP) [START_REF] Duff | Optimal learning: Computational procedures for Bayes-adaptive Markov decision processes[END_REF], a special kind of belief-MDP where the belief-state is factored into the (visible) system state and the belief over the (hidden) model. Moreover, due to the integration over all possible models in the value function of the BAMDP, the transition function T (ω, a, ω ′ ) is given by

P r(ω ′ |ω, a) = P r(b ′ |b, s, a, s ′ )E[P r(s ′ |s, a)|b],
where the first probability is 1 if b ′ complies with Eq. ( 1) and 0 else. The optimal Bayesian policy can then be obtained by computing the optimal Bayesian value function [START_REF] Duff | Optimal learning: Computational procedures for Bayes-adaptive Markov decision processes[END_REF][START_REF] Poupart | An analytic solution to discrete Bayesian reinforcement learning[END_REF]:

V * (s, b) = max a s ′ E[P r(s ′ |s, a)|b](R(s, a, s ′ ) + γV * (s ′ , b ′ )) = max a s ′ T (s, a, s ′ , b)(R(s, a, s ′ ) + γV * (s ′ , b ′ )) , (2)
with b ′ the posterior after the Bayes update with (s, a, s ′ ). For the finite horizon case we can use the same reasoning, so that the optimal value can be computed in theory for a finite or infinite horizon, by performing Bayes updates and computing expectations. However, in practice, computing this value function exactly is intractable due to the large branching factor of the tree expansion.

Here, we are interested in heuristic approaches following the optimism in the face of uncertainty principle, which consists in assuming a higher return on the most uncertain transitions. Some of them solve the MDP generated by the expected model (at some stage) with an added exploration reward which favors transitions with lesser known models, as in r-max [START_REF] Brafman | R-max -a general polynomial time algorithm for near-optimal reinforcement learning[END_REF], beb [START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF], or with variance based rewards [START_REF] Sorg | Variance-based rewards for approximate Bayesian reinforcement learning[END_REF]. Another approach, used in boss [START_REF] Asmuth | A Bayesian sampling approach to exploration in reinforcement learning[END_REF], is to solve, when the model has changed sufficiently, an optimistic estimate of the true MDP (obtained by merging multiple sampled models).

Flat and Structured Priors

The selection of a suitable prior is an important issue in BRL algorithms, because it has a direct impact on the solution quality and computing time. A naive approach is to consider one independent Dirichlet distribution for each state-action transition, known as Flat-Dirichlet-Multinomial prior (FDM), whose pdf is defined as

b = f (µ; θ) = s,a D(µ s,a ; θ s,a ),
where D(•; •) are independent Dirichlet distributions.

FDMs can be applied to any discrete state-action MDP, but is only appropriate under the strong assumption of independence of the state-action pairs in the transition function. However, this prior has been broadly used because of its simplicity for computing the Bayesian update and the expected value. Consider that the vector of parameters θ are the counters of observed transitions, then the expected value of a transition probability is

E[P r(s ′ |s, a)|b] = θs,a(s ′ )
s ′′ θs,a(s ′′ ) , and the Bayesian update under the evidence of a transition (s, a, s ′ ), is reduced only to θ ′ s,a (s ′ ) = θ s,a (s ′ ) + 1. Even though FDMs are useful to analyze and benchmark algorithms, in practice they are inefficient because they do not exploit structured information about the problem. One can for example encode the fact that multiple actions share the same model by factoring multiple Dirichlet distributions, or allow the algorithm to identify such structures using Dirichlet distributions combined using Chinese Restaurant Processes or Indian Buffet Processes [START_REF] Asmuth | A Bayesian sampling approach to exploration in reinforcement learning[END_REF].

PAC Algorithms

Probably Approximately Correct Learning (PAC) provides a way of analyzing the quality of learning algorithms [START_REF] Valiant | A theory of the learnable[END_REF]. The general idea is that with high probability 1 -δ (probably), a machine with a low training error produces a low generalization error bounded by ǫ (approximately correct). If the number of steps needed to arrive to this condition is bounded by a polynomial function, then the algorithm is PACefficient.

PAC-MDP Analysis

In RL, the PAC-MDP property [START_REF] Strehl | Reinforcement learning in finite MDPs: PAC analysis[END_REF] guarantees that an algorithm generates an ǫ-close policy with probability 1 -δ in all but a polynomial number of steps. An important result is the general PAC-MDP Theorem 10 in [START_REF] Strehl | Reinforcement learning in finite MDPs: PAC analysis[END_REF], where three sufficient conditions are presented to comply with the PAC-MDP property. First, the algorithm must use at least near optimistic values with high probability. Also, the algorithm must guarantee with high probability that it is accurate, meaning that, for the known parts of the model, its actual evaluation will be ǫ-close to the optimal value function. Finally, the number of non-ǫ-close steps (also called sample complexity) must be bounded by a polynomial function.

In mathematical terms, PAC-MDP algorithms are those for which, with probability 1 -δ, the evaluation of a policy A t , generated by algorithm A at time t over the real underlying model µ 0 , is ǫ-close to the optimal policy over the same model in all but a polynomial number of steps:

V At µ0 (s) ≥ V * µ0 (s) -ǫ. (3)
Several RL algorithms comply with the PAC-MDP property, differing from one another mainly on the tightness of the sample complexity bound. For example, r-max and Delayed Q-Learning [START_REF] Strehl | Reinforcement learning in finite MDPs: PAC analysis[END_REF] are some classic RL algorithms for which this property has been proved, whereas BOSS [START_REF] Asmuth | A Bayesian sampling approach to exploration in reinforcement learning[END_REF]) is a Bayesian RL algorithm which is also PAC-MDP.

In PAC-MDP analysis the policy produced by an algorithm should be close to the optimal policy derived from the real underlying MDP model. This utopic policy [START_REF] Poupart | An analytic solution to discrete Bayesian reinforcement learning[END_REF] cannot be computed, because it is impossible to learn exactly the model with a finite number of samples, but it is possible to reason on the probabilistic error bounds of an approximation to this policy.

PAC-BAMDP Analysis

An alternative to the PAC-MDP approach is to be PAC with respect to the optimal Bayesian policy, rather than using the optimal utopic policy. We will call this PAC-BAMDP analysis, because its aim is to guarantee closeness to the optimal solution of the Bayes-Adaptive MDP. This type of analysis was first introduced in [START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF], under the name of near-Bayesian property, where it is shown that a modified version of beb is PAC-BAMDP for the undiscounted finite horizon case1 .

Let us define how to evaluate a policy in the Bayesian sense:

Definition 3.1. The Bayesian evaluation V of a policy π is the expected value given a distribution over

Bayes update MDP MDP b t → b t+1 i i i + 1 i + 1 t t + 1 E[µ|b t ] ∞ E[µ|b t+1 ] 0 H H Figure 1
. exploit-like algorithm. At each time step t, algorithm performs a Bayes update of the prior, and solves the MDP derived from the expected model of the belief.

models b:

V π (s, b) = E µ [V π µ (s)|b] = M V π µ (s)P r(µ|b)dµ.
This definition has already been presented implicitly by [START_REF] Duff | Optimal learning: Computational procedures for Bayes-adaptive Markov decision processes[END_REF] , but it is very important to point out the difference between a normal MDP evaluation over some known MDP, and the Bayesian evaluation2 . This definition is consistent with Eq. 2, where

V * (s, b) = max π M V π µ (s)P r(µ|b)dµ = max a s ′ E[P r(s ′ |s, a)|b](R(s, a, s ′ ) + γV * (s ′ , b ′ )) .
Let us define the PAC-BAMDP property:

Definition 3.2. We say that an algorithm is PAC-BAMDP if, with probability 1 -δ, the Bayesian evaluation of a policy A t generated by algorithm A at time t is ǫ-close to the optimal Bayesian policy in all but a polynomial number of steps, where the Bayesian evaluation is parametrized by the belief b:

V At (s, b) ≥ V * (s, b) -ǫ, (4)
with δ ∈ [0, 1) and ǫ > 0.

A major conceptual difference is that in PAC-BAMDP analysis, the objective is to guarantee approximate correctness because the optimal Bayesian policy is hard to compute, while in PAC-MDP analysis, the approximate correctness guarantee is needed because the optimal utopic policy is impossible to find in a finite number of steps.

Optimistic BRL Algorithms

Sec. 2.2 has shown how to theoretically compute the optimal Bayesian value function. This computation being intractable, it is common to use suboptimalyet efficient-algorithms. A popular technique is to maintain a posterior over the belief, select one representative MDP based on the posterior and act according to its value function. The baseline algorithm in this family is called exploit [START_REF] Poupart | An analytic solution to discrete Bayesian reinforcement learning[END_REF], where the expected model of b is selected at each time step. Therefore, the algorithm has to solve a different MDP of horizon H-an algorithm parameter, not the problem horizon-at each time step t as can be seen in Fig. 1. We will consider for the analysis that H is the number of iterations i that value iteration performs at each time step t, but in practice convergence can be reached long before the theoretically derived H for the infinite horizon case.

beb [START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF] follows the same idea as exploit, but adding an exploration bonus to the reward function. In contrast, boss [START_REF] Asmuth | A Bayesian sampling approach to exploration in reinforcement learning[END_REF] does not use the exploit approach, but samples different models from the prior and uses them to construct an optimistic MDP. beb has the advantage of being an almost deterministic algorithm 3 and does not rely on sampling as boss. On the other hand, boss is optimistic about the transitions, which is where the uncertainty lies, meanwhile beb is optimistic about the reward function, even though this function is known.

Bayesian Optimistic Local Transitions

In this section, we introduce a novel algorithm called bolt (Bayesian Optimistic Local Transitions), which relies on acting, at each time step t, by following the optimal policy for an optimistic variant of the current expected model. This variant is obtained by, for each state-action pair, optimistically boosting the Bayesian updates before computing the local expected transition model. This is achieved using a new MDP with an augmented action space A = A × S, where the transition model for action α = (a, σ) in state s is the local expected model derived from b t updated with an artificial evidence of transitions λ η s,a,σ = {(s, a, σ), . . . , (s, a, σ)} of size η (a parameter of the algorithm). In other words, we pick both an action a plus the next state σ we would like to occur with a higher probability. The MDP can be solved as follows:

V bolt i (s, b t ) = max α s ′ T (s, α, s ′ , b t ) R(s, a, s ′ ) + γV bolt i-1 (s ′ , b t ) with T (s, α, s ′ ) = E[P r(s ′ |s, a)|b t , λ η s,a,σ
]. bolt's value iteration neglects the evolution of b t , but the modified transition function works as an optimistic approximation of the neglected Bayesian evolution.

Modifying the transition function seems to be a more natural approach than modifying the reward function as in beb, since the uncertainty we consider in these problems is about the transition function, not about the reward function.

From a computational point of view, each update in bolt requires |S| times more computations than each update in beb. This implies computation times multiplied by |S| when solving finite horizon problems using dynamic programming, and probably a similar increase for value iteration. However, under structured priors, not all the next states σ must be explored, but only those which are possible transitions.

Here, the optimism is controlled by the positive parameter η-an integer or real-valued parameter depending on the family of distributions-and the behaviour using different parameter values will depend on the used family of distributions. However, for common priors like FDMs, it can be proved that bolt is always optimistic with respect to the optimal Bayesian value function.

Lemma 4.1 (bolt's Optimism). Let (s t , b t ) be the current belief-state from which we apply bolt's value iteration with an horizon of H and η = H. Let also b t be a prior in the FDM family, and let V H (s t , b t ) be the optimal Bayesian value function. Then, we have

V bolt H (s t , b t ) ≥ V H (s t , b t ).
[Proof in [START_REF] Araya-López | Nearoptimal BRL using optimistic local transitions (extended version)[END_REF]]

Analysis of BOLT

In this section we prove that bolt is PAC-BAMDP in the discounted infinite horizon case, when using a FDM prior. The other algorithm proved to be PAC-BAMDP is beb, but the analysis provided in [START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF] is only for finite horizon domains with an imposed stopping condition for the Bayes update. Therefore, we include in [START_REF] Araya-López | Nearoptimal BRL using optimistic local transitions (extended version)[END_REF] an analysis of beb using the results of this section in order to be able to compare these algorithms theoretically afterwards.

By Definition 3.2, we must analyze the policy A t generated by bolt at time t, i.e., A t = argmax π V bolt,π H (s t ), and show that, with high probability and for all but a polynomial number of steps, this policy is ǫ-close to the optimal Bayesian policy.

Theorem 5.1 (bolt is PAC-BAMDP). Let A t denote the policy followed by bolt at time t with η = H. Let also s t and b t be the corresponding state and belief at that time. Then, with probability at least 1 -δ, bolt is ǫ-close to the optimal Bayesian policy

V At (s t , b t ) ≥ V * (s t , b t ) -ǫ for all but Õ |S||A|η 2 ǫ 2 (1-γ) 2 = Õ |S||A|H 2 ǫ 2 (1-γ) 2 time steps. [Proof in Section 5.2]
In the proof we will see that H depends on ǫ and γ. Therefore, the sample complexity bound and the optimism parameter η will depend only on the desired correctness (ǫ,δ) and the problem characteristics (γ,|S|,|A|).

Mixed Value Function

To prove that bolt is PAC-BAMDP we introduce some preliminary concepts and results. First, let us assume for the analysis that we maintain a vector of transition counters θ, even though the priors may be different from FDMs for the specific lemma presented in this section. As the belief is monitored, at each step we can define a set K = {(s, a)| θ s,a ≥ m} of known state-action pairs [START_REF] Kearns | Near-optimal reinforcement learning in polynomial time[END_REF], i.e., state-action pairs with "enough" evidence. Also, to analyze an exploit-like algorithm A in general (like exploit, bolt or beb) we introduce a mixed value function Ṽ obtained by performing an exact Bayesian update when a state-action pair is in K, and A's update when not in K. Using these concepts, we can revisit Lemma 5 of [START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF] for the discounted case.

Lemma 5.2 (Induced Inequality Revisited). Let V π H (s t , b t ) be the Bayesian evaluation of a policy π, a = π(s, b) be an action from the policy. We define

Ṽπ i (s, b) = (5) s ′ T (s, a, s ′ , b)(R(s, a, s ′ ) + γ Ṽπ i-1 (s ′ , b ′ )) if (s, a) ∈ K s ′ T (s, a, s ′ )( R(s, a, s ′ ) + γ Ṽπ i-1 (s ′ , b ′ )) if (s, a) / ∈ K
the mixed value function, where T and R can be different from T and R respectively. Here, b ′ is the posterior parameter vector after the Bayes update with (s, a, s ′ ). Let also A K be the event that a pair (s, a) / ∈ K is generated for the first time when starting from state s t and following the policy π for H steps. Assuming normalized rewards for R and a maximum reward Rmax for R, then

V π H (s t , b t ) ≥ Ṽπ H (s t , b t ) - (1 -γ H ) (1 -γ) Rmax P r(A K ), (6)
where P r(A K ) is the probability of event A K .

[Proof in [START_REF] Araya-López | Nearoptimal BRL using optimistic local transitions (extended version)[END_REF]]

BOLT is PAC-BAMDP

Let ṼAt

H (s t , b t ) be the evaluation of bolt's policy A t using a mixed value function where R(s, a, s ′ ) = R(s, a, s ′ ) the reward function, and T (s, a, s ′ ) = T (s, α, s ′ , b t ) = E[P r(s ′ |s, a)|b t , λ η s,a,σ ] the bolt transition model, where a and σ are obtained from the policy A t . Note that, even though we apply bolt's update, we still monitor the belief at each step as presented in Eq. 5. Yet, for T we consider the belief at time t, and not the monitored belief b as in the Bayesian update Lemma 5.3 (bolt Mixed Bound). The difference between the optimistic value obtained by bolt and the Bayesian value obtained by the mixed value function under the policy A t generated by bolt with η = H is bounded by

V bolt H (s t , b t ) -ṼAt H (s t , b t ) ≤ (1 -γ H )η 2 (1 -γ)m . (7)
[Proof in [START_REF] Araya-López | Nearoptimal BRL using optimistic local transitions (extended version)[END_REF]]

Proof of Theorem 5.1. We start by the induced inequality (Lemma 5.2) with A t the policy generated by bolt at time t, and Ṽ a mixed value function using bolt's update when (s, a) / ∈ K. As Rmax = 1, the chain of inequalities is

V At (s t , b t ) ≥ V At H (s t , b t ) ≥ ṼAt H (s t , b t ) - 1 -γ H 1 -γ P r(A K ) ≥ V bolt H (s t , b t ) - η 2 (1 -γ H ) m(1 -γ) - 1 -γ H 1 -γ P r(A K ) ≥ V * H (s t , b t ) - η 2 (1 -γ H ) m(1 -γ) - 1 -γ H 1 -γ P r(A K ) ≥ V * (s t , b t ) - η 2 (1 -γ H ) m(1 -γ) - 1 -γ H 1 -γ P r(A K ) - γ H (1 -γ)
where the 3 rd step is due to Lemma 5.3 (accuracy) and the 4 th step to Lemma 4.1 (optimism). To simplify the analysis, let us assume that γ

H (1-γ) = ǫ 2 and fix m = 4η 2 ǫ(1-γ) . If P r(A K ) > η 2 m = ǫ(1-γ)

4

, by the Hoeffding 4 and union bounds we know that A K occurs no more than

O |S||A|m P r(A K ) log |S||A| δ = O |S||A|η 2 ǫ 2 (1 -γ) 2 log |S||A| δ
4 Even though the Hoeffding bound assumes that samples are independent, which is trivially not in MDPs, it upper bounds the case where samples are dependent. Recent results shows that tighter bounds can be achieve with a more elaborated analysis [START_REF] Szita | Model-based reinforcement learning with nearly tight exploration complexity bounds[END_REF].

time steps with probability 1 -δ. By neglecting logarithms we have the desired theorem. This bound is derived from the fact that, if A K occurs more than |S||A|m times, then all the state-action pairs are known and we will never escape from K anymore.

For P r(A K ) ≤ η 2 m , we have that

V At (s t , b t ) ≥ V * (s t , b t ) - ǫ(1 -γ H ) 4 - ǫ(1 -γ H ) 4 - ǫ 2 ≥ V * (s t , b t ) - ǫ 4 - ǫ 4 - ǫ 2 = V * (s t , b t ) -ǫ
which verifies the proposed theorem.

Following [START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF], optimism can be ensured for beb with β ≥ 2H 2 , with Õ |S||A|H 4 ǫ 2 (1-γ) 2 non ǫ-close steps (see [START_REF] Araya-López | Nearoptimal BRL using optimistic local transitions (extended version)[END_REF]), which is a worse result than bolt. Nevertheless, the bounds used in the proofs are loose enough to expect the optimism property to hold for much smaller values of β and η in practice.

Experiments

To illustrate the characteristics of bolt, we present here experimental results over a number of domains. For all the domains we have tried different parameters for bolt and beb, but also we have used an ε-greedy variant of exploit. However, for all the presented problems plain exploit (ε = 0.0) outperforms the εgreedy variant.

Please recall that the theoretical values for parameters β and η-that ensure optimism-depend on the horizon H of the MDPs solved at each time step. In these experiments, instead of using this horizon we relied on asynchronous value iteration, stopping when V i+1 -V i ∞ < ǫ. For solving these infinite MDPs we used γ = 0.95 and ǫ = 0.01, but be aware that the performance criterion used here is averaged undiscounted total rewards.

The Chain Problem

In the 5-state chain problem [START_REF] Strens | A Bayesian framework for reinforcement learning[END_REF][START_REF] Poupart | An analytic solution to discrete Bayesian reinforcement learning[END_REF], every state is connected to state s 1 by taking action b and every state s i is connected to the next state s i+1 with action a, except s 5 that is connected to itself. At each step, the agent may "slip" with probability p, performing the opposite action as intended. Staying in s 5 had a reward of 1.0 while coming back to s 1 had a reward of 0.2. All other rewards are 0. The priors used for these problems were Full (FDM), Tied, where the probability p is factored for all transitions, and Semi, where each action has an independent factored probability.

Algorithm

Tied Semi Full exploit (ε = 0) 366.1 354.9 230.2 beb (β = 1) 365.9 362.5 343.0 beb (β = 150) 366.5 297.5 165.2 bolt (η = 7) 367.9 367.0 Averaged total reward over 500 trials for an horizon of 1000 with p = 0.2. The results with * come from previous publications.

Table 1 shows that beb outperforms other algorithms with a tuned up β value for the FDM prior as already shown by [START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF]. However, for a large value of β, this performance decreases dramatically. bolt on the other hand produces results comparable with boss for a tuned parameter, but does not decrease too much for a large value of η. Indeed, this value corresponds to the theoretical bound that ensures optimism, η = H ≈ log(ǫ(1 -γ))/ log(γ) ≈ 150. Unsurprisingly, the results of beb and bolt with informative priors are not much different than other techniques, because the problem degenerates into a easily solvable problem. Nevertheless, bolt achieves good results for a large η, in contrast to beb that fails to provide a competitive result for the Semi prior with large β.

This variability in the results depending on the parameters, rises the question of the sensitivity to parameter tuning. In a RL domain, one usually cannot tune the algorithm parameters for each problem, because the whole model of the problem is unknown. Therefore, a good RL algorithm must perform well for different problems without modifying its parameters.

Fig. 2 shows how beb and bolt behave for different parameters using a Full prior. In the low resolution analysis beb's performance decays very fast, while bolt also tends to decrease, but maintaining good results. We have also conducted experiments for other values of the slip probability p, the same pattern being amplified when p is near 0, i.e., worse decay for beb and almost constant bolt results, and obtaining almost identical behavior when p is near 0.5. In the high resolution results beb goes up and down near 1, while bolt maintains a similar behaviour as in the low resolution experiment.

Other Structured Problems

An other illustrative example is the Paint/Polish problem where the objective is to deliver several polished and painted objects without a scratch, using several stochastic actions with unknown probabilities. The full description of the problem can be found in [START_REF] Walsh | Exploring compact reinforcement-learning representations with linear regression[END_REF]. Here, the possible outcomes of each action are given to the agent, but the probabilities of each outcome are not. We have used a structured prior that encodes this information and the results are summarized in Fig. 3, using both high and low resolution analyses. We have also performed this experiment with an FDM prior, obtaining similar results as for the Chain problem. Unsurprisingly, using a structured prior provides better results than using FDMs. However, the high impact of being overoptimistic shown in Fig. 3, does not apply to FDMs, mainly because the learning phase is much shorter using a structured prior. Again, the decay of beb is much stronger than bolt, but in contrast to the Chain problem, the best parameter of bolt beats the best parameter of beb.

The last example is the Marble Maze problem5 [START_REF] Asmuth | A Bayesian sampling approach to exploration in reinforcement learning[END_REF] where we have explicitly encoded the 16 possible clusters in the prior, leading to little exploration requirements. exploit provides very good solutions for this problem, and bolt provides similar results with several different parameters. In contrast, for all the tested β parameters, beb behaves much worse than exploit. For example, for the best η = 2.0 bolt scores -0.445, while for the best β = 0.9 beb scores -2.127, while exploit scores -0.590.

In summary, it is hard to know a priori which algorithm will perform better for a specific problem with a specific prior and given certain parameters. However, bolt generalizes well (in theory and in practice) for a larger set of parameters, mainly because the optimism is bounded by the probability laws and not by a free parameter as in beb.

Conclusion

We have presented bolt, a novel and simple algorithm that uses an optimistic boost to the Bayes update, which is thus optimistic about the uncertainty rather than just in the face of uncertainty. We showed that bolt is strictly optimistic for certain η parameters, and used this result to prove that it is also PAC-BAMDP. The sample complexity bounds for bolt are tighter than for beb. Experiments show that bolt is more efficient than beb when using the theoretically derived parameters in the Chain problem, and in general that bolt seems more robust to parameter tuning. Future work includes using a dynamic η bonus for bolt, what should be particularly appropriate with finite horizons, and exploring general proofs to guarantee the PAC-BAMDP property for a broader family of priors than FDMs.

  Low resolution analysis β, η ∈ [1, 100] High resolution analysis β, η ∈ [0.1, 10]

Figure 2 .

 2 Figure 2. Chain Problem. Averaged total reward over 300 trials for an horizon of 150, and for β and η parameters between 1 and 100, and between 0.1 and 10. As a reference, the value obtained by exploit is also plotted. All results are shown with a 95% confidence interval. Low resolution Analysis β, η ∈ [1, 100]

Figure 3 .

 3 Figure 3. Paint/Polish Problem. Averaged total reward over 300 trials for an horizon of 150, for several values of β and η using an structured prior. As a reference, the value obtained by exploit is also plotted. All results are shown with a 95% confidence interval.

Table 1 .

 1 Chain Problem results for different priors.

		289.6
	bolt (η = 150)	366.6 358.3 278.7
	beetle *	365.0 364.8 175.4
	boss *	365.7 365.1 300.3

However, some-rectifiable-errors have been spotted in the proof of near-Bayesianness of beb in[START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF], as discussed with the authors.

We use a different notation for the Bayesian evaluation, V, to distinguish it from a normal MDP evaluation V .

Averaged over 100 trials with H = 100.