Ehsan Ahvar
email: ehsan.ahvar@telecom-sudparis.eu

Antonio M Ortiz
email: antonio.ortiztorres@it-sudparis.eu

Noel Crespi
email: noel.crespi@mines-telecom.fr

Improving Decision-Making for Fuzzy Logic-based Routing in Wireless Sensor Networks

The task of routing data from a source node to the base station is a critical issue in Wireless Sensor Networks (WSNs). Fuzzy logic is the main proposal of a number of papers in the literature as an effective method for making decisions to transfer data towards the destination. Although fuzzy logic has a very important role in designing routing protocols for WSNs, identifying its fuzzy sets and defining best possible rules is a complex challenge. This paper introduces Improved-fuzzy logic (I-fuzzy), a simple and effective method that helps to address the weakness of fuzzy logic in terms of defining rules. The Ifuzzy method is tested in several scenarios by using GloMosim simulator and compared to a classic fuzzy logic approach and to a traditional minimum hop routing. The results show that the I-Fuzzy method outperforms the other approaches in terms of data delivery, energy conservation and load distribution.

I. INTRODUCTION

Wireless Sensor Networks (WSN) are usually comprised of battery-operated sensor devices capable of communication and processing [START_REF] Akyildiz | Wireless sensor networks: a survey[END_REF]. This type of networks can be used in a number of applications to monitor and analyze complex phenomena over a large region and for a long period of time [START_REF] Hof | Applications of sensor networks[END_REF]. The nodes that compose WSNs can collect physical values such as humidity, temperature, pressure, lighting, oxygen level, presence, etc. Their ability to obtain these values combined with the possibility of autonomous operation and wireless communication makes these networks particularly appealing in applications such as environmental monitoring, smart cities, home automation, smart agriculture, industrial control, health care, logistics, security, etc.

Node deployment, data collection and analysis are the three main stages that define the operation of a WSN. Issues such as node redundancy, node failure, path break or data loss must be addressed to ensure satisfactory performance. One of the most critical aspects that directly impacts the overall performance of WSNs is routing.

The task of routing data from a source to a destination is an important procedure for any network. An efficient routing protocol, in conjunction with effective medium access control, allows for correct operation of the network by ensuring that data will be delivered to the destination. Several objectives can be targeted to evaluate the efficiency of a routing proposal, e.g., end-to-end delay, energy efficiency and load balance, depending on the type of network. In WSNs, where nodes are constrained in terms of computing capabilities, memory, storage, and specially energy, an efficient routing approach contributes to balancing the network load, with the ultimate objectives of ensuring data delivery and extending the network's lifetime.

Several methods can be used to improve routing efficiency in WSNs, one such method is the creation of clusters i.e., groups of nodes commanded by one central node [START_REF] Abbasi | A survey on clustering algorithms for wireless sensor networks[END_REF], to reduce the number of transmissions. The consideration of several variables such as the number of hops, residual node energy levels, channel state, etc., is the main contribution of a number of proposals. The parameter that is used by many of these approaches is the number of hops [START_REF] Al-Karaki | Routing techniques in wireless sensor networks: a survey[END_REF], [START_REF] Perkins | Ad-hoc on-demand distance vector routing[END_REF], but considering multiple parameters usually offers even better performance [START_REF] Akkaya | A survey on routing protocols for wireless sensor networks[END_REF]. One method that has shown good results uses fuzzy logic to combine multiple parameters [START_REF] Liang | Energy and mobility aware geographical multipath routing for wireless sensor networks[END_REF], [START_REF] Srinivasan | A fuzzy, energyefficient scheme for data centric multipath routing in wireless sensor networks[END_REF].

Fuzzy Logic [START_REF] Reznik | Fuzzy controllers handbook: how to design them, how they work[END_REF] is a decision system approach that works similarly to human control logic. It is a useful technique since it uses human language to describe inputs and outputs, and provides a simple method for reaching a conclusion from imprecise, vague or ambiguous input information. Fuzzy-logic systems include a fuzzy-rule set to define the relationship between the input and output variables. Furthermore, just a few data samples can provide quite accurate results. The potential of fuzzy logic is being fully explored in a range of fields such as signal processing, speech recognition, aerospace, robotics, embedded controllers, networking and marketing [START_REF] Ghosh | A survey of recent advances in fuzzy logic in telecommunications networks and new challenges[END_REF]. This paper focuses on improving decision making in fuzzy logic for routing in WSNs. The main contribution of this paper is the proposal of an assistant module (AM) for fuzzy logic controllers in WSN routing. The AM is a simple and effective technique that computes an independent metric considering the same parameters as fuzzy logic. This method can significantly improve the performance obtained with traditional fuzzy logicbased decision making. Furthermore, a Decision Module is also proposed in order to select the best routes in WSN communications.

The rest of this paper is organized as follows. Section II depicts the related work. A general view regarding fuzzy logicbased routing is shown in Sec. III. The main contribution of this paper, the assistant module for fuzzy logic-based routing in WSNs is presented in Sec. IV. The experimental evaluation is detailed in Sec. V, where the proposed approach is compared to traditional fuzzy logic and minimum hop routing. Finally, Sec. VI presents the conclusions and exposes the future work.

II. RELATED WORK

There are a number of papers that use fuzzy logic to improve the performance of routing protocols for WSNs. The work in [START_REF] Baccour | A Fuzzy Link Quality Estimator for Wireless Sensor Networks[END_REF] presents a fuzzy link quality estimator that makes use of fuzzy logic to combine four link-quality properties: channel quality, stability, asymmetry and packet delivery. The evaluation of this proposal is focused on one-hop networks, and no information about multihop networks is given. The use of fuzzy logic to improve the LEACH protocol is proposed in [START_REF] Ran | Improving on LEACH Protocol of Wireless Sensor Networks Using Fuzzy Logic[END_REF]. Combining node density, residual energy and distance using fuzzy logic, the obtained results show that LEACH-FL improves decision making for cluster head selection. Experiments were carried out in a 20-node network; experiments with a higher number of nodes would be desirable to evaluate the scalability of their proposal.

Fuzzy logic has also been used to improve the efficiency of the Ad-hoc On-demand Distance Vector (AODV) protocol. The AODV-FL is presented in [START_REF] Ortiz | On reactive routing protocols in zigbee wireless sensor networks[END_REF], where fuzzy logic is used to evaluate nodes and limit the scope of message flooding, thereby efficiently reducing the network traffic and enabling the network to extend its lifetime. Minor changes in the network discovery procedure were also proposed with the aim of improving the performance of the route creation process. [START_REF] Haider | A fuzzy approach to energy optimized routing for wireless sensor networks[END_REF] a method based on fuzzy logic to optimize cluster-based routing protocols. They accurately define the operation of fuzzy logic-based systems for routing enhancement, but they neglect important parameters such as route depth and communication time in the experiments. These works reinforce using fuzzy logic as a useful technique to improve the performance of routing protocols.

Haider et al. propose in

The performance of fuzzy logic techniques can also be improved, with the aim of outperforming their initial advantages, thus enhancing even more the results obtained when they are employed. Two examples of fuzzy logic improvement techniques can be found in [START_REF] Alcalá | Improving fuzzy logic controllers obtained by experts: a case study in hvac systems[END_REF] and [START_REF] Larbes | Genetic algorithms optimized fuzzy logic control for the maximum power point tracking in photovoltaic system[END_REF].

Usually, the fuzzy rule set is defined by an expert in the field of interest who can link the facts with the conclusions. This procedure sometimes fails to obtain an optimal behavior when dealing with nontrivial problems. The work presented in [START_REF] Alcalá | Improving fuzzy logic controllers obtained by experts: a case study in hvac systems[END_REF] is focused on improving rule selection in fuzzy logic systems. They propose the use of two advanced tuning techniques (lateral and LA-tuning) combined with rule selection to improve on the fuzzy logic-based controllers obtained by experts in nontrivial problems. These tuning techniques are focused on the variation of the shape of the membership functions, and they improve global interaction by inducing better cooperation among the rules.

Genetic algorithms [START_REF] Goldberg | Genetic algorithms in search, optimization, and machine learning[END_REF] can also be used for the optimization of decision making techniques such as fuzzy logic. In [START_REF] Larbes | Genetic algorithms optimized fuzzy logic control for the maximum power point tracking in photovoltaic system[END_REF], a fuzzy logic controller is proposed to improve the maximum power point tracking in photovoltaic systems. This fuzzy controller is then assisted by genetic algorithms that obtain the best subsets of the membership functions with the aim of improving the performance of the fuzzy controller.

These last two techniques improve the membership functions in fuzzy logic-based controllers. Our proposed approach aims at enhancing fuzzy logic decision making by reevaluating fuzzy parameters in order to balance them, thereby increasing the efficiency of the routing mechanism.

III. FUZZY LOGIC-BASED ROUTING FOR WSNS

This section gives a brief introduction related to the general operating mechanism of fuzzy-based routing protocols.

A. General Mechanism

The operation of fuzzy logic-based protocols can be generally divided into two steps:

Network setup: Once the network has been deployed in the area where it is to operate, the base station transmits a broadcast packet. When a node receives this initial message, it checks whether it has an entry in its neighbor table for the node that transmitted the message. If not, the receiver node adds an entry that consists of the information received (i.e., neighbor address, hop count and energy level). The node then increments the hop count stored in the message and sets this hop count as its own hop count. It then retransmits the broadcast, but changes the message information to include its own (i.e., local node address, number of hops and residual energy level). Normally every node in the network retransmits the broadcast message once to all of its neighbors, but for accuracy, in case of a node receiving a broadcast message with a lower hop count than the stored one, it updates its hop count and broadcast the massage again. When this initial broadcast has been flooded through the network, each node knows its hop count and has the address, hop count and residual energy level of each of its neighbors. In this situation, every node in the network has now enough information to send and route messages towards the base station. The routes to be selected will depend on the metric used in each case (e.g., shortest path, fuzzy logic metric, etc.).

Data transfer: When a node observes an event, it should initiate a routing process to send data packets towards the base station. Traditional fuzzy logic-based routing protocols consider several metrics (i.e., hop count, energy level) and merge all these metrics into one single metric that is used to select the next hop. Data is then sent to the next hop until reaching the base station. The execution of these kind of mechanisms does not affect the overall network performance (in terms of processing time), what is more, it usually increases the network performance thanks to the load balance that is done when selecting the node with best state as next hop.

B. Fuzzy Logic Module

In order to improve routing performance in WSNs, fuzzy logic can be used as a metric that allows the combination of several parameters into one single metric. In this work, a traditional fuzzy logic system is used to estimate the best node to send data towards the base station. Later, in Sec. IV, a method to improve fuzzy logic performance is proposed.

The fuzzy logic module has the ability of combining several metrics into one single metric. For that, four stages are needed: fuzzification, rule evaluation, combination or aggregation of rules, and deffuzification (see Fig. 1). The input of the fuzzy logic module is usually a crisp value. To allow this value to be processed by the system, it has to be converted to natural language, that is, it has to be fuzzified. In this way, the fuzzifier method takes numeric values and turns them into fuzzy values which can be processed by the inference system. These fuzzy values represent the membership values of the input variables to the fuzzy sets.

Once values have been fuzzified, the inference system processes the fuzzy rules to get a fuzzy output. In the case of a fuzzy rule having more than one antecedent (conditional element), an AND (minimum) or OR (maximum) operator is used to estimate the output value of rule evaluation.

The third step is the aggregation of all outputs, where the outputs of each rule are combined to form a new fuzzy set.

Finally, at the deffuzification stage, the new aggregated fuzzy set is converted to a number. Our fuzzy logic module uses the centroid technique which determines the point where a vertical line divides the combined set into two equal parts. This deffuzification method is sensitive to all the rules [START_REF] Cox | Fuzzy fundamentals[END_REF] and it is easy to compute in the resource constrained WSN nodes.

The parameters considered in this work, that will be combined through fuzzy logic are: number of hops to the base station and residual energy level. The number of hops to the base station represents the number of times that a message must be forwarded to reach the base station and be further analized. The residual energy level in the nodes is a critical parameter in WSNs, where nodes are usually battery powered, and efficient energy saving and balance leads to an extension of the overall network lifetime. These parameters are used as an example to show the efficiency of the proposed technique. Other parameters such as channel properties or network congestion can be also used, just adapting fuzzy sets and rules.

The membership functions for the input and output parameters used in our fuzzy logic model are detailed in Fig. 2. Note that both parameters (number of hops and residual energy level) are represented with equivalent membership functions. This simplifies operations in the fuzzy logic engine and increases its efficiency when executed in the WSN nodes.

For example, considering the number of hops, label1 corresponds to low, label2 to medium and label3 to high. The values X0 to X4 have been adjusted according to each input variable. Continuing with the example of residual energy, X0 = 0, X1 = 25, X2 = 50, X3 = 75, and X4 = 100%, considering 100% when node batteries are fully charged. Also, input parameters are characterized into a set of linguistic values: Number of hops [low, medium, high], Energy Level [low, medium, high], and Output [low(bad), medium, good (high)]. Linguistic input values are related to output values following a set of rules that is defined by an expertise in the field [START_REF] Lee | Fuzzy logic in control systems: fuzzy logic controller. i. Systems[END_REF]. The FL system used in this papers follows the rules defined in Tab. I, that represents rules such as: IF Number of hops is high AND energy level is low THEN Output is good (high). When new values come to the fuzzy logic model, they are fuzzified to linguistic values, and correspondent rules are triggered. To calculate the final result, the output values are deffuzified to provide a numerical value that will be used as a metric during the routing process. According to our rule definition, the higher the value, the more appropriate the node is to be selected as next hop. In some occasions, fuzzy logic by itself does not provide the best result. This can happen due to several reasons:

label1 label2 label3 membership degree X 0 X 2 X 3 X 4 X 1
• Membership functions do not represent all the possible situations, specially in threshold values between two consecutive fuzzy sets.

• Rules defined by the expert do not adjust to the desired behavior, and produce output values that are not optimal. This is very common, since it is very difficult to know a priori the results that will be produced by the system when combining several rules.

• There is noisy input values that will produce an undesired output value.

To mitigate as much as possible these situations and with the aim of improving the FL system performance, next section presents the main contribution of this paper. An assistant module that is executed in parallel to the FL system. This assistant module computes an independent metric by considering the same parameters as fuzzy logic. In order to break possible ties and to decide the final output, a decision maker is used to decide which output value will be considered: the one provided by fuzzy logic, or the output of the assistant module.

IV. ASSISTANT MODULE FOR FUZZY LO-GIC BASED ROUTING

In this section, we introduce an Assistant Module (AM), a simple but effective technique that can significantly improve the performance obtained with traditional fuzzy logic methods.

When a node i has a packet to send, or it receives a packet to forward, the routing process is invoked. The Fuzzy Logic (FL) selects the ID of the next-hop, ID (F L) , based on the values stored in the neighbor table. In parallel, the AM with access to the neighbor table also selects the next-hop based on an alternative criterion, which can be denoted as ID (AM ) . A Decision Maker module (DM) then selects the next-hop that will be finally used.

The operation of the AM can be summarized as follows: when a node i has a packet to send or receives a packet to forward, the routing process begins by the AM computing a weight for each neighbor (i.e, neighbor j) based on the cost function described in [START_REF] Abbasi | A survey on clustering algorithms for wireless sensor networks[END_REF].

W ij (t) =        ωE j (t) 1 - H j (t) H max E j (t) <T hreshold> > 1 0 E j (t) <T hreshold> ≤ 1 (1)
where E j (t) is the energy level of neighbor j, ω is a control parameter that simply limits the energy factor ωE j (t) to the interval [0,1] ∀ j, and H max is the maximum number of hops reported among all the neighbors of node i. Note that the energy threshold in ( 1) is used to remove from the selection process those neighbors j whose energy level is very low. The rationale of using ( 1) is that, it produces a good balance between energy and the hop count in the form of a simple compound metric. Next, the AM selects the neighbor with highest evaluation value as a next hop and sends its ID to the decision maker.

The processing of the Decision Maker module is summarized in Alg. 1. If the selections made by the FL and AM modules matches, then the selected node will become the next-hop and data will be sent to it. Otherwise, the DM runs a basic sequence of tie-breaking rules until the next-hop is selected. The main contribution of this paper is to show how this combined selection outperforms any possible selection of the isolated fuzzy logic.

The use of the AM in conjunction with traditional fuzzy logic is called Improved-Fuzzy (I-Fuzzy). A performance evaluation of the proposed mechanism and comparison with

Algorithm 1: The Decision Maker the traditional fuzzy logic and minimum hop count methods is presented.

Inputs : {ID (F L) , E (F L) ID , H (F L) ID }, {ID (AM ) , E (AM ) ID , H (AM ) ID } Output: next-hop node 1 foreach packet to be forwarded do 2 if ID (F L) == ID (AM )

V. EVALUATION

This section presents a performance evaluation of the Improved-Fuzzy mechanism by comparing it to Fuzzy-based routing, and to Minimum Hop Routing (MHR) [START_REF] Chiang | A minimum hop routing protocol for home security systems using wireless sensor networks[END_REF] as a basic routing protocol. The GloMoSim simulator developed by UCLA [START_REF] Zeng | Glomosim: a library for parallel simulation of large-scale wireless networks[END_REF] was used to realize the simulations. The simulation model and the results obtained are described below.

A. Simulation Model

The simulation surface considered was 500 m × 500 m. The radio range was set to 50 m, with an available bandwidth of 2 Mbps, a radio transmission(TX) power of -7.0 dBm, and packet size is 512 bits. Each simulation had a 150-minute duration, and the tests were run under various conditions, such as with different numbers of nodes, namely, 800, 900, and 1000 nodes, and with 10 different seeds. During simulation, a sensor is randomly selected every 10 seconds, which initiates a packet transmission to one of its neighbors towards the base station S. Moreover, node placements in the terrain were selected randomly. It is worth mentioning that, even though the placement and initial energy of the nodes were set randomly, once those factors were set, they remained fixed for rest of the trials to obtain comparable results across experiments.

The simulation model comprises two different scenarios:

Scenario I-In this scenario, we assume a critical situation, where the energy levels for transmission mode are very low (i.e. 0.00005 W). Under these conditions, we evaluate the different routing schemes considering three different tests:

Test 1: Time until the first path is broken-When a node wants to send/forward a data packet but no alive neighbors are available, it leads to a path break. This test is one of the indicators of the effectiveness of routing schemes in terms of energy management and traffic balance.

Test 2: Number of broken paths-This test computes the total number of paths that fail for each routing scheme during a simulation period of 150 minutes.

Test 3: Number of node failures at the end of the simulation-This test computes the total number of nodes that fail for each routing scheme during a simulation period of 150 minutes.

Test 4: Percentage of packet deliveries at the end of the simulation-The efficiency of packet delivery is another important factor for determining protocol quality. Scenario II-In this scenario, the nodes' energy level is set sufficiently high so as to avoid experiencing node failures during the simulation runtime. Our goal in this case is to compare the fairness in terms of path distribution and energy consumption. In order to avoid bias in the comparison, we ensure that all the routing schemes transmit the same amount of data, and that this occurs without node failures. We carry out two tests to examine how the routing schemes save and manage energy in regular operation mode.

B. Simulation Results

1) Scenario I: In case of no live neighbor available to be selected as a next hop, a path broke occurs. Fig. 3(a) details the outcome of Test 1 (i.e., the time elapsed until the first path is broken). These results provide a first indication of the performances obtained with the different routing schemes under evaluation, since once that path break happens, new routes must be selected, and data loss occurs. It can be observed that the first path failures are relatively similar for the basic fuzzy and MHR methods. As indicated in Fig. 3(a), when using the Assistant Module, the first path fails only after ∼ 80 to ∼ 100 minutes depending on the number of nodes present in the network. These results show that the use of I-Fuzzy provides an improved load balancing among network nodes, allowing them to use all the possible data paths for longer than is possible with the other approaches.

As time goes by, more paths are broken. Figure 3(b) shows the number of path breaks after 150 minutes for all the approaches. The best performance for this test is achieved by the I-Fuzzy method, outperforming the other approaches thanks to its better network load distribution. It is worth mentioning that as the number of nodes grows, the amount of broken paths decreases, since more nodes are available, and thus more paths can be selected.

During network operation, it is desirable that all nodes or at least as many as possible, are available to be selected as next hops and thus ensuring correct packet routing. When nodes run out of energy, they start to fail, and the overall network performance is at risk. Fig. 3(c) shows the number of node failures observed in the experiments. It can be observed that the number of nodes that fail for the I-Fuzzy scheme much less than in the other approaches. Just as with the number of broken paths, as the network size increases, more nodes are available to be selected as next hops, providing for better load balancing and enabling nodes to stay alive longer. Fig. 3(d) shows the percentage of successful packet deliveries after 150 minutes for all the approaches. Again, the best results for this test are for the I-Fuzzy approach, thanks to the load balance and better decision making performed by this technique. It is worth mentioning that as the number of network nodes grows, packet delivery increases for all the approaches, due to the higher number of available paths in the network.

2) Scenario II: This second scenario is designed to evaluate the load distribution and fairness in terms of packet transfer. As mentioned earlier, in this case the batteries are not in a critical state, and thus, we can examine the regular behavior of the different routing schemes normal situations.

How the load is distributed among network nodes will directly impact the overall network performance, as will the amount of energy available in the nodes. The nodes located close to the base station (i.e., the base station neighbors) are critical, since all the information coming from the rest of the network will have to be forwarded by them in order to reach the base station. How the energy is distributed among these nodes is an indicator of the likely node and path failures, and the consequent risk of network disconnection and data loss.

The variance of the remaining energy levels of the base station neighbor nodes is shown in Fig. 3(e). The lower the variance is, the better the load has been distributed, and the better the overall performance. I-Fuzzy and simple Fuzzy approaches achieve better results compared to the MHR method, indicating that a fairer distribution of energy consumption has been achieved. The use of MHR ensures shorter routes, but does not consider load balance, and so nodes in the most-used routes are quickly exhausted causing path break and data loss faster than in the other approaches.

To conclude, Fig. 3(f) shows the breakdown of the decisions made by the Decision Maker, indicating the fractions when the selection coincides with the one made by Assistant Module (AM) as well as the fraction where both methods (fuzzy logic and AM) agree in their next hop selection. The results exposed in Fig. 3(f) show that the AM has an important role in making decision and improving the quality of fuzzy logic decisions as it corrected close to 50 percent of the fuzzy logic decisions.

VI. CONCLUSIONS

Routing is one of the most critical stages in WSNs operation. The correct selection of the next hop directly affects the overall network performance in terms of network congestion, end-to-end delay and energy consumption.

Several techniques have been proposed in the literature to increase the efficiency of routing in WSNs, but most of them have something in common: consider one or several parameters to evaluate the current state of network nodes as a base to make decisions.

Fuzzy logic is a decision making technique that is able to combine several parameters into one single metric and that has shown good performance for the improvement of routing performance in WSNs. Despite of these improvements,some issues can arise, and fuzzy logic can be improved upon. This paper has proposed a simple and effective solution that can work in combination with fuzzy logic, called the Improved-Fuzzy method. This solution is composed of an Assistant Module that computes an independent metric by considering the same parameters as fuzzy logic. A Decision Module has been also proposed to decide which output value will be selected: the one provided by the fuzzy logic module, or the output of the Assistant Module, the I-Fuzzy approach.

The experimental evaluation shows that I-Fuzzy outperforms traditional fuzzy logic decision making. Furthermore, a minimum hop routing approach has also been considered in the experiments in order to show a fair comparison with a classic routing approach.

Fig. 1 .

 1 Fig. 1. Fuzzy logic module operation.

Fig. 2 .

 2 Fig. 2. Membership function.

  then

3 send the packet to the selected neighbor; 4 / 6 choose 8 choose

 3468 ID(LA) as the next-hop; ID (AM ) as the next-hop; 9 else choose the one with the highest energy;

Test 5 :

 5 Variance in the remaining energy levels of the neighbors of base station S-This test makes it possible to see Time until the first path is broken. Number of nodes that fail due to energy run out. Variance of the remaining energy for the base station neighbor nodes. Effect of the Assistant Module in decision making.

Fig. 3 .

 3 Fig. 3. Simulation Results. which routing scheme is best at performing energy balancing among the nodes closest to the base station. Test 6: Effect of AM on Fuzzy decisions-To understand the role of the Assistant Module in fuzzy decisions, this test analyzes the impact of AM decisions in the selection of the next hop.

TABLE I

 I

	.	FUZZY RULE BASE
	Energy level	Number of hops	Output
	Low	Low	Medium
	Low	Medium	Low
	Low	High	Low
	Medium	Low	Medium
	Medium	Medium	Medium
	Medium	High	Low
	High	Low	High
	High	Medium	Medium
	High	High	Low

ACKNOWLEDGEMENTS

This work was supported by the EU ITEA 2 Project: 11012, "ICARE: Innovative Cloud Architecture for Real Entertainment".


Bruno Bouchard
email: bouchard@ceremade.dauphine.fr.

Marcel Nutz
email: mnutz@columbia.edu.

Stochastic Target Games and Dynamic Programming via Regularized Viscosity Solutions *

Keywords: Stochastic target, Stochastic differential game, Knightian uncertainty, Shaking of coefficients, Viscosity solution AMS 2000 Subject Classification 93E20, 49L20, 91B28

We study a class of stochastic target games where one player tries to find a strategy such that the state process almost-surely reaches a given target, no matter which action is chosen by the opponent. Our main result is a geometric dynamic programming principle which allows us to characterize the value function as the viscosity solution of a non-linear partial differential equation. Because abstract measurable selection arguments cannot be used in this context, the main obstacle is the construction of measurable almost-optimal strategies. We propose a novel approach where smooth supersolutions are used to define almost-optimal strategies of Markovian type, similarly as in verification arguments for classical solutions of Hamilton-Jacobi-Bellman equations. The smooth supersolutions are constructed by an extension of Krylov's method of shaken coefficients. We apply our results to a problem of option pricing under model uncertainty with different interest rates for borrowing and lending.

Introduction

We study a stochastic (semi) game where we try to find a strategy u such that the controlled state process almost-surely reaches a given target at the time horizon T , no matter which control α is chosen by the adverse player. Here α is any predictable process with values in a given bounded set A ⊂ R d , whereas u is a non-anticipating strategy which associates to each α a predictable process u [α] with values in a given set U ⊂ R d . More precisely, if A and U denote the collections of predictable processes with values in A and U , respectively, then u is a map

A → U such that u[α]| [0,s] = u[α ′ ]| [0,s] on the set {α| [0,s] = α ′ | [0,s]
}, for all α, α ′ ∈ A and s ≤ T . We denote by U the collection of all such strategies.

Given an initial condition (x, y) ∈ R d × R at time t and (u, α) ∈ U × A, the (d + 1)-dimensional state process (X α t,x , Y u,α t,x,y )(s), t ≤ s ≤ T is defined as the solution of the stochastic differential equation dX(s) = µ X (s, X(s), α s )ds + σ X (s, X(s), α s )dW s , dY (s) = µ Y (s, X(s), Y (s), u[α] s , α s )ds + σ Y (s, X(s), Y (s), u[α] s , α s )dW s , where W is a Brownian motion and the coefficients satisfy suitable continuity and growth conditions. Given a measurable function g, the value function of the stochastic target game is then given by v(t, x) = inf y ∈ R : ∃ u ∈ U s.t. Y u,α t,x,y (T ) ≥ g(X α t,x (T )) a.s. ∀ α ∈ A .

(

That is, v(t, x) is the smallest y from which we can drive the state process into the epigraph of g by using a strategy u to react to the adverse player. The aim of this paper is to provide a dynamic programming principle for the stochastic target game and to characterize v in terms of a Hamilton-Jacobi-Bellman equation.

In the case where A is a singleton and u is a control, the above is a standard stochastic target problem in the terminology of [START_REF] Soner | Dynamic programming for stochastic target problems and geometric flows[END_REF][START_REF] Soner | Stochastic target problems, dynamic programming, and viscosity solutions[END_REF]. In [START_REF] Soner | Dynamic programming for stochastic target problems and geometric flows[END_REF], it is shown that the value function of this target problem satisfies a geometric dynamic programming principle (GDP) and, consequently, is a discontinuous viscosity solution of an associated Hamilton-Jacobi-Bellman equation. The GDP consists of two parts, called GDP1 and GDP2. Roughly, given a family {θ u , u ∈ U} of stopping times with values in [t, T ], GDP1 states that if y > v(t, x), then there exists u ∈ U such hat Y u,a t,y (θ u ) ≥ v(θ u , X a t,x (θ u )), and conversely, GDP2 states that if there exists u ∈ U such that Y u,a t,y (θ u ) > v(θ u , X a t,x (θ u )), then y ≥ v(t, x).

The line of argument for GDP1 can be reproduced in the context of games. However, all previous proofs of GDP2 crucially rely on the construction of almost optimal controls through measurable selections. It is well known that in the context of games, when u is a strategy as defined above, the possibility of using such a selection is a completely open problem. The main difficulties come from the lack of separability in the space U of strategies and the irregular dependence on the adverse control α.

For zero-sum differential games in standard form, see e.g. [START_REF] Fleming | On the existence of value functions of two-player, zero-sum stochastic differential games[END_REF] and [START_REF] Buckdahn | Stochastic differential games and viscosity solutions of Hamilton-Jacobi-Bellman-Isaacs equations[END_REF], there are by now several workarounds for this problem; they rely on approximations and exploit the continuity properties of the cost functions. We also refer to [START_REF] Pham | Two person zero-sum game in weak formulation and path dependent Bellman-Isaacs equation[END_REF] and [START_REF] Sirbu | Stochastic Perron's method and elementary strategies for zero-sum differential games[END_REF] for recent developments in different directions, in a setting where both players use controls. In [START_REF] Bouchard | Stochastic target games with controlled loss[END_REF], stochastic target games were analyzed when the target is of controlled-loss type; that is, of the form E ℓ(X u,α t,x,y (T ), Y u,α t,x,y (T )) ≥ m, where m is given and the loss function ℓ has certain continuity properties. Again, the regularity of ℓ was exploited to circumvent the problem of measurable selection. By contrast, the almost-sure target of the game under consideration is highly discontinuous, which has prevented us from arguing similarly as in the mentioned works.

In this paper, we follow a completely different and novel idea. As a starting point, recall that in the context of standard control problems with a smooth value function, we can sometimes use a verification argument. Here, an optimal control of Markovian (i.e. feedback) type is defined explicitly in terms of the derivatives of the value function. It plays the role of the almost-optimal controls mentioned above and renders measurable selection arguments unnecessary. Of course, this procedure requires a smooth value function, which cannot be expected in our context. However, it will turn out that a smooth supersolution with specific properties can be used in a similar spirit. The outline of our argument runs as follows.

(a) Show that the value function v satisfies a version of GDP1 above (Theorem 2.3).

(b) Deduce from GDP1 that v is a viscosity supersolution of the associated Hamilton-Jacobi-Bellman equation (Theorem 2.5).

(c) Regularize v to find a smooth supersolution w which is close to v is a specific sense (Lemma 2.6).

(d) Using w, construct a strategy of Markovian type that matches the criterion in (1.1) when starting slightly above v(t, x) and use this strategy to prove a version of GDP2 (Theorem 2.7).

(e) Deduce from GDP2 that v is also a viscosity subsolution of the Hamilton-Jacobi-Bellman equation (Theorem 2.8).

The arguments for (a) and (b) are along the lines of [START_REF] Soner | Dynamic programming for stochastic target problems and geometric flows[END_REF], while at least part of the proof of (e) follows [START_REF] Bouchard | Stochastic target games with controlled loss[END_REF]. The construction of the smooth supersolution in (c) is based on Krylov's method of shaking the coefficients from [15, Theorem 2.1] (see also [START_REF] Barles | On the convergence rate of approximation schemes for Hamilton-Jacobi-Bellman equations[END_REF]), which we extend here to semi-linear equations by considering value functions of controlled forward-backward stochastic differential equations (Theorem 3.3). We mention that this method imposes a concavity condition on one of the operators.

On the other hand, to the best of our knowledge, our result is the first proof of dynamic programming for stochastic target games with almost-sure target. 1Our results can be compared to the second order backward stochastic differential equations of [START_REF] Soner | Wellposedness of second order backward SDEs[END_REF], where the authors use quasi-sure analysis in the "weak formulation". Their setting is more general in the sense that path-dependence is allowed and concavity is not needed. On the other hand, we allow nonlinear dynamics for X, while their setting corresponds to the case where σ X (•, a) = a and µ X = 0.

We apply our results to a problem from mathematical finance where an option is to be super-hedged under model uncertainty. The model uncertainty is addressed in a worst-case fashion, so that it can be modeled by an adverse player as above. More precisely, the drift and volatility of the underlying of the option as well as the two interest rates for borrowing and lending depend on the adverse control α. Various incarnations of the super-hedging problem have been considered in the recent literature; see [START_REF] Avellaneda | Pricing and hedging derivative securities in markets with uncertain volatilities[END_REF][START_REF] Bouchard | Arbitrage and duality in nondominated discretetime models[END_REF][START_REF] Denis | A theoretical framework for the pricing of contingent claims in the presence of model uncertainty[END_REF][START_REF] Neufeld | Superreplication under volatility uncertainty for measurable claims[END_REF][START_REF] Peng | Nonlinear expectations and stochastic calculus under uncertainty[END_REF][START_REF] Soner | Martingale representation theorem for the G-expectation[END_REF][START_REF] Soner | Dual formulation of second order target problems[END_REF] and the references therein. The now standard approach is to use the weak formulation where the uncertainty is modeled by a non-dominated set P of possible laws on path space. The super-hedging property is then required to hold almost-surely under each element of P and the study involves the difficulty of dealing with a non-dominated set of probabilities (quasi-sure analysis). We adopt here a different point of view, where uncertainty is modeled as a game under a single probability measure; namely, the adverse player ("nature") chooses drift and volatility while we can react by using a suitable non-anticipating strategy and the superhedging-property is required to hold almostsurely for any control of the adverse player. Our formulation is thus in the spirit of [START_REF] Talay | Worst case model risk management[END_REF] and [START_REF] Tevzadze | Robust utility maximization for a diffusion market model with misspecified coefficients[END_REF] where problems of portfolio management are phrased as stochastic differential games of standard form in the framework of [START_REF] Fleming | On the existence of value functions of two-player, zero-sum stochastic differential games[END_REF].

The remainder of this paper is organized as follows. In Section 2, we formulate the stochastic target game in detail and provide the geometric dynamic programming principle together with the Hamilton-Jacobi-Bellman equation for the value function v. The key part of the dynamic programming principle, GDP2, is based on the regularization result, which is developed in Section 3 in a slightly more general setting. In Section 4, we exemplify our results by the application to super-hedging under model uncertainty.

Geometric dynamic programming for stochastic target games

In this section, we first detail our problem formulation. In the second subsection, we provide the first part of the geometric dynamic programming principle, GDP1, and infer the supersolution property of the value function. In the third subsection, we prove the difficult part, GDP2, together with the subsolution property.

Problem formulation

Fix a time horizon T > 0, let Ω be the space of continuous functions ω : [0, T ] → R d and let P be the Wiener measure on Ω. Moreover, let W be the canonical process on Ω, defined by W t (ω) = ω t . We denote by F = (F s ) 0≤s≤T the augmented filtration generated by W . Furthermore, for 0 ≤ t ≤ T , we denote by F t = (F t s ) 0≤s≤T the augmented filtration generated by (W s -W t ) s≥t ; by convention, F t s is trivial for s ≤ t. We denote by U t (resp. A t ) the collection of all F t -predictable processes in L p (P ⊗ dt) with values in a given Borel subset U (resp. bounded closed subset A) of R d , where p ≥ 2 is fixed throughout. Finally, let

D := [0, T ] × R d , D <T := [0, T ) × R d , D T := {T } × R d . Given (t, x, y) ∈ D × R and (ν, α) ∈ U t × A t , we let (X α t,x , Y ν,α t,x,y )(s), t ≤ s ≤ T be the unique strong solution of dX(s) = µ X (s, X(s), α s )ds + σ X (s, X(s), α s )dW s , dY (s) = µ Y (s, X(s), Y (s), ν s , α s )ds + σ Y (s, X(s), Y (s), ν s , α s )dW s (2.1)
with initial data (X(t), Y (t)) = (x, y). The coefficients µ X , µ Y , σ Y and σ X are supposed to be continuous in all variables, uniformly in the last one, and take values in R d , R, R d and M d := R d×d , respectively. (Elements of R d as viewed as column vectors). We assume throughout that there exists K > 0 such that

|µ X (•, x, •) -µ X (•, x ′ , •)| + |σ X (•, x, •) -σ X (•, x ′ , •)| ≤ K|x -x ′ |, |µ X (•, x, •)| + |σ X (•, x, •)| ≤ K, |µ Y (•, y, •) -µ Y (•, y ′ , •)| + |σ Y (•, y, •) -σ Y (•, y ′ , •)| ≤ K|y -y ′ |, |µ Y (•, y, u, •)| + |σ Y (•, y, u, •)| ≤ K(1 + |u| + |y|) (2.2)
for all (x, y), (x ′ , y ′ ) ∈ R d × R and u ∈ U . In particular, this ensures that the SDE (2.1) is well-posed. Moreover, we can note that the solution is in fact adapted not only to F but also to F t .

Remark 2.1. For simplicity, we consider the above dynamics for any initial point x ∈ R d . The case where X α t,x is restricted to an open domain O ⊂ R d will be discussed in Remark 3.4 below.

For the derivation of the viscosity supersolution property, we shall also impose a condition on the growth of µ Y relative to σ Y :

sup u∈U |µ Y (•, u, •)| 1 + |σ Y (•, u, •)| is locally bounded. (2.3)
Let t ≤ T . We say that a map u :

A t → U t , α → u[α] is a t-admissible strategy if it is non-anticipating in the sense that {ω ∈ Ω : α(ω)| [t,s] = α ′ (ω)| [t,s] } ⊂ {ω ∈ Ω : u[α](ω)| [t,s] = u[α ′ ](ω)| [t,
v(t, x) := inf y ∈ R : ∃ u ∈ U t s.t. Y u,α t,x,y (T ) ≥ g(X α t,x (T )) a.s. ∀ α ∈ A t (2.5)
for (t, x) ∈ D. We shall assume throughout that g is bounded and Lipschitz continuous on R d , and v is bounded on D.

(2.6)

Remark 2.2. The condition that v is bounded has to be checked on a case-by-case basis. One typical example in which v + is bounded is when there exists u such that σ Y (•, u, •) = 0. Then, the condition (2.2) on µ Y implies that v + is bounded by e KT (KT + sup R d g). A simple situation in which v -is bounded is when σ -1 Y µ Y is bounded. Then, an obvious change of measure argument allows to turn Y u,α t,x,y into a martingale, for (u, α) given, which implies that v ≥ inf R d g. See also Section 4.

First part of the dynamic programming principle and supersolution property

We first provide one side of the geometric dynamic programming principle, GDP1, for the value function v of (2.5). We denote by v * the lower-semicontinuous envelope of v on D.

Theorem 2.3 (GDP1). Let (t, x, y) ∈ D × R and let {θ u,α , (u, α) ∈ U t × A t } be a family of F t -stopping times with values in [t, T ]. Assume that y > v(t, x). Then, there exists u ∈ U t such that

Y u,α t,x,y (θ u,α ) ≥ v * (θ u,α , X α t,x (θ u,α )) a.s. ∀ α ∈ A t .
Proof. The ingredients of the proof are essentially known, so we confine ourselves to a sketch. As y > v(t, x), the definition of v shows that there exists u ∈ U t satisfying Y u,α t,x,y (T ) ≥ g(X α t,x (T )) a.s. ∀ α ∈ A t .

(2.7)

Step 1. We first consider the case where θ u,α ≡ s ∈ [t, T ] is a deterministic time independent of u, α. To be able to write processes as functionals of the canonical process, we pass to the raw filtration. More precisely, Ft denotes the raw filtration generated by

(W s -W t ) t≤s≤T , extended trivially to [0, T ]. By [10, Appendix I, Lemma 7], we can find for each α ∈ A t an Ft -predictable process ū[α] which is indis- tinguishable from u[α]. The map α ∈ A t → ū[α]
still satisfies the non-anticipativity condition (2.4) and therefore defines an element of U t . Moreover, (2.7) still holds if we replace u by ū:

Y ū,α t,x,y (T ) ≥ g(X α t,x (T )) a.s. ∀ α ∈ A t . (2.8)
We claim that it suffices to show that

Y u, ᾱ t,x,y (s) ≥ v * (s, X ᾱ t,x (s)) a.s. for all ᾱ ∈ Āt , (2.9)
where Āt is the set of all Ft -predictable processes with values in A. Indeed, if α ∈ A t , then by [10, Appendix I, Lemma 7] we can find ᾱ ∈ Āt such that α and ᾱ are indistinguishable. In view of the non-anticipativity condition (2.4), u[α] and u[ᾱ] are also indistinguishable, and then (2.9) implies that the same inequality holds for α; that is, (2.9) extends from Āt to A t . To prove (2.9), fix ᾱ ∈ Āt . For given ω ∈ Ω, we define

ūω : (ω, α) ∈ Ω × A s → ū[ᾱ(ω) ⊕ s α](ω ⊕ s (ω -ωs + ω s )),
where we use the notation

γ ⊕ s γ ′ := γ1 [0,s] + 1 (s,T ] γ ′ .
We observe that ūω ∈ U s . Using (2.8) and the flow property of the SDE (2.1), we can find a nullset N (depending on ᾱ) such that for all ω / ∈ N and all α ∈ A s ,

Y ūω , α s,x ′ (ω),y ′ (ω) (T ) ≥ g X α s,x ′ (ω) (T ) a.s., where x ′ (ω) := X ᾱ t,x (s)(ω) and y ′ (ω) := Y ū, ᾱ t,x,y (s)(ω). By the definition of v, this means that y ′ (ω) ≥ v(s, x ′ (ω)) or Y ū, ᾱ t,x,y (s)(ω) ≥ v(s, X ᾱ t,x (s)(ω)) ∀ ω / ∈ N. Since Y ū, ᾱ t,x,y (s) = Y u, ᾱ t,
x,y (s) a.s. and v ≥ v * , this shows that (2.9) holds.

Step 2. To deduce the case of a general family {θ u,α , (u, α) ∈ U t × A t } from

Step 1, we approximate each θ u,α from the right by stopping times with finitely many values and use the lower-semicontinuity of v * and the right-continuity of the paths of the state process. See e.g. [6, Section 2.3, Step 4] for a very similar argument.

We shall prove the supersolution property under the two subsequent conditions. A more general framework could be considered here (see e.g. [START_REF] Bouchard | Stochastic target problems with controlled loss[END_REF] or [START_REF] Bouchard | Stochastic target games with controlled loss[END_REF]), but we shall anyway need these conditions for the second part of the dynamic programming principle below. Given (t, x, y, z, a)

∈ D × R × R d × A, define the set N (t, x, y, z, a) := {u ∈ U : σ Y (t, x, y, u, a) = z}.
The first condition is that u → σ Y (t, x, y, u, a) is invertible, and more precisely:

Assumption (A). There exists a measurable map û : D × R × R d × A → U such that N = {û}. Moreover, the map û(•, a) is continuous for each a ∈ A.
The second assumption is for the boundary condition at time T .

Assumption (B). Fix a ∈ A and (x, y) ∈ R d × R. If there exist a sequence (t n , x n , y n ) ∈ D <T × R such that (t n , x n , y n ) → (T, x, y) and a sequence u n ∈ U tn such that Y un,a
tn,xn,yn (T ) ≥ g(X a tn,xn (T )) a.s. for all n ≥ 1, then y ≥ g(x).

Remark 2.4. It follows from (2.2) and (2.6) that g(X a tn,xn (T )) → g(x) a.s. for n → ∞. If U is bounded, then similarly Y un,a tn,xn,yn (T ) → y and we infer that Assumption (B) holds. In the applications we have in mind, the assumption is satisfied even when U is unbounded; see the proof of Corollary 4.1 below.

To state the supersolution property, let us define for (t, x, y, q, p, M )

∈ D × R × R × R d × M d the operators L a (t, x, y, q, p, M ) := µ û Y (t, x, y, σ X (t, x, a)p, a) -q -µ X (t, x, a) ⊤ p - 1 2 [σ X σ ⊤ X (t, x, a)M ] and L := min a∈A L a , where µ û Y (t, x, y, z, a) := µ Y (t, x, y, û(t, x, y, z, a), a), z ∈ R d .
Theorem 2.5. Let Assumptions (A) and (B) hold. Then, the function v * is a bounded viscosity supersolution of

L(•, ϕ, ∂ t ϕ, Dϕ, D 2 ϕ) = 0 on D <T ϕ -g = 0 on D T . (2.10)
Proof. Now that GDP1 has already been established, the argument is similar to [5, Section 5.1] and [6, Theorem 3.4, Step 1]. We sketch the proof for completeness.

Step 1. We start with the boundary condition, which is in fact an immediate consequence of Assumption (B).

Let (t n , x n ) → (T, x) be such that v * (t n , x n ) → v * (T, x), for some x ∈ R d . Set y n := v(t n , x n ) + n -1 . Then, we can find u n ∈ U tn such that Y un,a
tn,xn,yn (T ) ≥ g(X a tn,xn (T )) a.s. for all a ∈ A. Sending n → ∞ and using Assumption (B) yields v * (T, x) ≥ g(x) as desired.

Step 2. We now prove that v * is a viscosity supersolution of (2.10) on D <T . Let ϕ be a smooth function and let

(t o , x o ) ∈ D <T be such that min D<T (strict)(v * -ϕ) = (v * -ϕ)(t o , x o ) = 0;
(2.11)

we have to show that L(•, ϕ, ∂ t ϕ, Dϕ, D 2 ϕ)(t o , x o ) ≥ 0.
Suppose to the contrary that we can find a o ∈ A such that

L uo,ao (•, ϕ, ∂ t ϕ, Dϕ, D 2 ϕ)(t o , x o ) < 0,
where

u o := û(•, ϕ, σ X (•, a o )Dϕ, a o )(t o , x o ) and L u,a (t, x, y, q, p, M ) := µ Y (t, x, y, u, a) -q -µ X (t, x, a) ⊤ p - 1 2 [σ X σ ⊤ X (t, x, a)M ].
The continuity of û, cf. Assumption (A), implies that for all ε > 0, we can find

δ > 0 such that |u -u o | ≤ ε whenever u ∈ U is such that |σ Y (t, x, y, u, a o ) -σ X (t, x, a o )Dϕ(t, x)| ≤ δ for some (t, x, y) ∈ D × R satisfying |(t,
Y (s ∧ θ) ≥ v * (s ∧ θ, X(s ∧ θ)) a.s. ∀ s ≥ t, (2.14)
where we abbreviate (X, Y ) := (X ao t,x , Y u,ao t,x,y ) and θ is the stopping time

θ := θ 1 ∧ θ 2 , θ 1 is the first exit time of (•, X) from B
∆(s) := Y (s ∧ θ) -ϕ(s ∧ θ, X(s ∧ θ)) ≥ (ζ ∧ δ)1 [[θ,T ]] (s) a.s. ∀ s ≥ t. (2.15)
We now use (2.12) to obtain a contradiction to (2.15). To this end, set

λ := σ Y (•, X, Y, u[a o ], a o ) -σ X (•, X, a o )Dϕ(•, X), β := L u[ao]•,ao (•, Y, ∂ t ϕ, Dϕ, D 2 ϕ)(•, X) |λ| -2 λ1 {|λ|≥δ} .
It follows from the definition of θ and our regularity and relative growth conditions (2.2) and (2.3)2 that β is uniformly bounded on [[t, θ]]. This ensures that the (positive) exponential local martingale M defined by the stochastic differential equation

M (•) = 1 - •∧θ t M (s)β ⊤ s dW s
is a true martingale. Recalling (2.12), an application of Itô's formula shows that M ∆ is a local super-martingale. By the definition of θ ≤ θ 2 , this process is bounded by the martingale M δ, and is therefore a super-martingale. In particular, (2.15) implies that

y -ϕ(t, x) = ∆(t) ≥ E [M (θ)∆(θ)] ≥ E [M (θ)(ζ ∧ δ)] = ζ ∧ δ.
The required contradiction is obtained by choosing ε := (ζ ∧ δ)/2 in (2.13).

Second part of the dynamic programming principle and subsolution property

We now turn to the second part of the geometric dynamic programming, GDP2, and thus to the main contribution of this paper. As already mentioned in the Introduction, we cannot rely on an abstract measurable selection argument as in [START_REF] Soner | Dynamic programming for stochastic target problems and geometric flows[END_REF]. Instead, we construct an almost optimal Markovian strategy that will play the role of a measurable selector in the proof of Theorem 2.7 below. This strategy is defined in (2.16) in terms of a smooth supersolution w of (2.10) having specific properties. The existence of w will be proved in Section 3 by considering a family of controlled forward-backward stochastic differential equations and using the regularization technique of [START_REF] Krylov | On the rate of convergence of finite-difference approximations for Bellman's equations with variable coefficients[END_REF]. The arguments in Section 3 require existence and stability properties for the forward-backward stochastic differential equations, which hold under the following condition.

Assumption (C). The map (t, x, y, z)

∈ D × R × R d → µ û Y (t,
x, y, z, a) is continuous and uniformly Lipschitz in (x, y, z), uniformly in a ∈ A, and (y,

z) ∈ R × R d → µ û Y (t, x, y, z, a) has linear growth, uniformly in (t, x, a) ∈ D × A.
We also assume that the comparison principle holds for (2.10); see e.g. [START_REF] Crandall | User's guide to viscosity solutions of second order partial differential equations[END_REF] for sufficient conditions. Assumption (D). Let w (resp. w) be a lower-semicontinuous (resp. upper-semicontinuous) bounded viscosity supersolution (resp. subsolution) of (2.10). Then, w ≥ w on D.

As in [START_REF] Krylov | On the rate of convergence of finite-difference approximations for Bellman's equations with variable coefficients[END_REF], the regularization procedure also requires a concavity property for the operator L a .

Assumption (E). For all (t, x, a) ∈ D × A, (y, p) ∈ R × R d → L a (t, x, y, 0, p, 0) is concave.

We denote by C ∞ b (D) the set of bounded functions on D which have bounded derivatives of all orders. The following lemma summarizes the result of Section 3 in the present context. Lemma 2.6. Let Assumptions (A) to (E) hold. Let B ⊂ D be a compact set and let φ be a continuous function such that φ ≥ v * + η on B, for some η > 0. Then, there exists w ∈ C ∞ b (D) such that (i) w is a classical supersolution of (2.10),

(ii) w ≤ φ on B.
Proof. By Theorem 2.5 and Assumption (D), v * dominates any bounded subsolution of (2.10). Thus, the lemma is a special case of Theorem 3.3 below, applied with w := v * .

We can now state the main result of this section, the second part of the geometric dynamic programming principle.

Theorem 2.7 (GDP2). Let Assumptions (A) to (E) hold. Fix (t, x, y) in D × R, let B ⊂ D be a compact set containing (t, x) and let θ α be the first exit time of (•, X α t,x ) from B, for α ∈ A t . Let φ be a continuous function such that φ ≥ v * + η on ∂B \ D T for some η > 0 and suppose that there exists

u o ∈ U t such that Y uo,α t,x,y (θ α ) ≥ φ(θ α , X α t,x (θ α ))1 {θ α <T } + g(X α t,x (T ))1 {θ α =T } a.s. ∀ α ∈ A t .
Then, there exists u ∈ U t such that Y u,α t,x,y (T ) ≥ g(X α t,x (T )) a.s. ∀ α ∈ A t , and in particular y ≥ v(t, x).

Proof. Note that the lower-semicontinuity of v * ensures that φ ≥ v * + η on the closure of the bounded set ∂B \ D T . It then follows from Lemma 2.6 (applied to the closure of ∂B \ D T ) that we can find a function w ∈ C ∞ b which is a supersolution of (2.10) and satisfies w ≤ φ on ∂B \ D T . Next, we introduce u ∈ U t satisfying

u[α] = u o [α]1 [[t,θ α [[ + 1 [[θ α ,T ]] û(•, X α t,x , Y u,α t,x,y , (σ X (•, α)Dw)(•, X α t,x ), α) (2.16)
for α ∈ A t . To this end, let Y be the unique strong solution of the equation

Y = Y uo,α t,x,y (θ α ) + θ α ∨• θ α µ û Y •, Y (s), σ X (•, α s )Dw, α s (s, X α t,x (s))ds + θ α ∨• θ α σ X (s, X α t,x (s), α s )Dw(s, X α t,x (s))dW s
which is well-posed by Assumption (C). Then, if we define u by

u[α] := u o [α]1 [[t,θ α [[ + 1 [[θ α ,T ]] û(•, X α t,x , Y, (σ X (•, α)Dw)(•, X α t,x ), α), it follows via the definition of û in Assumption (A) that σ X (s, X α t,x (s), α s )Dw(s, X α t,x (s)) = σ Y (s, X α t,x (s), Y (s), u[α] s , α s )
for s ≥ θ α ; that is, (2.16) is satisfied. Note that u indeed belongs to the set U t of nonanticipating strategies, due to the fact that

θ α = θ α ′ on {α| [t,s] = α ′ | [t,s] }∩{θ α ≤ s} for all s ∈ [t, T ] and α, α ′ ∈ A t .
Let us now fix α ∈ A t . Since φ ≥ w on ∂B \ D T , the definition of the first exit time θ α implies that

Y u,α t,x,y (θ α ) ≥ w(θ α , X α t,x (θ α ))1 {θ α <T } + g(X α t,x (T ))1 {θ α =T } a.s.
Applying Itô's formula to the smooth function w and using that it is a supersolution of (2.10) then leads to

Y u,α t,x,y (T ) ≥ w(T, X α t,x (T ))1 {θ α <T } + g(X α t,x (T ))1 {θ α =T } ≥ g(X α t,x (T )) a.s.
as claimed. Since α ∈ A t was arbitrary, this implies that y ≥ v(t, x).

As a consequence of Theorem 2.7, we can now prove that the upper-semicontinuous envelope v * of v is a viscosity subsolution of (2.10).

Theorem 2.8. Let Assumptions (A) to (E) hold. Then, the function v * is a bounded viscosity subsolution of (2.10).

Proof. We remark that due to the present (game) context, the proof in [START_REF] Bouchard | Stochastic target problems with controlled loss[END_REF] cannot be reproduced per se; see Remark 2.9 for details. Instead, we first consider a case where µ û Y is non-decreasing in y and then treat the general case by reduction.

Step 1. Let µ û Y be non-decreasing in its third variable y. We only prove the subsolution property on D T ; the subsolution property on D <T follows from similar arguments based on Theorem 2.7; see [6, Section 3] and [5, Section 5]. Let

x o ∈ R d be such that max D (strict)(v * -ϕ) = (v * -ϕ)(T, x o ) = 0 (2.17)
for some smooth function ϕ, and suppose for contradiction that

ϕ(T, x o ) -g(x o ) =: 2κ > 0. (2.18) Define φ(t, x) := ϕ(t, x) + √ T -t for (t, x) ∈ D; then (2.18) implies that there exists δ > 0 such that φ -g > κ on B δ := {(t, x) ∈ D : |(t, x) -(T, x o )| ≤ δ}. (2.19)
Moreover, the fact that ∂ t φ(t, x) → -∞ as t → T and the monotonicity assumption on µ û Y imply that, after possibly changing δ > 0,

inf a∈A L a (•, y, ∂ t φ, D φ, D 2 φ)(t, x) ≥ 0, ∀ (t, x, y) ∈ B δ × R s.t. y ≥ φ(t, x) -δ. (2.20) Let -ζ := sup ∂B δ \DT (v * -φ) < 0, (2.21)
where the strict inequality follows from the fact that (T, x o ) achieves a strict maximum of v * -φ. Fix 0 < ε < δ ∧ ζ ∧ κ and let (t, x) ∈ B δ and y ∈ R be such that -ε + φ(t, x) < y < v(t, x); see (2.17). Next, consider the strategy defined in a Markovian way by

α ∈ A t → û[α] := û(•, X α t,x , Y û,α t,x,y , (σ X (•, α)D φ)(•, X α t,x ), α).
Without loss of generality, we can assume that D φ is bounded on [t, T ] × R d and then the same arguments as in the proof of Theorem 2.7 show that û is well-defined as an element of U t . Given α ∈ A t , let θ α be the first exit time of (•, X α t,x ) from B δ . Then, by the definition of û and (2.20), the process Y û,α t,x,y -φ(•, X α t,x ) is non-decreasing until it reaches -δ or time reaches θ α . But since this process starts above -ε > -δ, it is in fact non-decreasing until θ α and hence

Y û,α t,x,y (θ α ) ≥ φ(θ α , X α t,x (θ α )) -ε. Set η := ζ -ε > 0. Then, φ := φ -ε ≥ v * + η on the closure of ∂B δ \ D T ; see (2.21). Moreover, it follows from (2.19) that φ-ε ≥ g + κ-ε ≥ g on B δ ∩D T ; in particular, Y û,α t,x,y (θ α ) ≥ φ(θ α , X α t,x (θ α ))1 {θ α <T } + g(X α t,x (T ))1 {θ α =T } .
Since α ∈ A t was arbitrary, Theorem 2.7 yields a contradiction to the fact that y < v(t, x).

Step 2. We now turn to the general case. Fix ρ > 0 and define Ỹ u,α t,x,y as the strong solution of d Ỹ (s) = μY (s, X α t,x (s), Ỹ (s), u[α] s , α s )ds + σY (s, X α t,x (s), Ỹ (s), u[α] s , α s )dW s with initial data Y (t) = y, where μY (t, x, y, u, a) := ρy + e ρt µ Y (t, x, e -ρt y, u, a), σY (t, x, y, u, a) := e ρt σ Y (t, x, e -ρt y, u, a).

Set g := e ρT g and define

ṽ(t, x) := inf{y ∈ R : ∃ u ∈ U t s.t. Ỹ u,α t,x,y (T ) ≥ g(X α t,x (T )) a.s. ∀ α ∈ A t }.
Since µ û Y has linear growth in its second argument y, see Assumption (C), one can choose ρ > 0 so that μû Y : (t, x, y, z, a) → ρy + e ρt µ û Y (x, e -ρt y, e -ρt z, a)

is non-decreasing in its y-variable. This means that these dynamics satisfy the monotonicity assumption used in Step 1 above; moreover, Assumptions (A) to (E) are also satisfied. Hence, the upper-semicontinuous envelope ṽ * of ṽ is a viscosity subsolution of

L(•, ϕ, ∂ t ϕ, Dϕ, D 2 ϕ) = 0 on D <T ϕ -g = 0 on D T ,
where L is defined like L but with μY and σY instead of µ Y and σ Y ; that is, L := inf a∈A La and La (t, x, y, q, p, M ) := ρy + e ρt µ ũ Y (t, x, e -ρt y, e -ρt σ X (t, x, a)p, a)

-q -µ X (t, x, a) ⊤ p - 1 2 [σ X σ ⊤ X (t, x, a)M ],
where ũ is defined like û but now in terms of σY . Since ṽ(t, x) = e ρt v(t, x), this is equivalent to saying that v * is a viscosity subsolution of (2.10).

Remark 2.9. In the proofs of [5, Section 5], the condition |y -φ(t, x)| ≤ δ was used instead of y ≥ φ(t, x) -δ as in (2.20). Correspondingly, θ α would then be the minimum of the first time when (•, X α t,x ) reaches the boundary of B δ and the first time when |Y û,α t,x,y -φ(•, X α t,x )| reaches δ. In this case, similar arguments as above imply that

Y û,α t,x,y (θ α ) ≥ φ(θ α , X α t,x (θ α ))1 {θ α <T } + g(X α t,x (T ))1 {θ α =T }
and in the context of [START_REF] Bouchard | Stochastic target problems with controlled loss[END_REF], this was enough to obtain a contradiction. However, it is not the case in our situation: this stopping time θ α is not an exit time of (•, X α t,x ), which is a key condition in our Theorem 2.7.

Remark 2.10. It follows from Assumption (D), Theorem 2.5 and Theorem 2.8 that v is continuous and that v is the unique bounded (discontinuous) viscosity solution of (2.10), whenever Assumptions (A) to (E) hold.

On the regularization of concave non-linear PDEs

In this section, we prove Lemma 2.6 above. We consider a more general setting in order to isolate the result from the particular context of the preceding section; the general version of Lemma 2.6 is stated in Theorem 3.3 below. Our result is very much in the spirit of [15, Theorem 2.1] (see also [START_REF] Barles | On the convergence rate of approximation schemes for Hamilton-Jacobi-Bellman equations[END_REF]), which we extend to our setting. Consider the parabolic equation

H(•, ϕ, ∂ t ϕ, Dϕ, D 2 ϕ) = 0 on D <T and ϕ = g on D T , (3.1)
where, for (y, q, p, M

) ∈ R × R × R d × M d , H(•, y, q, p, M ) := inf a∈A f (•, y, σ X (•, a)p, a) -q -µ X (•, a) ⊤ p - 1 2 Tr[σ X σ ⊤ X (•, a)M ] ,
for some continuous function f :

D × R × R d × A → R such that (y, z) → f (t,
x, y, z, a) is concave and has linear growth uniformly in (t, x, a) ∈ D × A, (t, x, y, z) → f (t, x, y, z, a) is continuous and uniformly Lipschitz in (x, y, z), uniformly in a ∈ A.

(3.2)

We continue to assume that the continuity and growth conditions (2.2) hold for µ X and σ X , and that g is bounded and Lipschitz continuous.

Our aim is to provide a smooth supersolution of (3.1) which is controlled by a given viscosity supersolution of the same equation, in the sense of Theorem 3.3 below. To this end, we first introduce a family of supersolutions of perturbations of (3.1). Namely, they correspond to the shaken coefficients in the terminology of [START_REF] Krylov | On the rate of convergence of finite-difference approximations for Bellman's equations with variable coefficients[END_REF]; i.e. to the operators H ε defined for (t, x, y, q, p, M )

∈ D × R × R × R d × M d by H ε (t, x, y, q, p, M ) := inf b∈Bε(0)
H((t, x) + b, y, q, p, M ) , ε > 0, where B ε (0) ⊂ R d+1 denotes the closed ball of radius ε around the origin. This is also the first step in the analysis of [START_REF] Krylov | On the rate of convergence of finite-difference approximations for Bellman's equations with variable coefficients[END_REF]Theorem 2.1], where f does not depend on y and z and the result is obtained by considering a family of standard optimal control problems in the so-called Bolza form. We shall obtain the extension to our framework by considering instead controlled forward-backward stochastic differential equations.

As in the previous section, we impose that the comparison principle holds for (3.1); this will ensure that the family of supersolutions associated to H ε is controlled from above by the supersolutions of (3.1): Assumption (F). Let w (resp. w) be a lower-semicontinuous (resp. upper-semicontinuous) bounded viscosity supersolution (resp. subsolution) of (3.1). Then, w ≥ w on D. Proposition 3.1. Let Assumption (F) hold. For all ε ∈ [0, 1], there exists a bounded and continuous viscosity solution w ε of

H ε (•, ϕ, ∂ t ϕ, Dϕ, D 2 ϕ) = 0 on D <T (3.3)
with the following properties:

(i) There exists c ε ∈ [0, T ) such that Proof. We shall construct the functions w ε as value functions associated to controlled forward-backward stochastic differential equations. Some of the subsequent technical arguments are known and will only be sketched; we focus on the points specific to our problem.

w ε ≥ g + ε on [T -c ε , T ] × R d and c ε > 0 if ε > 0. ( 3
Step 1. In this step, we introduce a family of controlled forward-backward equations indexed by ε. To this end, let T denote the set of stopping times and D 2 the collection of pairs (τ, ξ) such that τ ∈ T and ξ ∈ L 2 (F τ ; R d ). Moreover, we denote by S 2 the set of predictable processes ψ such that sup t≤T |ψ t | ∈ L 2 and by H 2 the set of P⊗dt-square-integrable predictable processes. Finally, we let B ε (resp. A) denote the set of predictable processes with values in the ball B ε (0) ⊂ R d+1 (resp. A). For each ε ∈ [0, 1], given a control γ := (α, β) ∈ A × B ε =: Γ ε and an initial condition ζ := (τ, ξ) ∈ D 2 , we now consider the decoupled forward-backward stochastic differential equation

Xζ,γ = ξ + • τ µ X ((s, Xζ,γ s ) + β s , α s )ds + • τ σ X ((s, Xζ,γ s ) + β s , α s )dW s , Ȳ ε,ζ,γ = g ε ( Xζ,γ T ) - T •∨τ f ζ γ (s, Ȳ ε,ζ,γ s , Zε,ζ,γ s )ds - T •∨τ Zε,ζ,γ s dW s ,
where g ε := g + 2ε and

f ζ γ (s, y, z) := f ((s, Xζ,γ s ) + β s , y, z, α s ) for (s, y, z) ∈ [0, T ] × R × R d .
Note that the forward equation does not depend on ε. Moreover, (3.2) implies that

(y, z) ∈ R × R d → f ζ γ (s, y, z) is Lipschitz continuous with linear growth uniformly in (s, ζ, γ) ∈ [0, T ] × D 2 × Γ 1 . (3.6)
Existence and uniqueness of the solution ( Xζ,γ , Ȳ ε,ζ,γ , Zε,ζ,γ ) ∈ S 2 × S 2 × H 2 are standard; see e.g. [START_REF] Pardoux | Backward stochastic differential equations and viscosity solutions of systems of semilinear parabolic and elliptic pdes of second order[END_REF]. For γ ∈ Γ ε , ζ = (τ, ξ) ∈ D 2 and θ ∈ T such that θ ≥ τ a.s., we now define

Y ε,ζ,γ θ := ess sup γ ′ ∈Γε Ȳ ζ,γ⊕ θ γ ′ θ , where γ ⊕ θ γ ′ := γ1 [[0,θ]] + 1 ]]θ,T ]] γ ′ . (3.7)
By a Girsanov change of measure argument as in [8, Proposition 3.3] (which is in turn an extension of [START_REF] Peng | Bsde and stochastic optimizations[END_REF]), it follows that

(t, x) ∈ D → w ε (t, x) := Y ε,(t,x),γ t (3.8)
is a deterministic function on D, independent of γ ∈ Γ 1 . In the remainder of the proof, we show that w ε satisfies the requirements of the proposition.

Step 2. We provide some estimates that will be used later on. We first observe that (3.2), [18, Theorem 1.5], (2.2) and the Lipschitz continuity of g imply that we can find c > 0, independent of ε, such that

E | Ȳ ε,ζ1,γ⊕τ 1 γ ′ τ1 -E τ1 Ȳ ε,ζ2,γ⊕τ 2 γ ′ τ2 | 2 ≤cE |ξ 1 -ξ 2 | 2 + |τ 1 -τ 2 | (3.9)
for all ζ i = (τ i , ξ i ) ∈ D 2 , i = 1, 2, such that τ 1 ≤ τ 2 , and γ, γ ′ ∈ Γ ε . As the family

{ Ȳ ε,ζ1,γ⊕τ 1 γ ′ τ1 } γ ′ ∈Γε is directed upward, it follows from [17, Proposition VI-1-1] that we can find a sequence (γ ′ n ) n ⊂ Γ ε such that Ȳ ε,ζ1,γ⊕τ 1 γ ′ n τ1
↑ Y ε,ζ1,γ τ1 a.s.; see e.g. [6, Lemma 2.4] for a similar argument. Then

Y ε,ζ1,γ τ1 -E τ1 Y ε,ζ2,γ τ2 ≤ lim inf n Ȳ ε,ζ1,γ⊕τ 1 γ ′ n τ1 -E τ1 Ȳ ε,ζ2,γ⊕τ 2 γ ′ n τ2
.

Similarly, we can find

(γ ′′ n ) n ⊂ Γ ε such that E τ1 Y ε,ζ2,γ τ2 -Y ε,ζ1,γ τ1 ≤ lim inf n E τ1 Ȳ ε,ζ2,γ⊕τ 2 γ ′′ n τ2 - Ȳ ε,ζ1,γ⊕τ 1 γ ′′ n τ1 .
Moreover, as g is bounded and f satisfies (3.6), we deduce from [20, Theorem 2.2] that ess sup

γ ′ ∈Γε (| Ȳ ζ2,γ ′ τ2 | + | Ȳ ζ1,γ ′ τ1 |) ∈ L 2 .
Then, combining the above with the dominated convergence theorem and the apriori estimate (3.9) yields that

E |Y ε,ζ1,γ τ1 -E τ1 Y ε,ζ2,γ τ2 | 2 ≤ cE |ξ 1 -ξ 2 | 2 + |τ 1 -τ 2 | . (3.10)
Applying this inequality to ζ 1 = (t, x) ∈ D and ζ 2 = (T, x), we see that

|Y ε,(t,x),γ t -g ε (x)| ≤ c √ T -t ∀ (t, x, γ) ∈ D × Γ ε . (3.11)
Step 3. The fact that w ε

(z) = Y ε,z,γ t for all z = (t, x) ∈ D ensures that w ε (ζ) = Y ε,ζ,γ τ for simple random variables ζ = (τ, ξ) ∈ D 2 .
The estimate (3.10) shows that the function w ε is continuous and a simple approximation argument implies that

w ε (ζ) = Y ε,ζ,γ τ for all ζ = (τ, ξ) ∈ D 2 and γ ∈ Γ ε . In particular, for z = (t, x) ∈ D, w ε (τ, Xz,γ τ ) = Y ε,z,γ τ for all τ ∈ T t , (3.12)
and Y ε,z,γ admits a modification with continuous paths.

Step 4. We now sketch the proof of the dynamic programming principle for Y ε , and thus for

w ε . Fix z = (t, x) ∈ D, γ ∈ Γ ε and let t ≤ τ ≤ θ ≤ T be two stopping times. Let γ n ∈ Γ ε be such that Y ε,z,γ θ ≤ Ȳ z,γ⊕ θ γn θ + n -1 .
Then, by the stability result [18, Theorem 1.5], one can find c > 0 and a sequence (δ n ) n≥1 of random variables converging to 0 a.s. such that

Y ε,z,γ τ ≥ Ȳ ε,z,γ⊕ θ γn τ = E f z γ τ,θ [ Ȳ ε,z,γ⊕ θ γn θ ] ≥ E f z γ τ,θ [Y ε,z,γ θ ] -cδ n , where E f z γ τ,θ [χ]
denotes the value at time τ of the first component of the solution to the backward stochastic differential equation with driver f z γ and terminal condition χ ∈ L 2 (F θ ) at time θ. By sending n → ∞, this implies that

Y ε,z,γ τ ≥ E f z γ τ,θ [Y ε,z,γ θ ].
Conversely, it follows from the comparison principle [START_REF] Pardoux | Backward stochastic differential equations and viscosity solutions of systems of semilinear parabolic and elliptic pdes of second order[END_REF]Theorem 1.6] that

Y ε,z,γ τ = ess sup γ ′ ∈Γε Ȳ ε,z,γ⊕τ γ ′ τ ≤ ess sup γ ′ ∈Γε E f z γ⊕τ γ ′ τ,θ [Y ε,z,γ⊕τ γ ′ θ ],
which, combined with the above, implies

Y ε,z,γ τ = ess sup γ ′ ∈Γε E f z γ⊕τ γ ′ τ,θ [Y ε,z,γ⊕τ γ ′ θ ]. (3.13)
Step 5. We already know from Step 3 that w ε is continuous. Then, standard arguments based on the identification (3.12) and the dynamic programming principle (3.13) show that w ε is a continuous viscosity solution of (3.3); see [START_REF] Peng | A generalized dynamic programming principle and Hamilton-Jacobi-Bellman equation[END_REF] and [START_REF] Buckdahn | Stochastic differential games and viscosity solutions of Hamilton-Jacobi-Bellman-Isaacs equations[END_REF] for details.

Step 6. We conclude with the remaining estimates. The bound (3.11) and the fact that g is bounded imply that (w ε ) ε∈[0,1] is uniformly bounded. Moreover, the estimate (3.11) implies (3.4); it remains to prove (3.5). We first observe that the family (w ε ) ε∈[0,1] is non-decreasing by the comparison principle for backward stochastic differential equations and therefore admits a limit w0 ≥ w 0 as ε → 0. The stability of viscosity solutions, see e.g. [START_REF] Barles | Convergence of approximation schemes for fully nonlinear second order equations[END_REF], combined with Assumption (F) ensures that w0 is a continuous bounded viscosity solution of (3.1). Since w 0 is a bounded continuous viscosity solution of the same equation, Assumption (F) implies that lim ε↓0 w ε = w0 = w 0 . By Dini's theorem, the convergence is uniform on compact sets, which is (3.5). Remark 3.2. Consider again the setting of Section 2 with Assumptions (A) to (E). For f := µ û Y , the equations (3.1) and (2.10) coincide and hence v = w 0 by uniqueness, where w 0 is defined in (3.8). Thus, the controlled forward-backward stochastic differential equation (3.7) with ε = 0 is a dual problem for the stochastic target game.

We now apply the smoothing technique used in [START_REF] Krylov | On the rate of convergence of finite-difference approximations for Bellman's equations with variable coefficients[END_REF]Section 2] to the functions w ε obtained in Proposition 3.1 to construct a suitable smooth supersolution of (3.1). The stability results (3.4) and (3.5) play an important role in ensuring that the correct boundary condition at time T is satisfied and that the upper bound in (ii) below holds true. Theorem 3.3. Let Assumption (F) hold and let w be a function on D which dominates any bounded viscosity subsolution of (3.1). Moreover, let B ⊂ D be a compact set and φ be a continuous function such that φ ≥ w + η on B, for some η > 0. Then, there exists w ∈ C ∞ b (D) such that (i) w is a classical supersolution of (3.1),

(ii) w ≤ φ on B.
Proof. The proof is provided for the sake of completeness; we follow closely [START_REF] Krylov | On the rate of convergence of finite-difference approximations for Bellman's equations with variable coefficients[END_REF] and [START_REF] Ishii | On the equivalence of two notions of weak solutions, viscosity solutions and distribution solutions[END_REF]. Throughout, any function w on D is extended to R × R d by w(t, x) = w(0, x) for t < 0 and w(t, x) = w(T, x) for t > T .

Step 1. We first construct a semi-concave function which is a.e. a supersolution of (3.1) in the interior of the parabolic domain. Let w ε be as in Proposition 3.1. For k ≥ 1, consider the quadratic inf-convolution

w k ε (z) := inf z ′ ∈D (w ε (z ′ ) + k|z -z ′ | 2 ), z ∈ D.
Since w ε is continuous and bounded, the infimum is achieved at some point ẑk (z).

Note that

w ε ≥ w k ε ≥ -|w ε | ∞ , where | • | ∞ denotes the sup-norm on D. Hence, k|z -ẑk (z)| 2 = w k ε (z) -w ε (ẑ k (z)) ≤ 2|w ε | ∞ =: l. It follows that |z -ẑk (z)| 2 ≤ l/k =: (ρ k ) 2 . (3.14)
In particular, ẑk (z) → z as k → ∞ and thus, using again w ε ≥ w k ε and the continuity of w ε ,

w ε (z) ≤ lim inf k→∞ (w ε (ẑ k (z)) + k|z -ẑk (z)| 2 ) ≤ lim sup k→∞ w k ε (ẑ k (z)) ≤ w ε (z).
Let ϕ be a smooth function on D and let z ∈ D <T be such that

min D (w k ε -ϕ) = (w k ε -ϕ)(z) = 0.
Then, for any z ′ ∈ D,

w ε (ẑ k (z) + z ′ -z) + k|ẑ k (z) -z| 2 -ϕ(z ′ ) ≥ w k ε (z ′ ) -ϕ(z ′ ) ≥ w k ε (z) -ϕ(z) = w ε (ẑ k (z)) + k|ẑ k (z) -z| 2 -ϕ(z).
Hence, the minimum of z ′ ∈ D → w ε (ẑ k (z) + z ′ -z) -ϕ(z ′ ) is achieved by z ′ = z and therefore

(∂ t ϕ, Dϕ, D 2 ϕ)(z) ∈ P-w ε (ẑ k (z)),
where Pw ε (ẑ k (z)) denotes the closed parabolic subjet of w ε at ẑk (z); see e.g. [START_REF] Crandall | User's guide to viscosity solutions of second order partial differential equations[END_REF]. In view of Proposition 3.1, this shows that w k ε is a viscosity supersolution of

H ε (ẑ k (•), ϕ, ∂ t ϕ, Dϕ, D 2 ϕ) ≥ 0 on [ρ k , T -ρ k ] × R d .
Take k large enough so that ρ k ≤ ε/2. Then, (3.14) yields that

{ẑ k (z) + b, b ∈ B ε (0)} ⊃ {z + b, b ∈ B ε/2 (0)}.
This implies that w k ε is a viscosity supersolution of

min b∈B ε/2 (0) H(• + b, ϕ, ∂ t ϕ, Dϕ, D 2 ϕ) ≥ 0 on [ρ k , T -ρ k ] × R d .
Step 2. We now argue as in [START_REF] Ishii | On the equivalence of two notions of weak solutions, viscosity solutions and distribution solutions[END_REF] to construct from the previous step a smooth supersolution in the interior of the parabolic domain. Since w k ε is semi-concave, there exist D abs 2 w k ε ∈ L 1 (D) and a Lebesgue-singular negative Radon measure D sing

2 w k ε on D such that D 2 w k ε (dz) = D 2 abs w k ε dz + D 2 sing w k ε in the distribution sense and (∂ t w k ε , Dw k ε , D 2 abs w k ε ) ∈ P-w k ε a.e. on [ρ k , T -ρ k ] × R d ; see [14, Section 3]. Hence, Step 1 implies that min b∈B ε/2 (0) H(• + b, w k ε , ∂ t w k ε , Dw k ε , D 2 abs w k ε ) ≥ 0 a.e. on [ρ k , T -ρ k ] × R d . (3.15)
Next, we mollify w k ε . Let ψ ∈ C ∞ b be a non-negative function with support [-1, 0] × [-1, 1] d such that R d+1 ψ(z)dz = 1, and set ψ δ (z) = δ -d-1 φ(z/δ) for z ∈ R d+1 and δ > 0. For any bounded measurable function w on D and (t,

x) ∈ [δ, T ] × R d , let w ⋆ ψ δ (t, x) := R×R d w(t ′ , x ′ )ψ δ (t ′ -t, x ′ -x)dt ′ dx ′ = R×R d w(t + t ′ , x + x ′ )ψ δ (t ′ , x ′ )dt ′ dx ′ .
Using (3.15) and the fact that (y, q, p, M

) ∈ R × R × R d × M d → H(•, y, q, p, M ) is concave due to (3.2), we obtain for δ < ε/2 that H 0 •, w k ε ⋆ ψ δ , ∂ t w k ε ⋆ ψ δ , (Dw k ε ) ⋆ ψ δ , (D 2 abs w k ε ) ⋆ ψ δ (z o ) ≥ 0 for all z o ∈ [ρ k + δ, T -ρ k ] × R d . Note that, since D 2 sing w k ε ≤ 0 and ψ δ ≥ 0, R×R d ψ δ D 2 abs w k ε dz ≥ R×R d ψ δ D 2 abs w k ε dz + R×R d ψ δ D 2 sing w k ε (dz) = R×R d w k ε D 2 ψ δ dz
by integration-by-parts. Since L is parabolic, this shows that, on

[ρ k +δ, T -ρ k ]×R d , H 0 •, w k ε ⋆ ψ δ , ∂ t (w k ε ⋆ ψ δ ), D(w k ε ⋆ ψ δ ), D 2 (w k ε ⋆ ψ δ ) ≥ 0.
By sending k → ∞, we obtain that w ε,δ := w ε ⋆ ψ δ is a supersolution of (3.1) on (δ, T ). Moreover,

w ε,δ ∈ C ∞ b (D) since ψ ∈ C ∞ b (D)
and w ε is bounded by Proposition 3.1.

Step 3. We now choose ε and δ so that the supersolution property holds at T and (ii) of the theorem is satisfied for w = w ε,δ . We first use that φ ≥ w + η and that w dominates bounded subsolutions of (3.1); in particular, w ≥ w 0 by Proposition 3.1. Choose ε such that the constant c

B ε in (3.5) satisfies c B ε ≤ η/2, then w ε ≤ w 0 + c B ε ≤ φ -η + c B ε ≤ φ -η/2.
As w ε is continuous, we have w ε,δ → w ε uniformly on the compact set B. Thus, for δ > 0 small enough with respect to η, w ε,δ ≤ φ on B, which is assertion (ii). For the supersolution property at T , we first appeal to (3.4) and choose δ ∈ (0, c ε ) such that we also have w ε,δ ≥ g ⋆ ψ δ + ε on D T . Since g is uniformly continuous, we can choose δ > 0 small enough so that g ⋆ ψ δ ≥ g -ε on D T , and therefore w ε,δ ≥ g on the parabolic time boundary.

Step 4. The fact that w ε,δ is only a supersolution of (3.1) on (δ, T ] and not on [0, T ] is not restrictive; we can follow the same arguments on [-1, T ] instead of [0, T ] and obtain that w ε,δ is a supersolution of (3.1) on (-1 + δ, T ] ⊃ [0, T ] for 0 < δ < 1.

O ∈ C ∞ b (R d × R d ; R + ) such that, for all x ∈ R d , (i) x + δx ′ ∈ O for all δ ∈ (0, δ O ) and x ′ ∈ R d such that ψ O (x, x ′ ) = 0, (ii) R d ψ O (x, x ′ )dx ′ = 1, (iii) the support of ψ O (x, •) is contained in [-1, 1] d .
Indeed, it then suffices to replace the mollifier ψ δ introduced in Step 2 of the proof of Theorem 3.3 by

ψ δ (t ′ , x ′ ; x) := δ -1-d φ(t ′ /δ)ψ O (x, x ′ /δ), (t ′ , x ′ , x) ∈ R × R d × R d ,
for some smooth function φ ≥ 0 with support [-1, 0] such that R φ(t)dt = 1, and to define the convolution operation by

w ⋆ ψ δ (t, x) := R×R d w(t ′ , x ′ )ψ δ (t ′ -t, x ′ -x; x)dt ′ dx ′ = R×R d w(t + t ′ , x + x ′ )ψ δ (t ′ , x ′ ; x)dt ′ dx ′ . For δ ≤ δ O , the condition (i) above ensures that x ′ = x + δ(x -x ′ )/δ ∈ O whenever x ∈ O and ψ δ (t ′ -t, x ′ -x; x) = 0.
Similarly, the proofs of Theorems 2.3 and 2.5 do not change if we replace [0, T ]× R d by [0, T ] × O. Under the additional assumption introduced above, Lemma 2.6 also extends to this case, and so do the proofs of Theorems 2.7 and 2.8, whenever the comparison principle of Assumption (D) holds for D = [0, T ] × O.

Super-hedging under model uncertainty

In this section, we apply the above results to a super-hedging problem under model uncertainty, where the dynamics of the underlying stocks and the interest rates depend on a process α which is only known to take values in the given set A. We consider an investor who wants to hedge an option written on some underlying stocks whose log-prices evolve according to

X α t,x = x + • t µ(s, X α t,x (s), α s )ds + • t σ(s, X α t,x (s), α s )dW s ,
for some unknown process α ∈ A t . Thus, there can be uncertainty both about the drift and the volatility. Moreover, the range of possible coefficients may be statedependent. The investor also has a money market account at his disposal; however, the interest rates (r b (s, X α t,x (s), α s )) s≤T and (r l (s, X α t,x (s), α s )) s≤T for borrowing and lending are different and also depend on the process α.

A trading policy for the investor is a process ν ∈ U t taking values in U = R d . Recall that U t consists of processes which are in L p (P × dt) for some p ≥ 2. In this section, we choose p > 2. Each component ν i corresponds to the monetary amount invested in the i-th stock. Given some initial capital y ∈ R at time t, the wealth process Y ν,α t,x,y then evolves according to The process α may be interpreted as a directly observable risk factor such as the federal funds rate or an indicator for the state of the economy. In this case it clearly makes sense that the investor's actions may depend on α in a nonanticipative way. Alternatively, as the stocks X α t,x are observable, so are the volatilities σ(s, X α t,x (s), α s ). Therefore, if a → σ(s, x, a) is invertible, the process α is automatically observable. We thus allow the investor to choose a non-anticipative strategy u ∈ U t . As a result, the super-hedging price is defined by v(t, x) := inf{y ∈ R : ∃ u ∈ U t s.t. Y u,α t,x,y (T ) ≥ g(X α t,x (T )) a.s. ∀ α ∈ A t } or the smallest price which allows to super-hedge for all α ∈ A t . We henceforth assume that g is bounded and Lipschitz continuous, that µ and σ are continuous functions, that We observe that the assumption (4.2) is in fact a no-arbitrage condition. In this setting, we have the following characterization of the super-hedging price. Proof. The present model satisfies the conditions (2.2) and (2.3) of Section 2. Moreover, Assumption (A) holds with û(t, x, y, z, a) = (σ -1 ) ⊤ (t, x, a)z.

Y ν,
To verify Assumption (B), consider a ∈ A and u ∈ U. Then Itô's formula, our choice p > 2 and (4.2) imply that the process (e -• t r b (s,a)ds Y u,a t,x,y ) is a super-martingale under the probability measure Q a t,x defined via the Doléans-Dade exponential

dQ a t,x dP = E T - • t λ b (s, X a t,x (
s), a)dW s .

In particular, if D <T × R ∋ (t n , x n , y n ) → (T, x, y) ∈ D T × R and (u n ) n≥1 are such that u n ∈ U tn and Y un,a tn,xn,yn (T ) ≥ g(X a tn,xn (T )) a.s., then y n ≥ E Q a tn ,xn [g(X a tn,xn (T ))] for all n ≥ 1, while (4.1) and the continuity of the bounded function g ensure that E Q a tn ,xn [g(X a tn,xn (T ))] → g(x) as n → ∞. Since y n → y, this shows that y ≥ g(x), so Assumption (B) holds.

As g is bounded, the same super-martingale property implies that v is bounded from below. Moreover, as r l is bounded, v is also bounded from above, so we have (2.6). To verify Assumption (C), we use the definitions of û and ρ to obtain that µ û Y (t, x, y, z, a) := ρ(t, x,y, û(t, x, y, z, a), a) + û(t, x, y, z, a) ⊤ {µ(t, x, a) + 1 2 γ(t, x, a)}

. 4 )

 4 (ii) For any compact set B ⊂ D, there exists c B ε satisfying c B ε → 0 as ε → 0 and w ε -c B ε ≤ w 0 on B. (3.5)

Remark 3 . 4 .

 34 In some applications, one might want to restrict the spatial domain to an open set O ⊂ R d , for instance if the process X α of Section 2 is defined as a stochastic exponential. Then, the equation (3.1) should be naturally set on D := [0, T ] × O. In this more general context, the arguments of Proposition 3.1 can be reproduced without modification whenever the comparison principle of Assumption (F) holds for D = [0, T ] × O. Moreover, the proof of Theorem 3.3 can be generalized to this context under the following additional assumption: there exist δ O > 0 and ψ

  and, with1 := (1, . . . , 1) ⊤ , ρ(t, x, y, u, a) := [y -u ⊤ 1] + r l (t, x, a) -[y -u ⊤ 1] -r b (t, x, a) for (t, x, y, u, a) ∈ [0, T ]×R d × R × R × A.

  (t, x, a) ∈ [0, T ] × R d × A → (µ, σ, r l , r b )(t,x, a) is continuous, bounded, continuous in (t, x) and Lipschitz continuous in x, both uniformly in a, and that σ(t, x, a) is invertible for all (t, x, a) ∈ [0, T ] × R d × A.

(4. 1 )

 1 We also assume that r b ≥ r l and thatλ b := σ -1 (µ + 1 2 γ -r b ) and λ l := σ -1 (µ + 1 2 γ -r l ) are bounded, (4.2) (t, x, a) ∈ [0, T ] × R d × A → (λ b , λ l )(t,x, a) does not depend on x.(4.3)

Corollary 4 . 1 .

 41 The function v is continuous and the unique bounded viscosity solution ofinf a∈A ρ(•, ϕ, Dϕ, a) + 1 2 γ(•, a)Dϕ -L a ϕ = 0 on [0, T ) × R d ϕ(T, •) = g on R d ,where L a ϕ(t, x) := ∂ t ϕ(t, x) + 1 2 Tr[σσ ⊤ (t, x, a)D 2 ϕ(t, x)].

  satisfies |µ û Y (t, x, y, z, a)| ≤ |y|(|r b | ∨ |r l |)(t, x,a) + |z|(|λ l | ∨ |λ b |)(t, x, a) and|µ û Y (t, x, y, z, a) -µ û Y (t, x, y ′ , z ′ , a)| ≤ |y -y ′ |(|r b | ∨ |r l |)(t, x,a) +|z -z ′ |(|λ b | ∨ |λ l |)(t, x, a)for all (t, x, a) ∈ [0, T ]×R d ×A and (y, z), (y ′ , z ′ ) ∈ R×R d . The Lipschitz continuity in the x-variable follows immediately from (4.3). Assumption (E) is satisfied 3 due to r l ≤ r b . Finally, Assumption (D) follows from standard arguments under our Lipschitz continuity conditions; cf.[START_REF] Crandall | User's guide to viscosity solutions of second order partial differential equations[END_REF].

  and θ 2 is the first time |Y -ϕ(•, X)| reaches the level δ. Using (2.11) again, we observe that v

* -ϕ ≥ 0 on B and (v * -ϕ) ≥ ζ on ∂B, for some ζ > 0. Then, (2.14) and the definition of θ imply that

  (s), α s )dW s , where γ is the vector containing the elements of the diagonal of the matrix σσ ⊤

	α t,x,y	= y +		t	•	ν ⊤ s {dX α t,x (s) + 1 2 γ(s, X α t,x (s), α s )ds}
		+	t	•	ρ(s, X α t,x (s),Y ν,α t,x,y (s), ν s , α s )ds
		= y +		t	•	ν ⊤ s {µ + 1 2 γ} + ρ (s, X α t,x (s), Y ν,α t,x,y (s), ν s , α s )ds
		+	t	•	ν ⊤ s σ(s, X α t,x

Note added in proof: In the follow-up work[START_REF] Bayraktar | Stochastic perron for stochastic target games[END_REF], a similar target game problem is treated by a stochastic Perron's method which does not require a dynamic programming principle.

This last condition is missing in[START_REF] Bouchard | Stochastic target problems with controlled loss[END_REF].

We may observe here that this concavity condition is satisfied in a very natural way in the context of mathematical finance, where wealth dynamics are typically either linear or exhibit concave nonlinearities. The concavity is related to the absence of arbitrage opportunities; in the present example, the fact that r b ≥ r l .

Research supported by NSF Grant DMS-1208985.