INTRODUCTION

Path planning is a standard task in robotics, but it becomes much harder if we need to account for stochastic perturbations, adversarial interactions, and incomplete information about the dynamics or the environment. With repeated tasks, Reinforcement Learning (RL) provides a popular framework for optimizing the system performance based on the information accumulated in prior episodes while ensuring the asymptotic convergence to the globally optimal solution as the number of planning episodes grows (Sutton and Barto, 2018). In continuous setting, most applications of RL are focused on learning the process dynamics (Recht, 2019) using frequent or continuous observations of the system state. Our focus here is on a rather different class of problems, where the controlled dynamics are known, but the process termination is a random event, whose probability distribution is not only trajectory-dependent but also a priori unknown.

More specifically, we study the online path planning strategy for an Evader (E), who attempts to escape a region while minimizing the probability of being detected en route. Surveillance intensity imposed by the opponent(s) is assumed to be spatially inhomogeneous, making the choice of E's capture-evading trajectory important. This general setting is motivated by prior work on environmental crime modeling (Cartee and Vladimirsky, 2020) and surveillance avoidance (Gilles and Vladimirsky, 2020;Cartee et al., 2019). However, unlike in those prior papers, here the surveillance intensity is initially unknown to E, who needs to learn it on relevant parts of the domain through multiple planning episodes 1 . Whenever E is spotted, this results in capture and immediately terminates the trajectory. But the evidence obtained about the surveillance intensity on already traced parts of that trajectory can be used to improve the planning in future episodes. Such multi-episodic setting might seem unusual in capture/surveillance avoidance, but it arises naturally in several applied contexts including the environmental crime modeling. E.g., in many parts of Brazil, illegal forrest loggers are primarily subsistence farmers in need of firewood for family use (Chen et al., 2021). When apprehended, their punishment is usually wood confiscation plus sometimes a small fine. Repeat offenders are common, and they also share information with each other on paths taken or locations where they were caught in the past. Another example comes from asymmetries in modern warfare, where many types of UAVs become increasingly cheap -particularly compared to effective air defense systems for large geographic areas.

We develop an approach that balances the exploration against exploitation and uses spatial correlations for efficient learning. Our algorithm relies on numerical meth-ods for solving PDEs (Sethian, 1996), statistical estimates with censored data (Shorack and Wellner, 2009), Gaussian process (GP) regression (Williams and Rasmussen, 2006), and strategic exploration techniques from RL (Kocsis and Szepesvári, 2006;Azar et al., 2017). To simplify the exposition, our method is described and benchmarked here under the assumption that the Evader is isotropic (i.e., E can change the direction of motion instantaneously and the available speed depends on its current position, but not on its chosen direction). However, our main ideas are more broadly applicable, and the approach is also suitable for more realistic (anisotropic) agent dynamics.

We start by reviewing the basic problem with known random termination (capture) intensity in section 2. Section 3 poses the problem with unknown intensity and defines performance metrics for episodic path planning. We follow this with a review of algorithms for strategic exploration on graphs developed for finite horizon Markov Decision Processes and explain why their usefulness is rather limited in our continuous setting. In section 4 we describe a new approach based on Bayesian models of surveillance intensity function and episodic path planning based on the Confidence Bounds. We show that piecewise-continuous models lead to simpler algorithms but are usually outperformed by models based on GP-regression. The advantages of our methods are illustrated on several sample problems in section 5. We conclude by considering possible future extensions in section 6.

PATH PLANNING WITH KNOWN INTENSITY

Suppose E starts at x in some compact domain Ω ⊂ R 2 and moves with isotropic speed f (x). The motion of E is governed by:

where a : R → S 1 is a measurable control function specifying the direction of motion at every moment.

Define T a = min{s ≥ 0 | y(s) ∈ ∂Ω} as the domainexit time if E starts from x and uses the control a(•). The location-dependent surveillance intensity is a smooth, positive function K(x), which in this section is assumed to be fully known in advance. If E decides to follow a trajectory y(•), the probability of remaining undetected until time t is

where S is the random time when E is spotted and immediately captured, thus terminating the trajectory. E's goal is to maximize its probability of reaching ∂Ω or, equivalently, to minimize the cumulative intensity:

As usual in dynamic programming, the value function u(x) is defined to encode the result of optimal choices

and can be found as a solution of a Hamilton-Jacobi-Bellman equation (Bardi and Capuzzo-Dolcetta, 2008).

Here we focus on isotropic dynamics/intensity; i.e., f and K do not depend on a, which further simplifies the PDE to the following Eikonal equation:

This isotropic setting creates a one-to-one correspondence between a control function and a path. From now on, we interchangeably use the terms "determining a control function" and "selecting a path".

In general, (5) often does not have a classical solution, but always has a unique Lipschitz continuous viscosity solution (Bardi and Capuzzo-Dolcetta, 2008). Wherever ∇u exists, the optimal a is opposite to the gradient direction (a * = -∇u/|∇u|). The set on which u is not differentiable has measure zero and is comprised of all starting positions from which the optimal trajectory to ∂Ω is not unique.

Efficient numerical methods for solving (5) have been extensively studied in the last 25 years. Many of these algorithms take advantage of the causality found in upwind finite-difference discretizations: a gridpoint only depends on its smaller adjacent neighbors, making it possible to solve the system of discretized equations non-iteratively. We choose Fast Marching Method(FMM) (Sethian, 1996), which is a Dijkstra-like algorithm that has O(N log N ) computational complexity when solving (5) on a grid with N gridpoints. Once the value function is approximated, an optimal trajectory can be obtained starting from any x ∈ Ω by gradient decent in u until reaching ∂Ω.

MULTI-EPISODIC PLANNING WITH UNKNOWN K(x)

With a known K(x), E should persist in choosing a fixed optimal path deterministically, even though the outcomes (whether and where E is captured) may be different every time. But what if K(x) is a priori unknown and only learned gradually by trying different paths? If E faces a repeated task of surveillance-avoidance en route to ∂Ω, a natural interpretation is to find a path-selection policy that optimizes some long-term performance metric. This is a reinforcement learning (RL) problem, with information gradually collected in a sequence of episodes. Clearly, if E selects enough random trajectories that sufficiently cover the whole region, eventually K(x) can be approximately recovered. However, this approach is inefficient since E's goal is to learn K(x) only on those parts of Ω that are relevant to reduce the frequency of captures, asymptotically approaching the probability along the truly optimal trajectory, which would be chosen if K(x) were known.

To assess the long-term performance of a policy, a frequently considered criterion is regret, which is expected excess of cost due to not selecting the optimal control for all episodes. Letting ∆ i be the indicator of whether E is captured during the ith episode, we define the experimentally observed excess rate of captures

where W * = 1 -exp(-u(x 0 )) is the minimum capture probability. If an optimal a * (•) were used in each episode, the regret S j would converge to 0 as j → ∞.

Prior work: RL algorithms on graphs

Before delving into the continuous problem, we first present a discrete version on a finite directed graph G and examine the possibility of applying well-known RL algorithms. Suppose E starts from a node v 0 , moves between adjacent nodes, and tries to avoid capture en route to a set of target nodes Ξ. We assume that a transition along any edge e incurs some capture probabilityfoot_2 Ψ e ∈ (0, 1). If P denotes the set of all paths from v 0 to Ξ, we would prefer to use p ∈ P which maximizes the probability of not being captured up to Ξ; i.e., max p∈P e∈p (1 -Ψ e ) or, equivalently, min p∈P e∈p -log(1 -Ψ e ). When all Ψ e 's are known, this becomes a standard shortest path problem, with C e = -log(1 -Ψ e ) interpreted as edge weights, and the classical Dijkstra's method can solve it efficiently. Alternatively, this can be viewed as a simple Markov Decision Process (MDP) by adding an absorbing "captured state" node v c . In this MDP interpretation, an action corresponds to a choice of the next attempted edge e, a capture event is modeled as a transition to v c , and a unit reward is earned only upon reaching Ξ.

Of course, we are interested in the case where Ψ e s are not known in advance, and it would seem natural to address this by any of the RL algorithms developed to maximize the expected return in MDPs with unknown transition functions. This includes the Q-learning (Watkins and Dayan, 1992), temporal difference methods (Sutton, 1988), Thompson sampling (Thompson, 1933), and the techniques based on upper confidence bounds (UCB) (Auer, 2002). The latter served as a basis for a popular model-free Upper Confidence bounds on Trees (UCT) algorithm (Kocsis and Szepesvári, 2006), in which the evidence gathered in previous episodes is used to estimate the rewards of all (state, action) pairs, but the exploration of less visited pairs is encouraged by adding a bonus term proportional to each estimate's standard deviation. The same idea is also used in more recent model-based methods (Dann and Brunskill, 2015;Azar et al., 2017), in which prior evidence is used to model the transition probabilities and the value function is computed in each episode based on the current model but with similar bonus terms added to encourage the exploration.

While the above algorithms were originally designed for MDPs with a fixed finite horizon, they can also be adapted to our "exit time" case. For simplicity, suppose that Ω is discretized using a uniform Cartesian grid of nodes V, with each interior node v connected by edges to its 8 closest neighbors -corresponding to 8 actions (directions of motion) available at that node. We will use E(v) to denote all edges available at v and E for the set of all edges in the graph. Using the MDP interpretation, the process terminates upon reaching Ξ ⊂ V (which discretizes ∂Ω) or v c (in case of capture). To implement UCT, we maintain the statistics N v (and N e ) on how many times each state (and each edge -or state-action pair) is visited over multiple episodes, with Q e encoding the fraction of those visits on which E traversed e but was captured before reaching Ξ.

The selection of nodes is summarized in Algorithm 1, with the parameter λ > 0 regulating the rate of exploration.

Algorithm 1 UCT: model-free planning on a graph Set Q e = 0, N e = 0, N v = 0 for all v and e while t = 1 : T do capture = search(v 0 ); end while

The model-based version on a graph (which we will denote Alg-D, for "discrete") is implemented on the same grid, but relies on learning Ψ e for the relevant edges. We maintain statistics N e (and φ e ) on how many times a visit (and capture) happen for each edge e. An estimate of Ψ e is com-puted as Ψe = φ e N e and the confidence-bound-modified version is

where |E| is the total number of edges, and Ψ ≥ 0 is a known lower bound on all Ψ e , while γ ∈ (0, 1) is a parameter controlling the decay of expected regretfoot_3 . In each episode, we solve a shortest path problem based on edge weights Ĉe = -log(1 -Ψe ). Then we simulate running through the derived optimal path and update edge statistics N e and φ e , which are used to change Ĉe in the next episode. The resulting method is summarized in Algorithm 2.

Algorithm 2 Alg-D: model-based planning on a graph Set φ e = 0, N e = 0 for all e. while t = 1 : T do Update Ψe according to (7); Solve the deterministic shortest path problem with edge costs Ĉe = -log(1 -Ψe ); Simulate running through the Ψ-optimal path from v 0 using the actual Ψ;

Update φ e and N e accordingly; end while Unfortunately, as we show in Section 5, the performance of such methods is rather poor in our continuous setting. First, to ensure S j → 0, the number of actions/edges per node would have to grow as we refine the graph -otherwise, we will not be able to obtain all possible directions of motion in the limit. The methods above are hard to use in MDPs with large action sets and are not directly usable in MDPs with infinite action spaces. Second, in UCT any capture yields an equal penalty for all edges successfully traversed in that episode (even if the true Ψ e is quite low along some of them). This is why model-based methods, such as Alg-D, are preferable for this class of problems even on graphs. Third, and most importantly, both UCT and Alg-D do not account for correlations in (unknown) transition functions of different (state, action) pairs. In the continuous case, the smoothness of surveillance rate K(x) makes the spatial correlations crucial. Ignoring this feature results in much slower learning.

In the next section, we overcome these limitations by introducing new methods for continuous model learning and path planning based on a confidence-bounds-modified version of the model.

MODEL-BASED METHODS ON Ω

Piecewise-constant models of K and planning based on confidence bounds

As a first attempt to solve the continuous problem, we decompose Ω into a collection G of non-overlapping subdomains/cells and assume that K(x) is a constant on each of them. We define three auxiliary objects to gather data inside each cell over many episodes:

• G c : the total number of captures in a cell;

• G t : the total time spent in a cell;

• G n : the total number of visits/entries into a cell.

We will use K ∈ R |G| 0,+ to represent a piecewise constant estimate of K(x) and σ2 ∈ R |G| 0,+ to denote the elementwise estimated variance of K.

Focusing on a single cell, suppose that the surveillance intensity is indeed some (unknown) constant: K(x) = K cell . Enumerating all episodes in which our planned trajectory involved traveling through that cell and capture did not occur before we reached it, suppose in the k-th such episode our plan is to exit that cell after time t k . The capture time S k would be an exponentially distributed random variable with rate K cell , but of course we only get to observe its right censored (Shorack and Wellner, 2009) version R k = min(S k , t k ). For convenience, we also define a capture indicator δ k , which is equal to 1 if we are caught before exiting that cell and 0 otherwise (implying R k = t k ). Assuming there were n such visits to this cell up to the current episode, this right-censored data (δ k , R k ) n k=1 can be used to derive the maximum likelihood estimate (MLE)

The asymptotic expression for Kcell 's variance is

Using the fact that E[δ k ] = 1 -exp(-K cell t k ), we can estimate this asymptotic variance as

Using G c and G t notation, K and σ can be written as K = G c /G t , σ2 = G c /G 2 t on each cell. Inspired by the confidence bound techniques on graphs, we can also build up a "lower-confidence" intensity. Since this modification can produce negative values and our observation intensity must be non-negative, we do not approximate K directly but instead model Z(x) = log K(x). We use the statistic Zcell = log( Kcell ) as an estimator for Z values at a cell center, with Kcell defined as in (9). If Kcell is asymptotically distributed as N (µ K , σ 2 K ) with σ K approaching 0, then by local linearization of the logarithm (known as the delta method (Van der Vaart, 2000)), we have that Zcell is asymptotically distributed as

Using G c and G t notation, we estimate the mean and variance for Zcell by

This allows us to define corresponding piecewise-constant functions Z(x) and σZ (x). Our lower-confidence-adjusted intensity is constructed as

Designed similarly to (7), the constant factor multiplying σZ (x) balances the exploration vs exploitation and depends on the total number of episodes T , the number of cells |G|, and γ ∈ (0, 1) controls the rate of exploration. The resulting formula yields low values of K in rarely visited cells, thus encouraging the exploration if those cells are relevant for paths from x 0 to ∂Ω. (E.g., a cell with a low K might be completely irrelevant if passing through it requires traversing other high-K cells or if there exists a much shorter/safer path from x 0 to ∂Ω.) Since the above defined K is also piecewise-constant, the K-optimal trajectory will be polygonal, but finding its exact shape still requires solving an Eikonal equation. We use a Fast Marching Method (Sethian, 1996) to do this on a finer grid G pd .

Algorithm 3 summarizes the resulting method. To avoid Z in (11) becoming infinity, we initialize G t as a small positive constant and G c as K init so that initially G c /G t equals to some constant K initfoot_4 .

GP regression models of K and planning based on confidence bounds

Algorithm 3 ignores the correlations between K values in different cells and updates each cell independently. In this section, we capture spatial correlation in the intensity by using a Gaussian process (GP) (Williams and Rasmussen, 2006). A Gaussian process is a collection of Gaussian random variables indexed by x, with mean m(x) and covariance Σ(x, x ). Some common choices of Σ(x, x ) are, e.g. the squared exponential kernel

Algorithm 3 Alg-PC: planning with a piecewise-constant model Input: γ, .

Set

Numerically solve |∇û(x)| = K(x); Find an optimal path from x 0 using û(x); Simulate that path using the real K(x); Update G c , G t , G n using simulation results; Compute Z, σZ according to (11); end while or the Matérn kernel

where d = |x -x | , Γ is the gamma function, and B ν is the modified Bessel function of the second kind. Here, (α, β) are hyperparameters that can be learned from data while the parameter ν in the Matérn kernel controls the differentiability of GP and can reflect our assumptions about the level of regularity of K(x).

Criteria * . We only use cells whose estimates of K are accurate enough as inputs of GP regression. Here we introduce a list of rules to select these cells from G:

• G c ≥ 1, preventing 1/G c from becoming infinity.

• G n ≥ n min , guaranteeing enough entries into a cell. Our implementation uses n min = 20.

• G t ≥ t min , avoiding extremely short traverses. Our implementation sets t min to the time sufficient to traverse a cell's diameter.

We denote the cells satisfying Criteria * as G ob ⊂ G and their centers as X ob . Let Zob , σob be Z, σZ values at X ob reshaped as vectors. Use Σ as an abbreviation of

The GP posterior mean M (x) for Z based on noisy observations at X ob is

Another advantage of GP model is that we simultaneously obtain the posterior covariance

The resulting method is summarized in Algorithm 4. We note that partial knowledge K(x) can be encoded in a prior mean m(x), though in our experiments m(x) was simply set to a positive constant on the entire Ω. The final GP posterior variance ρ(x). Figure 4 shows the regret metric (i.e., the excess rate of captures S) for all of the benchmarked algorithms.

Figure 1: Bimodal surveillance intensity K(x). Most of the selected paths are around three locally optimal paths with the longer one being globally optimal.

The following observation hold true for all examples:

• Capture locations (magenta dots) in subfigure (iii) give rough indications of which parts of Ω Alg-GP prefers to explore. It mostly selects paths around locally optimal ones, and during the later episodes it focuses more on the vicinity of the globally optimal one, showing a proper balance between exploration and exploitation. Indeed, the two paths in subfigure (iv) indicate that Alg-GP's final prediction (black) approximately matches the true optimal path ). The shortest exiting path induces a higher capture probability, while the actual optimal path takes a longer detour towards a lower intensity region. Selected paths mostly cluster around two locally optimal paths, with one of them being globally optimal.

(red).

• In Figure 4, Alg-GP's averaged excess capture rate continuously decreases and appears to confirm the convergence. The third example contains multiple locally optimal (and roughly comparable) paths and requires more episodes to learn the globally optimal one, which explains the slow decrease of S in later episodes.

• In contrast, Alg-D and Alg-PC exhibit a consistently slower improvement of S and even stagnation -indicating that model-learning takes substantially longer for these methods.

• UCT algorithm generates much larger regrets than all others. We have also tested it with more episodes (10 5 ∼ 10 6 ), but the results still show obvious stagnation. The main reason is that UCT learns the state-action functions directly. It regards a whole path as a single datum and overlooks the information of not being captured along the earlier parts of the path, which could be used to improve the estimates for K.

• Both Alg-D and UCT restrict the Evader to move only along one of the eight directions. In principle, this will result in a gap between the truly optimal W * and the risk along the best path on this graph even after infinitely many episodes. However, as we show in Supplementary Materials, in these examples that gap is much smaller than the observed regret S.

Remarks on grid effects: Our use of a discrete observation grid G essentially lumps together all captures within one cell and limits the algorithm's ability to learn the true K. To account for this more accurately, we could mod-Figure 3: An intensity with eight peaks and multiple locally optimal paths. The peak around the southeast corner is displaced slightly, creating a gap in K(x) and the optimal path reflects this. Alg-GP attempts to discover each locally optimal path but concentrates more around three paths with one of them being globally optimal.

ify our definition of the regret metric, measuring the regret relative to the best path learnable on the specific G. We include such detailed tests in Supplementary Materials. But in summary we note that they demonstrate yet another advantage of GP regression:

1) For Alg-GP, if we assume infinitely many captures in each cell, the ideal (asymptotically learnable) W * = 1exp(J * ) is only very weakly dependent on G. E.g., the W * is already within 0.25% from the truly optimal W * = 1exp(-u(x 0 )) for all examples considered above even with a coarse 10 × 10 observation grid.

2) For Alg-PC, the ideal learnable W * can improve significantly when we refine G. Asymptotically, the averaged regret is certainly better for finer observation grids. But they also present a challenge since many more episodes are needed to obtain a reasonable approximation of K in all potentially relevant cells before the finer grid's asymptotic advantage becomes relevant. E.g., re-running the example from Figure 2 with T = 60, 000, Alg-PC yields a lower averaged regret on a 10×10 observation grid than on a 40×40 grid for the first 50,000 episodes, while the averaged regret on a 20 × 20 grid is much smaller throughout.

3) The effects of the computational grid G pd appear to be negligible in all of our simulations. The errors due to discretizing the Eikonal PDE are dominated by the errors due to uncertainty in K and the G effects described above.

Computational complexity: The cost of each episode consists of two components: (a) updating surveillance intensity model and (b) HJB-based path-planning using the current model. The cost of (a) for Alg-PC scales as O(|G|); i.e., linearly in the number of subdomains/cells. For Alg-GP, the complexity of this stage depends on the size of G ob (the collection of cells satisfying Criteria * ). During each episode, the cost of Alg-GP's update is dominated by solving the linear system in updating posterior covariance (16), which is O(|G ob | 3 ) and |G ob | is usually quite small compared to |G|. Alg-GP also includes an additional cost of periodically re-tuning the hyperparameters.

The use of the Fast Marching Method makes the actual path planning in each episode quite fast even for much finer G pd .

The cost of (b) is dominated by solving the PDE on a grid, which in our setting is O(N log N ) on a discretization grid G pd with N gridpoints. The latter cost can be prohibitive high-dimensional generalizations since N grows nentially with the dimension of Ω. The usual approach to overcome this "curse of dimensionality" is to use Approximate DP (e.g., based on mesh-free HJB discretizations), but this is not necessary in our 2D setting.

Learning less regular K: We have also used Examples 1-3 to test Alg-GP with the Matérn kernel, taking ν = 5/2. The results are quite similar to those of Alg-GPe and thus omitted. But the situation is noticeably different when the actual K(x) is non-smooth or even discontinuous. Figure 5 shows two such examples, modifying the smooth intensity from Figure 3. Suppose the center of a peak is x c , our first example replaces each single Gaussian peak by K single (x) = max{0, K p -|x -x c |} where K p > 0 is the maximum. Such a surveillance intensity (used in Example 4) is still continuous but not smooth. In Example 5, we replace each Gaussian peak by a piecewise constant function: K single (x) = K c when |x -x c | ≤ r for some radius r > 0 while K single (x) = 0 otherwise. In both cases, a small positive constant was later added to ensure that the resulting K(x) > 0 for all x ∈ Ω.

We have conducted these experiments with both the squared exponential kernel (Alg-GPe) and Matérn kernel (Alg-GPm) with ν = 1/2. In the continuous but nonsmooth Example 4, Alg-GPe still remains the best though Alg-GPm is almost as good. In the discontinuous Example 5, Alg-PC actually initially outperforms both GP-based algorithms though Alg-GPm eventually catches up.

CONCLUSIONS

We developed and numerically tested three algorithms (Alg-D, Alg-PC, and Alg-GP) for continuous pathplanning problems with unknown random termination/capture intensity. These algorithms follow a Bayesian approach to model the surveillance intensity K and then apply confidence bound techniques to tackle the exploration-exploitation dilemma. The GP-regression used in Alg-GP leverages the spatial correlations in K and usually results in more efficient learning from captures -particularly when the GP covariance kernel is chosen to reflect the smoothness of the actual K. While our experimental results are very promising, we do not currently have a proof of convergence and rigorous upper bound on the cumulative regret. We hope that the graph-theoretic UCB proofs (Azar et al., 2017) can be extended to cover edgecorrelations and ultimately to our continuous setting.

Several extensions would broaden the applicability of our approach. If we consider E's post-detection planning, the terminal cost will become spatially inhomogeneous (Andrews and Vladimirsky, 2014). Multiobjective control methods (Kumar and Vladimirsky, 2010) and various robust path planning techniques (Qi et al., 2021) will become relevant if the risk of detection is balanced against other optimization criteria (e.g., the profit from smuggling resources from a protected area (Arnold et al., 2019;Cartee and Vladimirsky, 2020;Chen et al., 2021)). We have focused on the isotropic dynamics primarily to simplify the exposition. Non-isotropic controlled dynamics lead to more general HJB PDEs, which can be similarly solved on a grid to approximate the value function efficiently (Sethian and Vladimirsky, 2001;Tsai et al., 2003;Alton and Mitchell, 2012;Mirebeau, 2014). The gradient of that value function can be then used to synthesize the optimal control. If K is viewed as changing in time, this will introduce an additional challenge of change point detection (Aminikhanghahi and Cook, 2017) in our RL algorithms. It will be also interesting to consider an antagonistic version, where K is chosen by surveillance authorities to maximize the probability of capture in response to E's path choices. A Nash equilibrium for this problem was already studied under the assumption that K is selected (perhaps probabilistically) from a finite list of options K 1 , ..., K r , all of which are known to E (Gilles and Vladimirsky, 2020;Cartee et al., 2019). We hope that it can be also extended to our setting where K i 's are learned online.

where N t e is how many times edge e is visited up until the t-th episode. Choosing = log(T |E|/γ)

N t e , we obtain P Ψt e -Ψ e ≥ log(T |E|/γ) N t e ≤ 2γ 2 T 2 |E| 2 . Applying Boole's inequality over all edges and all episodes, we obtain a union bound P   e∈E,t≤T Ct e -C e ≥ L log(T |E|/γ) N t e   ≤ e∈E,t≤T P Ct e -C e ≥ L log(T |E|/γ) N t e ≤ e∈E,t≤T P Ψt e -Ψ e ≥ log(T |E|/γ) N t e ≤ 2γ 2 T |E| . This equation measures the model error since it bounds the difference between the estimated cost with the true cost. With probability at least (1 -2γ 2 /T |E|), | Ct e -C e | ≤ L log(T |E|/γ) N t e for any edge and any episode. Along the t-th episode's path p t , triangle inequality yields e∈p t Ct e -e∈p t C e ≤ e∈p t Ct e -C e ≤ L log(T |E|/γ) e∈p t 1 N t e . We denote the last term as ∆ p t . As Ψt e -Ψt e ≤ log(T |E|/γ) N t e , using the Lipschitz condition of -log(1 -x) we obtain Ĉt e -Ce ≤ L log(T |E|/γ) N t e . Therefore, by triangle inequality we have e∈p t Ĉt e -e∈p t C e ≤ e∈p t Ĉt e -e∈p t Ct e + e∈p t Ct e -e∈p t C e ≤ 2∆ p t . We denote v p t the true total cost of p t (i.e., the sum of true edge costs C e along p t ) and vp t the total cost based on the modified cost Ĉe . Using v p t = e∈p t C e and vp t = e∈p t Ĉt e , we finally obtain P ∀t, |v p t -v p t | ≤ 2∆ p t ≥ 1 -2γ 2 T |E| . Notice that either Ĉt e = -log(1 -Ψ) ≤ C e or Ψt e = Ψt e -log(T |E|/γ) N t e ≤ Ψ e (hence Ĉt e ≤ C e ) with the probability of at

where the second inequality follows from the Ĉt e -optimality of p t while the first & third inequalities hold with probability of at least q.

Assuming that each path the algorithm considers has no more than M ≤ |E| edges, the expected cumulative regret can be bounded as

where C = -log(1 -Ψ).

Lemma 1. The first term in previous inequality satisfies

Proof. A different way to do the summation leads to

The first inequality is due to the Jensen's inequality while the second follows from the Cauchy-Schwartz inequality. The last one uses the fact that there are no more than M T visits to all the edges.

Theorem 1. Using Lemma 1, we can bound the averaged expected regret of our Alg-D on graph as

In particular, as T → ∞, the averaged expected regret converges to zero.

We note that the above bounds apply to a graph-constrained problem only. The graph-optimal capture probability (1 -exp[-v p * ]) might in principle be significantly larger than the W * = 1 -exp[-u(x 0 )] describing the minimized capture probability in the continuous domain Ω.

B HYPERPARAMETER TUNING

We conduct hyperparameter tuning (17) every thousand episodes by applying the constrained optimizer fmincon with gradients in MATLAB . Assume the log marginal likelihood in ( 17) is log Zob X ob , α, β , the α-gradient can be computed as

z ob,c and Σ are the same notations as defined in section 4.2. The expression of ∂ Σ ∂α depends on which kernel we choose. The β-gradient can be computed similarly.

C AVERAGED EXCESS RISK R

In this section, we define another path-related regret metric in addition to the excess rate of captures defined in (6). If y i (•) is the ith-episode path and J i is the corresponding cumulative intensity, the capture probability along y

The minimum capture probability is W * = 1 -exp(-u(x 0 )). The averaged excess risk is defined as

Unlike excess rate of captures which uses probabilistic outcomes, R compares directly the expected capture rate of episodic paths with the truly optimal W * . Unfortunately, UCT algorithm is not guaranteed to find a path reaching the boundary during each episode. As a result, W i cannot be computed and regret R is not applicable to UCT. The following are R results of Alg-D, Alg-PC and Alg-GP for all examples in this paper. D LEARNABLE LIMITS RESTRICTED BY DISCRETIZATIONS D.1 UCT and Alg-D

For graph algorithms UCT and Alg-D, the Evader selects paths only on the grid and is restricted to move only along eight fixed directions. As a result, even if we let the grid size approach zero, in the limit there is a gap between W * and the minimum capture rate that can be achieved on the grid. From the figure below we can observe, as the grid size decreases, the blue dots approach some level which is closer to the optimal (red line, original continuous case, computed on a h = 1/800 grid) but there remains a gap (≈ 0.014 when h = 1/640). Our numerical experiments use h = 1/20, in which case the best learnable limit is larger than the optimal capture probability by about 0.033. However, as we observe from Figure 2, after 15000 episodes the regret of Alg-D remains much larger than 0.033; i.e. the error due to this grid-restricted motion is not the reason why Alg-D shows such huge regrets. Using a smaller grid size can reduce this gap, but it also increases the number of parameters to be estimated. An overly fine grid takes more episodes to obtain accurate enough prediction of the capture rate, making it harder to observe its advantages. D.2 Alg-PC and Alg-GP We conduct an observation grid refinement study for Alg-PC using Example 2. The following figure shows the log of (non-averaged, instantaneous) differences between W i and W * in each episode, for different G resolutions. We observe that the lower (W i -W * ) values for 20 × 20 and 40 × 40 grids are much lower than for a 10 × 10 grid. This indicates that with a finer grid Alg-PC is able to explore paths which are closer to optimal. Our use of the discrete observational grid G essentially lumps together all captures within one cell. This limits the algorithm's ability to learn the true K. To account for this more accurately, we can modify our definition of regret metric and measure the regret relative to the best path learnable on the specific G. Below we provide additional tests illustrating this idea for Alg-PC and data showing that this subtlety is largely irrelevant for Alg-GP.

We define K * (x) to be the cell-averaged version of K. This piecewise-constant function also represents the best approximation of K that we could hope to attain with infinitely many captures in every cell.