Paul Gassiat
email: pgassiat@math.jussieu.fr

Huyên Pham
email: pham@math.jussieu.fr

Mihai Sîrbu
email: sirbu@math.utexas.edu

Optimal investment on finite horizon with random discrete order flow in illiquid markets *

Keywords: liquidity modelling, discrete order flow, optimal investment, inhomogenous Poisson process, dynamic programming MSC Classification (2000): 60G51, 49K22, 93E20, 91B28. JEL Classification: G11, C61

We study the problem of optimal portfolio selection in an illiquid market with discrete order flow. In this market, bids and offers are not available at any time but trading occurs more frequently near a terminal horizon. The investor can observe and trade the risky asset only at exogenous random times corresponding to the order flow given by an inhomogenous Poisson process. By using a direct dynamic programming approach, we first derive and solve the fixed point dynamic programming equation and then perform a verification argument which provides the existence and characterization of optimal trading strategies. We prove the convergence of the optimal performance, when the deterministic intensity of the order flow approaches infinity at any time, to the optimal expected utility for an investor trading continuously in a perfectly liquid market model with no-short sale constraints.

Introduction

Financial modeling very often relies on the assumption of continuous-time trading. This is essentially due to the availability of the powerful tool of stochastic integration, which allows for an elegant representation of continuous-time trading strategies, and the analytic tractability of the stochastic calculus, typically illustrated by Itô's formula. Sometimes this assumption may not be very realistic in practice: illiquid markets provide a prime example. Indeed, an important aspect of market liquidity is the time restriction both on trading and observation of the assets. For example, in power markets, trading occurs through a brokered OTC market, and the liquidity is really thin. There could be a possible lack of counterparty for a given order: bids and offers are not available at any time, and may arrive randomly, while the investor can observe the asset only at these arrival times. Moreover, in these markets, because of the physical nature of the underlying asset, trading activity is really low far from the delivery, and is higher near the delivery.

In this paper, we propose a framework that takes into account such liquidity features by considering a discrete order flow. In our model, the investor can observe and trade over a finite horizon only at random times given by an inhomogenous Poisson process encoding the quotes in this illiquid market. To capture the high frequency of trading in the neighborhood of the finite horizon, we assume that the deterministic intensity of this inhomogenous Poisson process approaches infinity as time gets closer to the finite horizon. In this context, the objective of the agent is to maximize his/her expected utility from terminal wealth.

Optimal investment problems with random discrete trading dates were studied by several authors. Rogers and Zane [START_REF] Rogers | A simple model of liquidity effects[END_REF] and Matsumoto [START_REF] Matsumoto | Optimal portfolio of low liquid assets with a log-utility function[END_REF] considered trading times associated to the jump times of a Poisson process, but assumed that price process is observed continuously, so that trading strategies are actually in continuous-time. Recently, Pham and Tankov [START_REF] Pham | A model of optimal consumption under liquidity risk with random trading times[END_REF] (see also [START_REF] Cretarola | Optimal consumption policies in illiquid markets[END_REF]) investigated an optimal portfolio/consumption choice problem over an infinite horizon, where the asset price, essentially extracted from a Black-Scholes model, can be observed and traded only at the random times corresponding to a Poisson process with constant intensity.

As mentioned above, here we investigate an optimal investment problem over a finite horizon with random trading and observation times given by an inhomogeneous Poisson process with a deterministic intensity going to infinity near the final horizon. The underlying continuous-time asset price is given by an inhomogeneous Lévy process. We use a direct dynamic programming approach for solving this portfolio selection problem. We first derive the fixed point dynamic programming equation (DPE) and provide a constructive proof for the existence of a solution to this DPE in a suitable functional space by means of an iterative procedure. Then, by proving a verification theorem, we obtain the existence and characterization of optimal policies. We also provide an approximation of the optimal strategies that involves only a finite number of iterations. Finally, we address the natural question of convergence of our optimal investment strategy/expected utility when the arrival intensity rate becomes large at all times. We prove that the value function converges to the value function of an agent who can trade continuously in a perfectly liquid mar-ket with no-short sale constraints. A related convergence result was recently obtained by Kardaras and Platen [START_REF] Kardaras | Multiplicative approximation of wealth processes involving no-short-sale strategies via simple trading[END_REF] by considering continuous-time trading strategies approximated by simple trading strategies with constraints, but with asset prices observed continuously. Here we face some additional subtleties induced by the discrete observation filtrations: the illiquid market investor has less information coming from observing the asset, compared to the continuous-time investor, but he/she has the additional information coming from the arrival times, which is lacking in the perfectly liquid case.

The rest of the paper is organized as follows. Section 2 describes the illiquid market model with the restriction on the trading times, and sets up all the assumptions of the model. We formulate in Section 3 the optimal investment problem, and solve it by a dynamic programming approach and verification argument. Finally, Section 4 is devoted to the convergence issue when the deterministic intensity of arrivals is very large at all times.

The illiquid market model and trading strategies

We consider an illiquid market in which an investor can trade a risky asset over a finite horizon. In this market, bids and offers are not available at any time, but trading occurs more frequently near the horizon. This is typically the case in power markets with forward contracts. This market illiquidity feature is modelled by assuming that the arrivals of buy/sell orders occur at the jumps of an inhomogeneous Poisson process with an increasing deterministic intensity converging to infinity at the final horizon. In order to obtain an analytically tractable model, we further assume that the discrete-time observed asset prices come from an unobserved continuous-time stochastic process, which is independent of the sequence of arrival times. We may think about the continuous time process as an asset price process based on fundamentals independent of time-illiquidity, which would be actually observed if trading occurred at all times.

More precisely, fixing a probability space (Ω, G, P) and a finite horizon T < ∞, we consider the fundamental unobserved positive asset price (S t ) 0≤t≤T . An investor can observe and trade the asset only at some exogenous random times (τ n ) n≥0 , τ 0 = 0, such that (τ n ) n≥0 and (S t ) 0≤t≤T are independent under the physical probability measure P.

In order to obtain a stochastic control problem of Markov type for the utility maximization problem below, we assume an exponential-Lévy structure and some regularity/integrability conditions on the continuous time positive price process S. More precisely, we assume that

S t = E(L) t , 0 ≤ t ≤ T,
where the process (L t ) 0≤t≤T is a semimartingale on (Ω, G, P) with independent increments and jumps strictly greater than one. We use E(L) to denote the Doléans-Dade stochastic exponential of L. The assumption ∆L > -1 ensures that the asset S, as well as its leftlimit S -, are strictly positive at all times. It is well known that a semimartingale with independent increments has deterministic predictable characteristics, see e.g. [START_REF] Jacod | Limit theorems for stochastic processes[END_REF]. Denoting by µ(dt, dx, ω) the jump measure and by ν(dt, dx) its deterministic compensator, we assume that the large jumps are integrable, namely that the compensator measure ν(dt, dy) of µ satisfies

T 0 ∞ -1 y ν(dt, dy) < ∞. (2.1)
The Lévy-Khintchin-Itô decomposition implies that

L t = A(t) + M t + t 0 ∞ -1 y(µ(dt, dy) -ν(dt, dy)), 0 ≤ t ≤ T,
where A is a deterministic function of bounded variation and M is a continuous local martingale with deterministic quadratic variation, so it is Gaussian. We further assume the following regularity of the deterministic predictable characteristics 1. there exists a function b : [0, T ] → R such that

T 0 |b(u)|du < ∞ and A(t) = t 0 b(u) du, 0 ≤ t ≤ T (2.2)
2. there exists a function c

: [0, T ] → (0, ∞) such that T 0 c 2 (u)du < ∞ and M t = t 0 c 2 (u) du, 0 ≤ t ≤ T. (2.3)
Conditions (2.1), (2.2) and (2.3) together mean that we actually make the following assumption on L: (HL)

L t = t 0 b(u) du + t 0 c(u) dB u + t 0 ∞ -1 y(µ(dt, dy) -ν(dt, dy)), 0 ≤ t ≤ T,
where (B t ) 0≤T is a Brownian motion on (Ω, G, P) independent on the jump measure µ, the measure µ satisies (2.1) and b, c satisfy (2.2) and (2.3). We denote by

Z t,s = S s -S t S t =    e (Ls-Lt-1 2 R s t c 2 (u) du) t<u≤s e -∆Lu (1 + ∆L u )    -1, 0 ≤ t ≤ s ≤ T,
the return between times t and s (if trading is allowed at both times) and denote by

p(t, s, dz) = P[Z t,s ∈ dz]
the distribution of the return.

Remark 2.1 Assumption (HL) ensures that (i) For all 0 ≤ t < s ≤ T the distribution p(t, s, dz) has support whose interior is equal to (-1, ∞).

(ii) There exists some positive constant C > 0 such that (- , where b is defined in (2.2). (iii) Since in our model the asset S is not observed at terminal time T , there is no loss of generality if we assume that S T = S T -, which can be translated in terms of predictable characteristics as ν({T }, (-1, ∞)) = 0. We will make this assumption for the rest of the paper.

The sequence of observation/trading times is represented by the jumps of an inhomogeneous (and independent on S) Poisson process (N t ) t∈[0,T ] with deterministic intensity function t ∈ [0, T ) → λ(t) ∈ (0, ∞), such that:

t 0 λ(u)du < ∞, (∀) 0 ≤ t < T and T 0 λ(u)du = ∞.
(2.4)

The simplest way to actually define such an inhomogeneous Poisson process is to consider a homogeneous Poisson process M with intensity equal to one, independent of S and define

N t = M R t 0 λ(u)du for 0 ≤ t < T. (2.5)
Condition (2.4) ensures that the probability of having no jumps between any interval [t, T ], t < T , is null, and so the sequence (τ n ) converges increasingly to T almost surely when n goes to infinity. We also know that the process of jump times (τ n ) n≥0 is a homogeneous Markov chain on [0, T ), and its transition probability admits a density given by:

P[τ n+1 ∈ ds|τ n = t] = λ(s)e - R s t λ(u)du 1 {t≤s<T } ds, (2.6)
(which does not depend on n).

An investor trading in this market can only observe/trade the asset S at the discrete arrival times τ n . Therefore, the only information he/she has is coming from observing the two-dimensional process (τ n , S τn ) n≥0 . Taking this into account, we introduce the discrete observation filtration F = (F n ) n≥0 , with F 0 trivial and

F n = σ (τ k , Z k ) : 1 ≤ k ≤ n , n ≥ 1, (2.7)
where we denote by

Z n = Z τ n-1 ,τn , n ≥ 1,
the observed return process valued in (-1, ∞).

Remark 2.2 Assumption (HL) together with the independence of S and N ensures that for all n ≥ 0, the (regular) distribution of (τ n+1 , Z n+1 ) conditioned on F n is given as follows:

1. P[τ n+1 ∈ ds|F n ] = λ(s)e - R s τn λ(u)du ds
2. further conditioning on knowing the next arrival time τ n+1 , the return

Z n+1 has distribution P[Z n+1 ∈ dz|F n ∨ σ(τ n+1 )] = p(τ n , τ n+1 , dz).
In this model a (simple) trading strategy is a real-valued F-adapted process α = (α n ) n≥0 , where α n represents the amount invested in the stock over the period (τ n , τ n+1 ] after observing the stock price at time τ n . Assuming that the money market pays zero interest rate, the observed wealth process (X τn ) n≥0 associated to a trading strategy α is governed by:

X τ n+1 = X τn + α n Z n+1 , n ≥ 0, (2.8)
where X 0 is the initial capital of the investor. In order to simplify notation, we fix once and for all an initial capital X 0 > 0 and denote by A the set of trading strategies α such that the wealth process stays nonnegative:

X τn ≥ 0, n ≥ 1.
(2.9)

For the rest of the paper, we will call simple these trading strategies where trading occurs only at the discrete times τ n , n ≥ 0.

Remark 2.3 Constrained strategies. From (2.8) and the support property of Z t,s in Remark 2.1 (i), the admissibility condition (2.9) on α ∈ A means that we have a no-short sale constraint (on both the risky and savings account asset):

0 ≤ α n ≤ X τn , for all n ≥ 0. (2.10)
Moreover, since Z n > -1 a.s. for all n ≥ 1, the wealth process associated to α ∈ A 0 is actually strictly positive:

X τn > 0, n ≥ 0.
For technical reasons, some related to the asymptotic behavior in Section 4.1, we need to define some continuous time filtrations along with the discrete filtration F. To avoid confusion, we will denote by G (with different parameters) all continuous-time filtrations.

In this spirit, we define the filtration G = (G t ) 0≤t≤T generated by observing continously the process S and the arrival times as

G t = σ{(S u , N u ), 0 ≤ u ≤ t} ∨ N , 0 ≤ t ≤ T, (2.11)
where N is the inhomogenous Poisson process in (2.5) and N are all the null sets of G under the historical measure P. We would like to point out that, because of the Lévy structure of the joint process (S, N ), the filtration G is right continous, so it satisfies the usual conditions. In addition, we have the strict inclusion:

F n ⊂ G τn for all n ≥ 1.
We make an additional assumption on the model, which, among others, precludes arbitrage possibilities:

(NA) T 0 b 2 (u) c 2 (u) du < ∞.
Remark 2.4 Underssumption (NA), we can define the probability measure Q by

dQ dP = e - R T 0 b(u) c(u) dWu- R T 0 " b(u) c(u) " 2 du .
Under Q, the process N has the same law as under P, and (τ n ) n≥0 and (S t ) 0≤t≤T are still independent under Q. Moreover, the process S is a positive (Q, G)-local martingale so a supermartingale. This means that the discrete-time process (S τn ) n≥0 is a (Q, F) supermartingale as well.

Remark 2.5 Embedding in a continuous-time wealth process. Given α ∈ A with corresponding wealth process (X τn ) n in (2.8), let us define the continuous time process (X t ) 0≤t<T by

X t = X τn + α n Z τn,t , τ n < t ≤ τ n+1 , n ≥ 0, = X 0 + t 0 H u dS u , 0 ≤ t < T, (2.12)
where H is the simple and G-predictable process

H t = ∞ n=0 α n S τn I {τn<t≤τ n+1 } , 0 ≤ t < T,
representing the number of shares invested in the risky asset. From (2.10) and since S t > 0, so Z τn,t > -1, n ≥ 0, we notice that the continuous time process X is strictly positive: X t > 0 for 0 ≤ t < T . Moreover, according to Remark 2.4, (X t ) 0≤t<T is a (Q, G)-local martingale, hence a super-martingale up to T . Consequently, we also have X t-> 0 for 0 ≤ t < T . We would like to point out that the definition of X τn in (2.8) is consistent with (2.12), so (X τn ) n≥0 is a positive F-supermartingale under Q. Therefore, for each α ∈ A we may define the terminal wealth value by:

X T = lim n→∞ X τn = lim tրT X t = X 0 + ∞ n=0 α n Z n+1 ,
and, since S T = S T -we also have

X T = X 0 + T 0 H u dS u ,
where the integrand H is related to the simple trading strategy α as described above. The supermartingale property implies the budget constraint

E Q [X T ] ≤ X 0 .
The continuous time wealth process X has the meaning of a shadow wealth process: it is not observed except for at times τ n , n ≥ 0. The no-short sale constraints (2.10) is translated in terms of the number of shares held as

0 ≤ H t S t-≤ X t-, 0 ≤ t < T. (2.13)
We denote by X the set of all wealth processes (X t ) 0≤t≤T given by (2.12), by using simple trading strategies under the no-short sale constraint (2.10)/(2.13). We denote by X the set of all positive wealth processes (X t ) 0≤t≤T given by (2.12), by using general Gpredictable and S-integrable processes H satisfying (2.13). We clearly have X ⊂ X .

For technical reasons, it is sometimes convenient to regard trading strategies equivalently in terms of proportions of wealth. For any continuous time wealth process X ∈ X associated to a trading strategy H satisfying (2.13), let us consider the process π = (π t ) 0≤t≤T , defined by: π t = H t S t-/X t-, and notice that π is valued in [0, 1] by (2.13). We stress the dependence of the wealth on the proportion π, and denote by X (π) = X, which is then written in a multiplicative way as

X (π) . = X 0 E . 0 π dS S- = X 0 E . 0 πdL , (2.14)
where E is the Doléans-Dade operator. Denote by

D(G) the set of all G-predictable pro- cesses π valued in [0, 1]. It is then clear that X = {X (π) | π ∈ D(G)}.

Optimal investment problem and dynamic programming

We investigate an optimal investment problem in the illiquid market described in the previous section. Let us consider an utility function U defined on (0, ∞), strictly increasing, strictly concave and C 1 on (0, ∞), and satisfying the Inada conditions:

U ′ (0 + ) = ∞, U ′ (∞) = 0.
We make the following additional assumptions on the utility function U :

(HU) (i) there exist some constants C > 0 and p ∈ (0, 1) such that

U + (x) ≤ C(1 + x p ), (∀) x > 0
where U + = max(U, 0) (ii) Either U (0) > -∞, or U (0) = -∞ and there exist some constants C ′ > 0 and p ′ < 0 such that

U -(x) ≤ C(1 + x p ′ ), (∀) x > 0,
where U -= max(-U, 0). The above assumptions include most popular utility functions, in particular those with constant relative risk aversion 1p > 0, in the form U (x) = (x p -1)/p, x > 0.

Given the chosen positive initial wealth X 0 > 0, we consider the optimal investment problem:

V 0 = sup α∈A E[U (X T )] = sup X∈X E[U (X T )]. (3.1)
Our aim is to provide an analytic solution to the control problem (3.1) using direct dynamic programming, i.e. first solve the Dynamic Programming Equation (DPE) analytically and then perform a verification argument. Therefore, there is no need to either define the value function at later times or to prove the Dynamic Programming Principle (DPP).

The Lemma below provides the intuition behind the (DPE):

Lemma 3.1 Assume (HL) holds true. Let α ∈ A and let (X τn ) n≥0 be the wealth process associated with the trading strategy α. Consider a measurable function

v : [0, T ) × (0, ∞) → R. For a fixed n ≥ 0, if v(τ n+1 , X τ n+1 ) ∈ L 1 (Ω, G, P), then E[v(τ n+1 , X τ n+1 )|F n ] = T τn (-1,∞) λ(s)e - R s τn λ(u)du v(s, X τn + α n z)p(τ n , s, dz)ds,
where the above equality holds P-a.s.

Proof. From Remark 2.2 we have

E[v(τ n+1 , X τ n+1 )|F n ] = E E[v(τ n+1 , X τn + α n Z n+1 )|F n ∨ σ(τ n+1 )] F n = E (-1,∞) v(τ n+1 , X τn + α n z)p(τ n , τ n+1 , dz) F n = T τn (-1,∞) λ(s)e - R s τn λ(u)du v(s, X τn + α n z)p(τ n , s, dz)ds. 2
Taking into account the above Lemma, we can now formally write down the Dynamic Programming Equation as

v(t, x) = sup a∈[0,x] T t (-1,∞) λ(s)e - R s t λ(u)du v(s, x + az)p(t, s, dz)ds, = sup π∈[0,1] T t (-1,∞) λ(s)e - R s t λ(u)du v(s, x(1 + πz))p(t, s, dz)ds, (3.2)
for all (t, x) ∈ [0, T ) × (0, ∞) together with the natural terminal condition

lim tրT,x ′ →x v(t, x ′ ) = U (x), x > 0. (3.
3)

It appears that the right space of functions to be looking for a solution of (3.2)-(3.3) is actually the space C U ([0, T ) × (0, ∞)) of measurable functions w on [0, T ) × (0, ∞), such that 1. w(t, .) is concave on (0, ∞) for all t ∈ [0, T ), and 2. for some C = C(w) > 0, we have

U (x) ≤ w(t, x) ≤ C(1 + x), ∀(t, x) ∈ [0, T ) × (0, ∞). (3.4)
For any w ∈ C U ([0, T ) × (0, ∞)), we consider the measurable function Lw on [0, T ) × (0, ∞) defined by:

Lw(t, x) = sup π∈[0,1] T t (-1,∞) λ(s)e -
L : C U ([0, T ) × (0, ∞)) → C U ([0, T ) × (0, ∞)),
is well defined. Therefore, we are looking for a a solution w ∈ C U ([0, T ) × (0, ∞)) to the DPE:

Lw = w lim tրT,x ′ →x w(t, x ′ ) = U (x). (3.6)
In order to solve the DPE and perform the verification argument, we need some technical details collected in the subsection below:

3.1 A supersolution of the DPE and other technical details Lemma 3.2 Assume that (HL) holds. For any

w ∈ C U ([0, T ) × (0, ∞)), Lw also belongs to C U ([0, T ) × (0, ∞)). For each (t, x) ∈ [0, T ) × (0, ∞) the supremum in (3.5
) is attained at some π(t, x) which can be chosen measurable in (t, x).

Proof. Given w ∈ C U ([0, T ) × (0, ∞)), let us consider the measurable function w defined on [0, T ) × (0, ∞) × [0, 1] by:

w(t, x, π) = T t (-1,∞) λ(s)e - R s t λ(u)du w(s, x(1 + πz))p(t, s, dz)ds,
so that Lw(t, x) = sup π∈[0,1] w(t, x, π). Observe from (3.4) and the integrability condition in Remark 2.1 (ii) that ŵ is well-defined on [0, T ) × (0, ∞) × [0, 1] and satisfies:

-∞ ≤ w(t, x, π) ≤ C(1 + x), ∀(t, x, π) ∈ [0, T ) × (0, ∞) × [0, 1], (3.7)
for some positive constant C > 0 and, by (3.4), for each (t, x) ∈ [0, T ) × (0, ∞), we have

w(t, x, 0) ≥ U (x). (3.8)
As a matter of fact, one can easily see that w(t, x, π) is actually finite for any π ∈ [0, 1) and may only equal negative infinity for π = 1. Consequently, for fixed (t, x) ∈ [0, T ) × (0, ∞), w(t, x, .) is a proper one-dimensional concave function defined on [0, 1] (concavity follows easily from that of w). In addition, using the linear growth (3.4) together with Fatou lemma, we obtain that π ∈ [0, 1] → w(t, x, π) is upper semicontinuous (this refers to the endpoints π = 0, 1 since the function is continuous on (0, 1) being finite and concave). Therefore Lw(t, x) = max π∈[0,1] w(t, x, π), where the maximum is attained at some π = π(t, x) which can be chosen measurable in (t, x), see e.g. Ch. 11 in [START_REF] Bertsekas | Stochastic optimal control: the discrete-time case[END_REF]. In addition, since π → w(t, x, π) is continuous on (0, 1), the function Lw has the additional representation

Lw(t, x) = sup π∈[0,1]∩Q w(t, x, π),
which shows that Lw is measurable. The concavity of w(t, .) implies the concavity of (x, a)

∈ {(x, a) ∈ (0, ∞) × R : a ∈ [0, x]} → w(t,
x, a/x) for all t ∈ [0, T ). This easily implies that Lw(t, .) is also concave on (0, ∞) for all t ∈ [0, T ). Finally, it is clear from (3.7) and (3.8) that Lw satisfies also the growth condition:

U (x) ≤ Lw(t, x) ≤ C(1 + x), ∀(t, x) ∈ [0, T ) × (0, ∞).
f (t, x) = inf y>0 E[ Ũ (yY t,T )] + yx (t, x) ∈ [0, T ] × (0, ∞),
where

Y t,T = e - R T t b(u) c(u) dWu- R T t " b(u) c(u) " 2 du , (3.9)
and Ũ is the Fenchel-Legendre transform of U :

Ũ (y) = sup x>0 [U (x) -xy] < ∞, ∀y > 0. (3.10)
Then, f lies in the set C U ([0, T ) × (0, ∞)), and satisfies

Lf ≤ f lim tրT,x ′ →x f (t, x ′ ) = U (x). (3.11)
Proof. Jensen's inequality gives E[ Ũ (yY t,T )] ≥ Ũ (y), so

f (t, x) ≥ inf y>0 Ũ (y) + yx = U (x).
From the definition of f we know that

f (t, x) ≤ E[ Ũ(yY t,T )] + yx, (∀) y > 0. (3.12)
Fix a y 0 > 0. Jensen's inequality together with Assumption (HU)(i) shows that

E[ Ũ (y 0 Y t,T )] ≤ E[ Ũ (y 0 Y 0,T )] < ∞, so f (t, x) ≤ E[ Ũ (y 0 Y t,T )] + y 0 x ≤ C(1 + x) (∀) (t, x) ∈ [0, T ] × (0, ∞).
This shows that f ∈ C U ([0, T ) × (0, ∞)). Using assumption (HU) (both (i) and (ii)) and the expression (3.9) we see that lim tրT E[ Ũ(yY t,T )] = Ũ (y), (∀) y > 0.

We can now use this in (3.12) to deduce that

U (x) ≤ lim inf tրT,x ′ →x f (t, x ′ ) ≤ lim sup tրT,x ′ →x f (t, x ′ ) ≤ Ũ (y) + xy, (∀) y > 0.
Taking the infimum over y we obtain the terminal condition. For each fixed t, the function f (t, •) is finite and concave on (0, ∞), so the only thing left to check is the supersolution property. Fix 0 ≤ t ≤ s ≤ T and x > 0. Denote by h(z) = E[ Ũ (zY s,T )] and fix y > 0 and π ∈ [0, 1]. By the very definition of the function f we have that

f (s, x(1 + πZ t,s )) ≤ h(yY t,s ) + x(1 + πZ t,s )yY t,s .
Using independence and the definition of h, we obtain

E[f (s, x(1 + πZ t,s ))] ≤ E[h(yY t,s ) + x(1 + πZ t,s )yY t,s ] = = E[ Ũ (yY t,s Y s,T )] + E[x(1 + πZ t,s )yY t,s ] ≤ E[ Ũ(yY t,T )] + xy.
Taking the inf over all y and recalling the definition of f (t, x) we obtain

f (t, x) ≥ E[f (s, x(1 + πZ t,s ))] = (-1,∞) f (s, x(1 + πz))p(t, s, dz)
for all π and s. For a fixed π, we can integrate over s to obtain

f (t, x) ≥ T t (-1,∞) λ(s)e - R s t λ(u)du f (s, x(1 + πz))p(t, s, dz)ds,
and then taking the supremum over π we obtain f (t, x) ≥ (Lf )(t, x), so the proof is complete. We would like to point out that, due to the linear growth condition on f , as well as Remark 2.1 (ii), all expectations/integrals above are well defined, but may be negative infinity. In other words, the positive parts in all expectations/integrals are actually integrable. 2

Remark 3.1 We would like to point out that the whole analysis in this paper extends to the case when the Brownian part of the process L is degenerate, as long as the jumps have full support on (-1, ∞) and the jump measure allows for a martingale measure with density process Y that can replace the definition (3.9) in the corresponding proofs. In other words, the assumptions (HL) and (NA) can be relaxed to include the situation when the drift can be removed by changing the jump measure appropriately, if the Gaussian part is missing.

It turns out that, for the verification arguments below, we also need an assumption on the integrability of jumps. (HI): (i) there exists q > 1 such that

T 0 ∞ 0 (1 + y) q -1 -qy ν(dt, dy) < ∞.
(ii) If the utility function U satisfies U (0) = -∞ , then there exists r < p ′ < 0 (where p ′ is given in (HU)(ii)) such that

T 0 0 -1 (1 + y) r -1 -ry ν(dt, dy) < ∞.
(iii) there are no predictable jumps, i.e. ν({t}, (-1, ∞)) = 0 for each t Remark 3.2 Using convexity, it is an easy exercise to see that assumption (HI) (i) can actually be rephrased as ν q ([0, T ]) < ∞, and assumption (HI)(ii) as ν r ([0, T ]) < ∞ where

ν l (dt) = ∞ -1 sup π∈[0,1]
(1 + πy) l -1lπy ν(dt, dy).

We now prove a crucial uniform integrability condition, but before that we denote by T the set of random times 0 ≤ τ < T which are stopping times with respect to the filtration G.

Lemma 3.4 Assume that (HL), (HU), (NA) and (HI) hold.

(1) For any X ∈ X , the family (f + (τ, X τ )) τ ∈T is uniformly P-integrable.

(2) For any X ∈ X , the family (U -(X τ )) τ ∈T , is uniformly P-integrable.

Proof. Assume ν l ([0, T ]) < ∞ for some l. Consider X = X (π) ∈ X for some π ∈ D(G), and recall that dX

(π) t = π t X (π) t-dL t , 0 ≤ t ≤ T.
(3.13)

In order to simplify notation, we supress the upper indices of X. We apply Itô formula to (X t ) l to conclude that

X l t = x l + t 0 (X u-) l lπ u b(u) + l(l -1)c 2 (u)π 2 (u) du + t 0 ∞ -1 (X u-) l (1 + π u y) l -1 -lπ u y ν(du, dy) + ′′ local martingale ′′ Fix a stopping time τ ∈ T . If T ′
n is a sequence of localizing stopping times for the local martingale part, denote by

T n = T ′ n ∧ { inf t : (X t ) l ≥ n}.
Observe that T n ր T a.s. since X -is locally bounded and locally bounded away from zero. We then have, for each 0

≤ t < T , E[(X t∧τ ∧Tn ) l ] = x l + E t∧τ ∧Tn 0 (X u-) l lπ u b(u) + l(l -1)c 2 (u)π 2 (u) du + ∞ -1
(1 + π u y) l -1lπ u y ν(du, dy)

≤ x l + E t∧τ ∧Tn 0 (X u-) l |lb(u)| + |l(l -1)c 2 (u)| du + ν l (du) (3.14) Since (X u-) l ≤ n for 0 ≤ u ≤ τ ∧ T n and ν l ([0, T ]) < ∞, we conclude that E[(X t∧τ ∧Tn ) l ] < ∞, 0 ≤ t < T.
(3.15)

In addition, since the paths of the process X l are RCLL and ν l ({u}) = 0 for each 0 ≤ u ≤ T (because of (HI) part (iii)), we have that, for each 0 ≤ t < T , with P-probability one

t∧τ ∧Tn 0 (X u-) l |lb(u)| + |l(l -1)c 2 (u)| du + ν l (du) = t∧τ ∧Tn 0 (X u ) l |lb(u)| + |l(l -1)c 2 (u)| du + ν l (du) ≤ t 0 (X u∧τ ∧Tn ) l |lb(u)| + |l(l -1)c 2 (u)| du + ν l (du) .
Replacing this in (3.14) and using Fubini, we obtain

E[(X t∧τ ∧Tn ) l ] ≤ x l + t 0 E[(X u∧τ ∧Tn ) l ] |lb(u)| + |l(l -1)c 2 (u)| du + ν l (du) . (3.16)
Now, using (3.15) and ν l ([0, T ]) < ∞, we can apply Gronwall in (3.16) to conclude that E[(X t∧τ ∧Tn ) l ] ≤ M (l) < ∞, for each 0 ≤ t < T , where M (l) does not depend on τ or n.

Letting n → ∞ and t → T , by Fatou, we obtain E[(X τ ) l ] ≤ M (l) for each stopping time τ ∈ T . We can finish the proof considering l = q for item (i) and l = r for item (ii), and also using the upper bound f (t, x) ≤ C(1 + x) as well as Assumption (HU) part (ii). 2

Remark 3.3 In case U (0) = -∞, we can follow the arguments in the Proof of Lemma 3.4 for the case π = 1 and l = r (taking into account that X t = X 0 S t for 0 ≤ t < T ) to conclude that

E[(S t ) r ] = E[(1 + Z 0,t ) r ] ≤ C(0) < ∞ for 0 ≤ t < T.
(we assumed that S 0 = 1 above, and we also used that the times 0 ≤ t < T , because are deterministic, belong to T ). The same argument actually works if we start at any time 0 ≤ t < T , so we have

E[(1 + Z t,s ) r ] = (-1,∞) (1 + z) r p(t, s, dz) ≤ C(t) < ∞, for t ≤ s < T.

Construction of a solution for the DPE

We provide a constructive proof for the existence of a solution of (3.6) using an iteration scheme. Let us define inductively the sequence of functions

(v m ) m in C U ([0, T ) × (0, ∞)) by: v 0 = U, v m+1 = Lv m , m ≥ 0.
Lemma 3.5 Assume (HL), (NA), and (HU). Then the sequence of functions v m satisfies

v m ≤ v m+1 ≤ f, m ≥ 0.
Proof. We do the proof by induction. We obviously have U = v 0 ≤ v 1 . In addition, since the operator L is monotone and U ≤ f we have

v 1 = LU ≤ Lf ≤ f,
so the statement is true for m = 0. Assume now the statement is true for m. We use again the monotonicity of L to get

v m+2 = Lv m+1 ≥ Lv m = v m+1 , v m+2 = Lv m+1 ≤ Lf ≤ f, so the proof is finished. 2
Under the conditions of the above Lemma, the nondecreasing sequence (v m ) m converges pointwise, and we may define

v * = lim m→∞ v m ≤ f.
(3.17)

We show next that v * satisfies the fixed point DP equation.

Theorem 3.1 Assume that (HL), (NA), (HU) and (HI) hold. Then, v * is solution to the fixed point DP (3.6).

Proof. Fix π ∈ [0, 1]. We know by construction that

v m+1 (t, x) ≥ T t (-1,∞) λ(s)e - R s t λ(u)du v m (s, x(1 + πz))p(t, s, dz)ds. If 0 ≤ π < 1, then v m (s, x(1 + πz) ≥ U (x(1 -π)
) so the integral on the right hand side is clearly finite. If π = 1, according to Remark 3.3, the integral on the right hand side is still finite for each m ≥ 0. Therefore, we can let m ր ∞ and use the monotone convergence theorem to obtain

v * (t, x) ≥ T t (-1,∞) λ(s)e - R s t λ(u)du v * (s, x(1 + πz))p(t, s, dz)ds.
Since this happens for each π, taking the supremum over π we get v * ≥ Lv * . Conversely, for ε > 0 there exists m such that v * (t, x)ε ≤ v m+1 (t, x) and (because of convexity the maximum is attained)

π m (t, x) such that v m+1 (t, x) = T t (-1,∞) λ(s)e - R s t λ(u)du v m (s, x(1 + π m (t, x)z))p(t, s, dz)ds. Since v m ≤ v * it follows that v * (t, x) -ε ≤ T t (-1,∞) λ(s)e - R s t λ(u)du v * (s, x(1 + π m (t, x)z))p(t, s, dz)ds ≤ Lv * (t, x).
Letting ε → 0 we obtain v * = Lv * . Finally, since U (t, x) ≤ v * (t, x) ≤ f (t, x) and the function f satisfies the boundary condition (3.3) by Lemma 3.3, we conclude that v * is a solution to the fixed point DP equation (3.6). 2

Remark 3.4 The previous theorem shows the existence of a fixed point to the DP equation (3.6), and gives also an iterative procedure for constructing a fixed point. In the next subsection, we shall prove that such a fixed point is equal to the value function v, which implies in particular the uniqueness for the fixed point equation (3.6).

Verification and optimal strategies

Consider the solution v * to the fixed point DP equation (3.6), constructed in Theorem 3.1. We now state a verification theorem for the fixed point equation (3.6), which provides the optimal portfolio strategy in feedback form.

Theorem 3.2 Assume that (HL), (NA), (HU) and (HI) hold. Then,

V 0 = v * (0, X 0 ),
and an optimal control α ∈ A is given by αn = π(τ n , Xτn ) Xτn , n ≥ 0, (3.18) where π is a measurable function on [0, T ) × (0, ∞) solution to Proof. Consider α ∈ A and the corresponding positive wealth process (X τn ) n≥0 . From Lemma 3.4, we know that

π(t, x) ∈ arg max π∈[0,1] T t (-1,∞) λ(s)e -
E[|v * (τ n , X τn )|] < ∞, (∀) n ≥ 0.
We apply Lemma 3.1 to get for any n ≥ 0:

E[v * (τ n+1 , X τ n+1 )|F n ] = T τn (-1,∞) λ(s)e - R s τn λ(u)du v * (s, X τn + α n z)p(τ n , s, dz)ds ≤ Lv * (τ n , X τn ) = v * (τ n , X τn ), (3.19)
so the process {v * (τ n , X τn ), n ≥ 0} is a (P, F)-supermartingale. Recalling that v * (t, .) ≥ U we obtain

E[U (X τn )] ≤ E[v * (τ n , X τn )] ≤ v * (0, X 0 ), (∀) n ≥ 0.
Now, by Lemma 3.4, the sequence (U (X τn )) n is uniformly integrable. By sending n to infinity into the last inequality, we then get

E[U (X T )] ≤ v * (0, X 0 ).
Since α is arbitrary, we obtain V 0 ≤ v * (0, X 0 ). Conversely, let α ∈ A be the portfolio strategy given by (3.18), and ( Xτn ) n≥0 the associated wealth process. Then, by the same calculations as in (3.19), we have now the equalities:

E[v * (τ n+1 , Xτ n+1 )|F n ] = T τn (-1,∞) λ(s)e - R s τn λ(u)du v * (s, X τn + αn z)p(τ n , s, dz)ds = Lv * (τ n , Xτn ) = v * (τ n , Xτn ), n ≥ 0,
by definition of L and α. This means that the process {v * (τ n , Xτn ), n ≥ 0} is a (P, F)martingale, and so:

E[v * (τ n , Xτn )] = v * (0, X 0 ), (∀) n ≥ 0.
From the the bounds U ≤ v * ≤ f and Lemma 3.4, we know that the sequence (v * (τ n , Xτn )) n is uniformly integrable. By sending n to infinity into the last equality, and recalling the terminal condition for v * , we then get

E[U ( XT )] = v * (0, X 0 ).
Together with the inequality, V 0 ≤ v * (0, X 0 ), this proves that V 0 = v * (0, X 0 ) and α is an optimal control. 2

An identical verification argument to the proof of Theorem 3.2 can be performed for an investor starting at time t with initial capital x: this way we prove that v * is actually the value function of the control problem. In addition, this shows that the Dynamic Programming Equation (3.6) has a unique solution. For the sake of avoiding the heavy notation associated with strategies starting at time t, we decided to only do the verification for time t = 0.

The Proposition below shows that actually we can approximate the optimal control, and not only the maximal expected utility, using a finite number of iterations. The approximate optimal control is actually very simple, since after the m-th arrival time all the wealth is invested in the money market. In addition, a stochastic control representation for the iteration v m is provided.

v m-n (t, x) = T t (-1,∞) λ(s)e - R s t λ(u)du v m-n-1 (s, x(1 + π n (t, x)z))p(t, s, dz)ds.
Define in feedback form the admissible strategy αm ∈ A m by α m n = πn (τ n , Xm τn ) Xm τn for 0 ≤ n ≤ m -1 and α m n = 0 for n ≥ m, where the wealth processes ( Xm τn ) n≥0 is given by

Xm τ n+1 = Xm τn + αm n Z n+1 , 0 ≤ n ≤ m -1, Xm τn = Xm τm , n ≥ m,
starting from the initial wealth X 0 . Then α m ∈ A m is an optimal control for (3.20).

Proof. The proof is based on similar arguments to the proof of Theorem 3.2. Namely, for each α ∈ A m , one can use Lemma 3.1 to conclude that (v m-n (τ n , X n )) n=0,1,...,m is a supermartingale and, for the particular choice of the control α m described above we actually have that (v m-n (τ n , Xm n )) n=0,1,...,m is a true martingale. Since v 0 (t, x) = U (x) and for each α ∈ A m the wealth process X is constant after the arrival time τ m , it is easy to finish the proof. 2

Theorems 3.1 and 3.2 together show how we can compute by iterations the maximal expected utility and the optimal control. Since the control problem is finite-horizon in time and infinite horizon in n, taking into account Proposition 3.1, the iteration procedure represents exactly the approximation of the infinite horizon problem by a sequence of finite horizon problems.

Example: the case of CRRA utility functions

In this subsection, we consider the case of CRRA (Constant Relative Risk Aversion) utility functions.

First, let us take logarithm utility functions:

U (x) = ln x, x > 0.
We easily see that in this case the value function has the form:

v(t, x) = U (x) + ϕ(t),
for some nonnegative continuous function ϕ on [0, T ) with ϕ(T -) = 0. The computation of Lv in (3.5) is straightforward:

Lv = ln x + T t λ(s)e - R s t λ(u)du ϕ(s)ds + sup π∈[0,1] T t λ(s)e - R s t λ(u)du (-1,∞)
ln(1 + πz)p(t, s, dz) ds.

Hence, we see that v is a solution to the fixed point equation: Lv = v iff ϕ satisfies:

ϕ(t) = T t λ(s)e - R s t λ(u)du ϕ(s)ds + F (t), t ∈ [0, T ),
where F is the function defined on [0, T ) by

F (t) = sup π∈[0,1] T t λ(s)e - R s t λ(u)du (-1,∞)
ln(1 + πz)p(t, s, dz) ds.

We next consider power utility functions:

U (x) = x γ γ , x > 0, γ < 1, γ = 0,
In this case, the value function has the form:

v(t, x) = ϕ(t)U (x),
for some continuous function ϕ on [0, T ), greater than 1, with ϕ(T -) = 1. We easily compute Lv in (3.5):

Lv = U (x) sup π∈[0,1] T t λ(s)e - R s t λ(u)du ϕ(s) (-1,∞)
(1 + πz) γ p(t, s, dz) ds.

Hence, we see that v is a solution to the fixed point equation: Lv = v iff ϕ satisfies:

ϕ(t) = sup π∈[0,1] T t λ(s)e - R s t λ(u)du ϕ(s) (-1,∞) (1 + πz) γ p(t, s, dz) ds, t ∈ [0, T ).
4 Convergence in the illiquid market model

So far, we have considered the optimal investment problem (3.1) for a fixed arrival rate function λ : [0, T ) → [0, ∞) satisfying condition (2.4). To emphasize the dependence on the arrival rate, let us denote by V λ 0 the value in (3.1). When the arrival rate is very large at all times (in some sense to be precised), one would expect that V λ 0 is very close to the optimal expected utility of an agent who can trade at all times (therefore continuously) in the asset S. It is also expected that the constraint (2.10), which is implicitly contained in the admissibility condition (2.9) in the discrete time illiquid case, becomes an explicit no-short constraint (2.13) in the continuous time limit. This section is devoted to proving that this is actually true.

First, we need to define the optimization problem for the agent who can trade continuously. We remind the reader that continuous time trading strategies can be defined by (2.12). We denote by X S the set of positive wealth processes (X t ) 0≤t≤T given by (2.12), by using G S -predictable and S-integrable processes H satisfying the no-short sale constraint (2.13). The filtration G S = (G S t ) 0≤t≤T is defined by

G S t = σ{S s , 0 ≤ s ≤ t} ∨ N ,
and represents the information one can get from following the asset S. Because of the Lévy structure of S, G S satisfies the usual conditions. We also denote by D(S) the set of all G S -predictable processes π valued in [0, 1]. It is then clear that X S = {X (π) | π ∈ D(S)}.

The optimization problem for an agent trading continuously, under no-short selling constraints can be formulated as

V M 0 = sup X∈X S E[U (X T )] = sup π∈D(S) E[U (X (π) T )]. (4.1)
The main result of this section is: Proof of Theorem 4.1. We first represent continuous time trading strategies with no short sale constraints in terms of proportion of wealth, for the larger filtration G ∞ . For any continuous time wealth process X ∈ Xc associated to a trading strategy H satisfying (2.13), we still denote by π t = H t S t -/X t-, and notice that the process (π t ) 0≤t≤T is valued in [0, 1] by (2.13). We also denote by X (π) the process defined by (2.14) and define D ∞ to be the set of all G ∞ -predictable processes π valued in [0, 1]. It is then clear that

V ∞ 0 = sup π∈D ∞ E[U (X (π)
T )].

Using Lemma 4.1 and Lemma 4.2 we have, for each intensity function λ that

V λ 0 = V λ,c 0 ≤ V ∞ 0 = V M 0 . (4.4)
Let now π ∈ D(S) ⊂ D ∞ be a (proportional) trading strategy in (4.1) and let (λ k ) k a sequence of intensity functions as in Theorem 4.1. We will follow the arguments in [START_REF] Kardaras | Multiplicative approximation of wealth processes involving no-short-sale strategies via simple trading[END_REF] to approximate this continuous time trading strategy by simple strategies α k ∈ A λ k c , which are discrete, but use information from continuous observations. First, according to Lemma 3.4 and 3.5 in [START_REF] Kardaras | Multiplicative approximation of wealth processes involving no-short-sale strategies via simple trading[END_REF], there exists a sequence π m ∈ D(S) such that each π m is LCRL (left continuous with right limits) and such that ucPlim m→∞ X (π m ) = X (π) , so, in order to approximate π we can actually assume it is LCRL. Here, by ucP-convergence, we mean the usual convergence of processes in probability, uniformly on compact time-sets.

Let us check that our sequence of stopping times satisfies the condition sup n τ k n+1τ k n → 0 a.s., k → ∞. Take a subdivision 0 = t 0 < . . . < t i < . . . < t M = T of [0, T ] such that |t i+1t i | ≤ ǫ/2, for all i. We then have :

P sup n τ k n+1 -τ k n > ǫ ≤ M -1 i=0 P ∃n, τ k n ≤ t i < t i+1 ≤ τ k n+1 = M -1 i=0 P N λ k t i = N λ k t i+1 = M -1 i=0 exp - t i+1 t i λ k (u) du .
By Borel-Cantelli and (4.2), we deduce that

P lim sup k sup n τ k n+1 -τ k n > ǫ = 0, (∀) ε > 0. (4.5)
Next, let us define π k n = π τ λ k n + , n ≥ 0, where π t+ = lim uցt π t . Because the filtration G λ k satisfies the usual conditions we have that the process (π t+ ) 0≤t≤T is optional with respect to G λ k for each k. Since, in addition, τ λ k n are stopping times with respect to G λ k we obtain that, for each k,

π k n ∈ G λ k τ λ k n , k ≥ 0. (4.6)

  u)du w(s, x(1 + πz))p(t, s, dz)ds. (3.5) Lemma 3.2 below shows that the operator

2Lemma 3 . 3

 33 The next lemma constucts a supersolution f ∈ C U ([0, T ) × (0, ∞)) for the DPE: Assume that (HL), (NA) and (HU) hold. Define

  u)du v * (s, x(1 + πz))p(t, s, dz)ds, and ( Xτn ) n≥0 is the wealth given by Xτ n+1 = Xτn + αn Z n+1 , n ≥ 0, and starting from X0 = X 0 .

Proposition 3 . 1

 31 Assume that (HL), (NA), (HU) and (HI) hold. Thenv m (0, X 0 ) = sup α∈Am E[U (X T )],(3.20)where A m is the set of admissible controls α = (α n ) ≥0 ∈ A such that all money is invested in the money market after m arrivals, i.e. α n = 0 for n ≥ m.For any 0 ≤ n ≤ m -1, consider the measurable function πn (•, •) defined by πn (t, x) = arg max u)du v m-n-1 (s, x(1 + πz))p(t, s, dz)ds, so that

Theorem 4 . 1

 41 Under Assumptions (HL), (NA), (HU) and (HI), consider (λ k ) k a sequence of intensity functions satisfying(2.4). If u) du < ∞, (∀) 0 ≤ t < s < T, (4.2) then V λ k 0 → V M 0 , as k goes to infinity,where V M 0 is defined by (4.1).

  1,∞) |z|p(t, s, dz) ≤ C, for all 0 ≤ t ≤ s < T . This means that, the expectation of the absolute value of the return is uniformly bounded in (t, s), i.e. E[|Z t,s |] ≤ C. The constant C can be chosen as C = e

	R T 0 |b(u)|du

Remark 4.1 Condition (4.2) is satisfied for example with λ k (t) = k.λ(t), where λ is an intensity function satisfying (2.4). This condition also implies that for all 0 ≤ t < s < T , s t λ k (u)du → ∞, as k goes to infinity.

In order to prove Theorem 4.1, we first have to put all the optimization problems (3.1) on the same physical probability space, independent of the intensity function λ. This is an easy task actually. We consider a probability space (Ω, G, P) supporting two independent processes: the continuous time stock price process (S t ) 0≤t≤T (which has all the desired properties) and a Poisson process (M t ) 0≤t<∞ with intensity equal to one. After that, for each intensity function λ we define the nonhomogenous Poisson process N λ (actually its sequence of jumps) by (2.5). Therefore, for different intensities, we still have the same physical space. We now denote by F and G λ the discrete and continuous time filtrations on (Ω, G, P) defined by (2.7) and (2.11) corresponding to the intensity λ, and by τ λ n the associated jump times.

The main obstacle in proving Theorem 4.1 is the fact that the filtration F λ only observes the process S at the arrival times, while the filtration G S used by the investor in (4.1) observes the stock continuously. This problem is overcome in three steps

Step 1: first, we show that in (3.1), the discrete-time filtration F λ = (F λ n ) n≥0 can be replaced by the larger filtration (G λ τ λ n ) n≥0 . In other words, due to the Markov structure of the model, an investor who can only trade at the discrete arrival times, cannot improve his/her expected utility by continuously observing the evolution of the stock between the arrival times. This is done in Lemma 4.1 below.

Lemma 4.1 Fix an intensity function λ and define

where A λ c is the set of simple admissible strategies α = (α n ) n≥0 with continuous observation, which means that for each n ≥ 0 we have α n ∈ G λ τ λ n and α satisfies the constraint (2.10) for the wealth process (X τn ) n≥0 defined by (2.8).

Then, under Assumptions (HL), (NA), (HU) and (HI), we have

Proof. Similarly to Remark 2.2, Assumption (HL) together with the independence of S and N ensures that for all n ≥ 0, the (regular) distribution of (τ n+1 , Z n+1 ) conditioned on G λ τ λ n is given by:

2. further conditioning on knowing the next arrival time τ λ n+1 , the return

Therefore, in Lemma 3.1, one can replace the filtration F λ by the larger filtration (G λ τ λ n ) n≥0 and obtain that, for each α ∈ A λ c we have

After that, one can just follow the verification arguments in the proof of Theorem 3.2 to show that

which ends the proof. 2

Step 2: we define the continuous time filtration

0≤t≤T which contains all the information from the arrival times right at time zero. This corresponds to an investor who knows in advance all the jumps of the homogeneous Poisson process M and also observes continuously the stock S up to time t:

Because the information added is independent, the process S is still a semimartingale with respect to the larger filtration G ∞ , which satisfies the usual conditions as well. Using again the independence property, Lemma 4.2 below shows that if the investor in (4.1) has the additional information in G ∞ , he/she cannot improve the maximal expected utility.

Lemma 4.2 Consider the set Xc of wealth processes defined by (2.12) where the general integrand H is G ∞ -predictable, S-integrable and satisfies (2.13). Define

.

Proof. Since X S ⊂ Xc , we obviously have V M 0 ≤ V ∞ 0 . Now take some arbitrary X ∈ Xc associated to a no-short sale trading strategy H, which is G ∞ -predictable. Consider the G S -predictable projection of H:

This means that the process X lies in X S . Since U is concave, we get by the law of iterated conditional expectations and Jensen's inequality

We conclude from the arbitrariness of X in Xc . 2

Step 3: Once we prove the step above and transform the Merton problem in a utility maximization problem with no short-sale constraints under the filtration G ∞ , we can basically follow the arguments in Theorems 3.1, 3.3 and 4.1 in [START_REF] Kardaras | Multiplicative approximation of wealth processes involving no-short-sale strategies via simple trading[END_REF], to finish the proof.

Therefore, if we define, for each fixed k the discrete-time wealth process by

and denote by

To each of the above defined α k , we can associate by Remark 2.5 a continuous time simple integrand H k which is G λ k -predictable and the continuous time wealth process (X k t ) 0≤t≤T . The fundamental observation is now that all H k are predictable with respect to the same "large" filtration G ∞ . Using this universal filtration, we can now follow the proof of Theorem 3.1 in [START_REF] Kardaras | Multiplicative approximation of wealth processes involving no-short-sale strategies via simple trading[END_REF], which actually works for stochastic partitions under condition (4.5), to conclude that

Therefore, we can approximate any continuous time strategy in the Merton problem (4.1) by simple trading strategies α k ∈ A λ k c . The rather obvious details on how approximation of strategies leads to approximation of optimal expected utility are identical to the arguments in [START_REF] Kardaras | Multiplicative approximation of wealth processes involving no-short-sale strategies via simple trading[END_REF] Section 4, and are omitted: this means that for all π ∈ D(S), E[U (X (π)

T )], and so V M 0 ≤ lim inf k V λ k ,c 0 . Together with (4.4), this concludes the proof of Theorem 4.1.

2


Pierre Marza
email: pierre.marza@insa-lyon.fr

Olivier Simonin
email: olivier.simonin@insa-lyon.fr

Teaching Agents how to Map: Spatial Reasoning for Multi-Object Navigation

Pierre Marza 1 , Laetitia Matignon 2 , Olivier Simonin 3 and Christian Wolf 4 Abstract-In the context of visual navigation, the capacity to map a novel environment is necessary for an agent to exploit its observation history in the considered place and efficiently reach known goals. This ability can be associated with spatial reasoning, where an agent is able to perceive spatial relationships and regularities, and discover object characteristics. Recent work introduces learnable policies parametrized by deep neural networks and trained with Reinforcement Learning (RL). In classical RL setups, the capacity to map and reason spatially is learned end-to-end, from reward alone. In this setting, we introduce supplementary supervision in the form of auxiliary tasks designed to favor the emergence of spatial perception capabilities in agents trained for a goal-reaching downstream objective. We show that learning to estimate metrics quantifying the spatial relationships between an agent at a given location and a goal to reach has a high positive impact in Multi-Object Navigation settings. Our method significantly improves the performance of different baseline agents, that either build an explicit or implicit representation of the environment, even matching the performance of incomparable oracle agents taking ground-truth maps as input. A learning-based agent from the literature trained with the proposed auxiliary losses was the winning entry to the Multi-Object Navigation Challenge, part of the CVPR 2021 Embodied AI Workshop.

I. INTRODUCTION

Navigating in a previously unseen environment requires different abilities, among which is mapping, i.e. the capacity to build a representation of the environment. The agent can then reason on this map and act efficiently towards its goal. How biological species map their environment is still an open area of research [START_REF] Peer | Structuring knowledge with cognitive maps and cognitive graphs[END_REF], [START_REF] Warren | Wormholes in virtual space: From cognitive maps to cognitive graphs[END_REF]. In robotics, spatial representations have taken diverse forms, for instance metric maps [START_REF] Elfes | Using occupancy grids for mobile robot perception and navigation[END_REF], [START_REF] Bresson | Simultaneous localization and mapping: A survey of current trends in autonomous driving[END_REF] or topological maps [START_REF] Shatkay | Learning topological maps with weak local odometric information[END_REF], [START_REF] Thrun | Learning metric-topological maps for indoor mobile robot navigation[END_REF]. Most of these variants have lately been presented in neural counterparts, i.e. involving artificial neural networks -metric neural maps [START_REF] Parisotto | Neural map: Structured memory for deep reinforcement learning[END_REF], [START_REF] Beeching | Egomap: Projective mapping and structured egocentric memory for deep RL[END_REF], [START_REF] Henriques | Mapnet: An allocentric spatial memory for mapping environments[END_REF] or neural topological maps [START_REF] Beeching | Learning to plan with uncertain topological maps[END_REF], [START_REF] Chaplot | Neural topological slam for visual navigation[END_REF] learned from RL or with supervision.

This work focuses on improving the RL-based training strategy of autonomous agents parametrized by deep neural networks. We explore the question whether the emergence of mapping and spatial reasoning capabilities can be favored by the use of spatial auxiliary tasks that are In the context of Deep-RL for Multi-Object Navigation, two auxiliary tasks predict the direction (left) and the distance (right) to the next object to retrieve if it has been observed during the episode. The green object (square) is the current target, and other targets exist and have already been found or might be required to be found later (ex: blue object / square). Red dot: position of the agent. White and grey cells, respectively, indicate free space and obstacles. Both, the angle ϕt and the distance dt between the center of the map (i.e. the agent) and the target at time t are discretized and associated with a class label. A third sub-task is to predict if the current target has already been within the agent's field of view during the episode. related to a downstream objective. We target the problem of Multi-Object Navigation [START_REF] Wani | Multion: Benchmarking semantic map memory using multi-object navigation[END_REF], where an agent must reach a sequence of specified objects in a particular order within a previously unknown environment. Such a task is interesting because it requires an agent to recall the position of previously encountered objects it will have to reach later in the sequence. This work does not introduce a new agent architecture, but rather showcases the impact of augmenting the vanilla RL training of state-of-the-art (SOTA) agents selected in [START_REF] Wani | Multion: Benchmarking semantic map memory using multi-object navigation[END_REF] to solve the Multi-Object Navigation task. Augmenting the RL training of agents with auxiliary tasks has shown promise in many recent works introducing several variants [START_REF] Mirowski | Learning to navigate in complex env[END_REF], [START_REF] Jaderberg | Reinforcement learning with unsupervised auxiliary tasks[END_REF], [START_REF] Lample | Playing fps games with deep reinforcement learning[END_REF], [START_REF] Ye | Auxiliary tasks and exploration enable objectnav[END_REF], [START_REF] Ye | Auxiliary tasks speed up learning pointgoal navigation[END_REF]. These different formulations are presented in more details in section II. Our work belongs to the group of supervised auxiliary tasks, with an application to 3D complex and photo-realistic environments, and specifically targets the learning of mapping and spatial reasoning, which has not been the scope of previous work.

We take inspiration from behavioral studies of human spatial navigation [START_REF] Ekstrom | Human spatial navigation[END_REF]. Experiments with human subjects aim at evaluating the spatial knowledge they acquire when navigating a given environment. In [START_REF] Ekstrom | Human spatial navigation[END_REF], two important measures are referred as the sense of direction and judgement of relative distance. Regarding knowledge of direction, a wellknown task is scene-and orientation-dependent pointing (SOP), where participants must point to a specified location that is not currently within their field of view. Being able to assess its relative position compared to other objects in the world is critical to navigate properly, and disorientation is considered a main issue. In addition to direction, evaluating the distance to landmarks is also of high importance.

We conjecture that an agent able to estimate the location of target objects relative to its current pose will implicitly extract more useful representations of the environment and navigate more efficiently. A fundamental skill for such an agent is thus to remember previously encountered objects. Our auxiliary supervision targets exactly this ability. Classical methods based on RL rely on the capacity of the learning algorithm to extract mapping strategies from reward alone. While this has been shown to be possible in principle [START_REF] Beeching | Egomap: Projective mapping and structured egocentric memory for deep RL[END_REF], we will show that the emergence of a spatial mapping strategy is significantly boosted through auxiliary tasks, which require the agent to continuously reason on the presence of targets w.r.t. to its viewpoint -see Figure 1.

We introduce three auxiliary tasks, namely estimating if a target object has already been observed since the beginning of the episode, and if it is the case, the relative direction and the Euclidean distance to this object. If an object is visible in the current observation, it will be helpful for training the agent to recognize it (discover its existence and relevance to the task) and estimate its relative position. More importantly, if the target object was seen in the past, the auxiliary supervision will encourage the learning of representations of the environment, either implicitly or explicitly predicted by the agent, that are better spatially structured and populated with more relevant semantic information, leading to an update of the neural memory of the agent.

We propose the following contributions: (i) we show that the auxiliary tasks improve the performance of previous neural baselines by a large margin, which even allows to reach the performance of (incomparable) agents using ground-truth oracle maps as input; (ii) we show the consistency of the gains over different inductive biases, i.e. different ways to structure neural networks, reaching from simple recurrent models to agents structured with projective geometry. This raises the question whether spatial inductive biases are required or whether spatial organization can be learned; (iii) the proposed method reaches SOTA performance on the Multi-ON task, and corresponds to the winning entry of the CVPR 2021 Multi-ON challenge 1 . The Test-Standard leaderboard 2 , as well as an explanatory video 3 are publicly available.

II. RELATED WORK

Visual navigationhas been extensively studied in robotics [START_REF] Bonin-Font | Visual navigation for mobile robots: A survey[END_REF], [START_REF] Thrun | Probabilistic robotics[END_REF]. An agent is placed in an unknown environment and must solve a specified task involving reaching positions based on visual input, where [START_REF] Bonin-Font | Visual navigation for mobile robots: A survey[END_REF] distinguish mapbased and map-less navigation. Recently, many navigation problems have been posed as goal-reaching tasks [START_REF] Anderson | On evaluation of embodied navigation agents[END_REF]. The nature of the goal, its regularities in the environment and how it is communicated to the agent have a significant impact on required reasoning capacities of the agent [START_REF] Beeching | Deep reinforcement learning on a budget: 3d control and reasoning without a supercomputer[END_REF].

In Pointgoal [START_REF] Anderson | On evaluation of embodied navigation agents[END_REF], an agent must reach a location specified as relative coordinates, while ObjectGoal [START_REF] Anderson | On evaluation of embodied navigation agents[END_REF] requires the agent to find an object of a particular semantic category.

Recent literature [START_REF] Beeching | Deep reinforcement learning on a budget: 3d control and reasoning without a supercomputer[END_REF], [START_REF] Wani | Multion: Benchmarking semantic map memory using multi-object navigation[END_REF] introduced new navigation tasks with two important characteristics, (i) their sequential nature, i.e. an episode is composed of a sequence of goals to reach, and (ii) the use of external objects as target objectives, i.e. the objects to find are not part of the scanned 3D scenes used as environments, but are for example randomly placed coloured cylinders as in [START_REF] Wani | Multion: Benchmarking semantic map memory using multi-object navigation[END_REF].

Multi-Object Navigation (Multi-ON) [START_REF] Wani | Multion: Benchmarking semantic map memory using multi-object navigation[END_REF] is a task requiring to sequentially retrieve objects, but unlike the Ordered K-item task [START_REF] Beeching | Deep reinforcement learning on a budget: 3d control and reasoning without a supercomputer[END_REF], the order is not fixed between episodes. A sequential task is interesting as it requires the agent to remember and to map potential objects it might have seen while exploring the environment, as reasoning on them might be required in a later stage. Moreover, using external objects as goals prevents the agent from leveraging knowledge about the environment layouts, thus focusing solely on memory. Exploration is another targeted capacity as objects are placed randomly within environments. For these reasons, our work thus focuses on the new challenging Multi-ON task [START_REF] Wani | Multion: Benchmarking semantic map memory using multi-object navigation[END_REF].

Learning-free navigation -A recurrent pattern in methods tackling visual navigation [START_REF] Bonin-Font | Visual navigation for mobile robots: A survey[END_REF], [START_REF] Thrun | Probabilistic robotics[END_REF] is modularity, with different computational entities solving a particular sub-part of the problem. A module might map the environment, another one localize the agent within this map, a third one performing planning. Low-level control is also often addressed by a specialized sub-module. Known examples are based on Simultaneous Localization and Mapping (SLAM) [START_REF] Bresson | Simultaneous localization and mapping: A survey of current trends in autonomous driving[END_REF].

Learning-based navigation -The task of navigation can be framed as a learning problem, leveraging the abilities of deep networks to extract regularities from a large amount of training data. Formalisms range from Deep Reinforcement Learning (DRL) [START_REF] Mirowski | Learning to navigate in complex env[END_REF], [START_REF] Jaderberg | Reinforcement learning with unsupervised auxiliary tasks[END_REF], [START_REF] Zhu | Target-driven visual navigation in indoor scenes using deep reinforcement learning[END_REF] to (supervised) Imitation Learning [START_REF] Ding | Goal-conditioned imitation learning[END_REF]. Our work focuses on improving the training strategy of autonomous agents trained with DRL by augmenting the reward-based supervision signal with auxiliary losses that are related to the downstream task.

Such agents can be reactive [START_REF] Zhu | Target-driven visual navigation in indoor scenes using deep reinforcement learning[END_REF] , but recent work tends to augment agents with memory, which is a key component, in particular in partially-observable environments [START_REF] Hausknecht | Deep recurrent q-learning for partially observable mdps[END_REF], [START_REF] Oh | Control of memory, active perception, and action in minecraft[END_REF]. It can take the form of recurrent units [START_REF] Cho | Learning phrase repr. using RNN encoder-decoder for statistical machine translation[END_REF], or become a dedicated part of the system. In the context of navigation, memory can fulfill multiple roles: holding a latent map-like representation of the spatial properties of the environment, as well as general high-level information related to the task ("did I already see this object?"). Common representations are metric [START_REF] Parisotto | Neural map: Structured memory for deep reinforcement learning[END_REF], [START_REF] Beeching | Egomap: Projective mapping and structured egocentric memory for deep RL[END_REF], [START_REF] Henriques | Mapnet: An allocentric spatial memory for mapping environments[END_REF], or topological [START_REF] Beeching | Learning to plan with uncertain topological maps[END_REF], [START_REF] Chaplot | Neural topological slam for visual navigation[END_REF]. Other work reduces assumptions about the necessary structure of the environment representation by using Transformers [START_REF] Vaswani | Attention is all you need[END_REF] as a memory mechanism on episodic data [START_REF] Fang | Scene memory transformer for embodied agents in long-horizon tasks[END_REF].

In contrast to end-to-end training, other approaches decompose the agent into sub-modules [START_REF] Chaplot | Learning to explore using active neural slam[END_REF], [START_REF] Chaplot | Neural topological slam for visual navigation[END_REF] trained simultaneously with supervised learning [START_REF] Chaplot | Neural topological slam for visual navigation[END_REF] or a combination of supervised, reinforcement and imitation learning [START_REF] Chaplot | Learning to explore using active neural slam[END_REF].

Somewhat related to our work, in [START_REF] Chaplot | Neural topological slam for visual navigation[END_REF], a dedicated semantic score prediction module is proposed, which estimates the direction towards a goal and is explicitly used to decide which previously unexplored ghost node to visit next inside a topological memory. In contrast, in our work we propose to predict spatial metrics such as relative direction as an auxiliary objective to shape the learnt representations, instead of explicitly using those predictions at inference time.

Learning vs. learning-free -The differences in navigation performance between SLAM-based and learning-based agents have been studied before [START_REF] Mishkin | Benchmarking classic and learned navigation in complex 3d environments[END_REF], [START_REF] Savva | Habitat: A platform for embodied ai research[END_REF]. Even though trained agents begin to perform better than classical methods in recent studies [START_REF] Savva | Habitat: A platform for embodied ai research[END_REF], arguments regarding efficiency of SLAM-based methods still hold [START_REF] Mishkin | Benchmarking classic and learned navigation in complex 3d environments[END_REF], [START_REF] Sadek | An in-depth experimental study of sensor usage and visual reasoning of robots navigating in real environments[END_REF]. Frequently hybrid methods are suggested [START_REF] Chaplot | Learning to explore using active neural slam[END_REF], [START_REF] Chaplot | Neural topological slam for visual navigation[END_REF]. In contrast, we explore the question, whether mapping strategies can emerge naturally in end-to-end training through additional pretext tasks.

Auxiliary taskscan be combined with any downstream objective to guide a learning model to extract more useful representations as proposed in [START_REF] Mirowski | Learning to navigate in complex env[END_REF], [START_REF] Jaderberg | Reinforcement learning with unsupervised auxiliary tasks[END_REF] to improve, both, data efficiency and overall performance. [START_REF] Mirowski | Learning to navigate in complex env[END_REF] predict loop closure and reconstruct depth observations; Lample et al. [START_REF] Lample | Playing fps games with deep reinforcement learning[END_REF] also augment the DRQN model [START_REF] Hausknecht | Deep recurrent q-learning for partially observable mdps[END_REF] with predictions of game features in fps games. A potential drawback is the need for privileged information, which, however, is readily available in simulated environments [START_REF] Savva | Habitat: A platform for embodied ai research[END_REF]. This is also the case in our work, where we access information during training on explored areas, positions of objects and of the agent, which, of course, is also used for reward generation in classical RL.

In [START_REF] Jaderberg | Reinforcement learning with unsupervised auxiliary tasks[END_REF], unsupervised objectives are introduced, such as pixel or action features and reward prediction. [START_REF] Ye | Auxiliary tasks speed up learning pointgoal navigation[END_REF] introduce self-supervised auxiliary tasks to speed up the training on PointGoal. They augment the base agent from [START_REF] Wijmans | Dd-ppo: Learning near-perfect pointgoal navigators from 2.5 billion frames[END_REF] with an inverse dynamics estimator as in [START_REF] Pathak | Curiosity-driven exploration by self-supervised prediction[END_REF], a temporal distance predictor, and an action-conditional contrastive module, which must differentiate between positives, i.e. real observations that occur after the given sequence, and negatives, i.e. observations sampled from other timesteps. [START_REF] Ye | Auxiliary tasks and exploration enable objectnav[END_REF] introduce auxiliary tasks for ObjectGoal, building on top of [START_REF] Ye | Auxiliary tasks speed up learning pointgoal navigation[END_REF] and introduce the action distribution prediction and generalized inverse dynamics tasks and coverage prediction.

Our work belongs to the group of supervised auxiliary tasks, with an application to 3D complex and photo-realistic environments, which was not the case of most concurrent methods. We also specifically target the learning of mapping and spatial reasoning through additional supervision, which has not been the scope of previous approaches.

III. LEARNING TO MAP

We target the Multi-ON task [START_REF] Wani | Multion: Benchmarking semantic map memory using multi-object navigation[END_REF], where an agent is required to reach a sequence of target objects, more precisely coloured cylinders, in a certain order, and which was used for a recent challenge organized in the context of the CVPR 2021 Embodied AI Workshop. Compared to much easier tasks like PointGoal or (Single) Object Navigation, Multi-ON requires more difficult reasoning capacities, in particular mapping the position of an object once it has been seen. The following capacities are necessary to ensure optimal performance: (i) mapping the object, i.e. storing it in a suitable latent memory representation; (ii) retrieving this location on request and using it for navigation and planning, including deciding when to retrieve this information, i.e. solving a correspondence problem between sub-goals and memory representation.

The agent deals with sequences of objects that are randomly placed in the environment. At each time step, it only knows the class of the next target, which is updated when reached. The episode lasts until either the agent has found all objects in the correct order or the time limit is reached.

A. SOTA agents in Multi-ON

Our contribution is independent of the actual implementation choices in agents solving the Multi-ON task as we rather target an improvement of the learning objective. We therefore explored several neural baselines with different architectures, as selected in [START_REF] Wani | Multion: Benchmarking semantic map memory using multi-object navigation[END_REF]. The considered agents share a common base shown in Figure 2, which extracts information from the current RGB-D observation of the robot with a convolutional neural network (CNN) f o , and computes embeddings of the target object class and the previous action taken by the agent. Differences between the considered baselines is in their representation of the environment. The simplest recurrent baseline NoMap does not construct a map of its environment. OracleMap and OracleEgoMap baselines do not build a global map, but rather have access to oracle global maps of the environment containing channels for occupancy information and location of goal objects. Finally, ProjNeuralMap builds a map of the environment in real time, associating feature vectors from f o with discrete cells in the spatial 2D representation using projective geometry. In variants that keep a global map, i.e. all except NoMap, it is first transformed into an egocentric representation centered around the agent's position (explained further below). A vector representation of the map is then extracted using another CNN f m . Such operation can be considered as a global read of the map. The vector representations are concatenated and fed to a GRU [START_REF] Cho | Learning phrase repr. using RNN encoder-decoder for statistical machine translation[END_REF] unit that integrates temporal information, and whose output serves as input to an actor and a critic heads, that respectively output a distribution over the set of actions to take and an estimation of the value of the state the agent is currently in. All agents are trained with the same RL algorithm (and same training hyper-parameter values) detailed in subsection III-C, as well as the actor-critic formulation.

We present here in more details the considered variants which have been explored in [START_REF] Wani | Multion: Benchmarking semantic map memory using multi-object navigation[END_REF], but which have been introduced in prior work (numbers ➀➁➂➃ correspond to choices in Figure 2):

NoMap ➀is a recurrent GRU baseline that does not explicitly build nor read a spatial map. The only memory available for storing mapping information is the flat vectorial hidden state of the GRU [START_REF] Cho | Learning phrase repr. using RNN encoder-decoder for statistical machine translation[END_REF], a variant of a recurrent neural network. While the agent could in principle still learn (through RL) to use this vectorial memory like a spatial map, this is in no way enforced through any design choice.

ProjNeuralMap ➀➁ [START_REF] Henriques | Mapnet: An allocentric spatial memory for mapping environments[END_REF], [START_REF] Beeching | Egomap: Projective mapping and structured egocentric memory for deep RL[END_REF] is a neural network structured with spatial information and projective geometry. Or, stated in different terms, in this work the map is not pre-computed by a handcrafted and engineered function (e.g. with estimated occupancy) and fed to an agent, as done in classical robotics; rather, the map is an internal activation of a neural network layer without trainable parameters. As such the content of the map is not predefined and interpretable through a handcrafted definition, the content is trained through machine learning, in our case RL. This layer is a map in the sense that (i) it is spatially organized and corresponds to an allocentric birds-eye representation, which is shifted and rotated with each agent motion through estimated odometry; (ii) using calibrated cameras, pixels are mapped to corresponding points on the map. However, the actual values stored at each position are determined through training and can, according to the learning signal, correspond to a latent representation of anything ranging from occupancy to more semantic information like object positions.

More specifically, ProjNeuralMap maintains a global allocentric map of the environment M t ∈ R H×W ×n composed of n-channel vector representations, n being an hyperparameter, at each position within the full H×W environment. Similar to Bayesian occupancy grids (BOG), which have been used in mobile robotics for many years [START_REF] Moravec | Sensor fusion in certainty grids for mobile robots[END_REF], [START_REF] Rummelhard | Conditional Monte Carlo Dense Occupancy Tracker[END_REF], the map is updated in the two-step process already mentioned above: (1) resampling taking into account estimated agent motion, and (2) integration of the representation of the current observation produced by a CNN f o .

Writing to the map -Given the current RGB observation o t ∈ R h×w×3 , f o extracts an n-channel feature map o ′ t , which is then projected onto the 2D ground plane following the procedure in MapNet [START_REF] Henriques | Mapnet: An allocentric spatial memory for mapping environments[END_REF] to obtain an egocentric map of the agent's spatial neighbourhood m t ∈ R h ′ ×w ′ ×n . The ground projection module assigns a discrete location on the ground plane to each element within o ′ t conditioned on the input depth map d t ∈ R h×w and known camera intrinsics. Registration of the observation m t to the global map is based on the assumption that the agent has access to odometry, as in [START_REF] Wani | Multion: Benchmarking semantic map memory using multi-object navigation[END_REF]. The update to M t is performed through an elementwise max-pooling between m t and M t-1 .

Reading the map -The global map is first cropped around the agent and oriented towards its current heading to form an egocentric map of its neighbourhood at time t, which is then fed to f m producing a context feature vector. The latter is then concatenated to the rest of the input, i.e. representations of the current observation, target object and previous action, producing the input to the recurrent memory (GRU) unit. The full model is trained end-toend with Reinforcement Learning (RL), including networks involved in map writing and reading operations.

OracleMap ➀➂has access to a ground-truth grid map of the environment with 2 channels. The first channel is dedicated to occupancy information with a binary value per cell indicating the presence of free space or an obstacle. The second channel encodes the presence of objects and their classes with thus 9 possible values per cell, i.e. 1 to 8 for one of the 8 object classes, or 0 for no object. Each channel information is passed through a learned embedding layer to output a m-dim vector, m being an hyperparameter, as it is common practice to represent categorical data fed to a neural network. This leads to a map with 2 × m channels. The map is cropped and centered around the agent to produce an egocentric map as input to the model.

✓ - - - - - - - OracleMap ✓ ✓ - ✓ ✓ ✓ ✓ - OracleEgoMap ✓ ✓ - ✓ - - ✓ - ProjNeuralMap ✓ ✓ ✓ ✓ - - - ✓ RGBD observation
OracleEgoMap ➀➂➃gets the same egocentric map as OracleMap with only object channels, and revealed in regions that have already been within its field of view during the episode. This variant corresponds to an agent capable of perfect mapping -no information gets lost, but only observed information is used.

Table I summarizes the environment representation strategies used by the different baselines.

B. Learning to map objects with auxiliary tasks

We introduce auxiliary tasks, additional to the classical RL objectives, and formulated as classification problems, which require the agent to predict information on object appearances, which were in its observation history in the current episode. To this end, the base model is augmented with three classification heads (Figure 2) taking as input the contextual representation produced by the GRU unit. It is important to note that these additional classifiers are only used at training time to encourage the learning of spatial reasoning. At inference time, i.e. when deploying the agent on new episodes and/or environments, predictions about already seen targets, their relative direction are distance are not considered. Only the output of the actor is taken into account to select actions to execute.

Directionthe agent predicts the relative direction of the target object, only if it has been within its field of view in the observation history of the episode (Figure 1 left). The ground-truth direction towards the goal is computed as,

ϕ t = ∢(o t , e) = -atan2(o t,x -e x , o t,y -e y ) (1)
where e = [e x e y ] ("ego") are the coordinates of the agent on the grid and o = [o t,x o t,y ] are the coordinates of the center of the target object at time t. As the ground-truth grid is egocentric, the position of the agent is fixed, i.e. at the center of the grid, while the target object gets different coordinates with time. The angles are kept in the interval [0, 2π] and then discretized into K bins, giving the angle class. The groundtruth one-hot vector is denoted ϕ * t . At time instant t, the probability distribution over classes φt is predicted from the GRU hidden state h t through an MLP as p( φt ) = f ϕ (h t ; θ ϕ ) with parameters θ ϕ .

Distance -The second task requires the prediction of the Euclidean distance in the egocentric map between the center box, i.e. position of the agent, and the mean of the grid boxes containing the target object (Figure 1 Observed target -This third loss favors learning whether the agent has previously encountered the target object. The model is required to predict the binary value 1 obs t , defined as 1 if the target object at time t has been within the agent's field of view at least once in the episode, and 0 otherwise. The model predicts the probability distribution over classes ô bs t given the hidden GRU state h t through an MLP as p( ô bs t ) = f obs (h t ; θ obs ) with parameters θ obs .

C. Training agents with Deep RL

Following [START_REF] Wani | Multion: Benchmarking semantic map memory using multi-object navigation[END_REF], all agents are trained with Proximal Policy Optimization (PPO) [START_REF] Schulman | Proximal policy optimization algorithms[END_REF] and a reward composed of three terms,

R t = 1 reached t • R goal + R closer + R time-penalty (2)
where 1 reached t is the indicator function whose value is 1 if the found action was called at time t while being close enough to the target, and 0 otherwise. R closer is a reward shaping term equal to the decrease in geodesic distance to the next goal compared to previous timestep. Finally, R time-penalty is a negative slack reward to force the agent to take short paths.

PPO alternates between sampling and optimization phases. At sampling time k, a set U k of trajectories τ with length T are collected using the latest policy π θ where θ denotes the set of weights of the policy neural network. Note that T is smaller than the length of a full episode. The base PPO loss is then,

L P P O = 1 |U k | T τ ∈U k T -1 t=0 min r t (θ) Ât , C(r t (θ), ϵ) Ât (3)
where (at|st) is the probability ratio between the updated and old versions of the policy. γ is referred to as the discount factor, s t and a t respectively denote the state and action at time t within the trajectory. We did not make the dependency of states and actions on τ explicit in the notation.

C(r t (θ), ϵ) = clip (r t (θ), 1 -ϵ, 1 + ϵ), Ât is an estimate of the advantage function A π θ (s t , a t ) = Q π θ (s t , a t ) -V π θ (s t ) at time t with Q π θ (s t , a t ) = E a t ′ ∼π θ T t ′ =t γ t ′ R t ′ | S t = s t , A t = a t , V π θ (s t ) = E a t ′ ∼π θ T t ′ =t γ t ′ R t ′ | S t = s t , and r t (θ) = π θ (at|st) π θ old
We provide more details here regarding the actor and critic heads in the base architecture shared by all the considered agents. These two modules respectively predict a distribution π θ (a t | s t ) over actions a t conditioned on the current state s t and the state-value function V π θ (s t ), i.e. expected cumulative reward starting in s t and following policy π θ . Combining an actor and a critic is a common approach in RL [START_REF] Sutton | Reinforcement learning: An introduction[END_REF].

D. Modification of the training objective with auxiliary tasks

We now detail our contribution, i.e. additional terms to the base PPO loss in order to encourage spatial reasoning in trained agents.

Direction, distance and observed target predictions are supervised with cross-entropy losses from ground truth values ϕ * t , d * t and 1 obs t , respectively, as

L ϕ = 1 |U k | T τ ∈U k T -1 t=0 -1 obs t K c=1 ϕ * t,c log p( φt,c ) (4)
L d = 1 |U k | T τ ∈U k T -1 t=0 -1 obs t L c=1 d * t,c log p( dt,c ) (5)
L obs = 1 |U k | T τ ∈U k T -1 t=0 -(1 obs t log p( ô bs t )+ (1 -1 obs t ) log(1 -p( ô bs t ))) (6
) where 1 obs t is the binary indicator function specifying whether the current target object has already been seen in the current episode (1 obs t =1), or not (1 obs t =0). The auxiliary losses L ϕ , L d and L obs are added as follows,

L tot = L P P O + λ ϕ L ϕ + λ d L d + λ obs L obs (7)
where λ ϕ , λ d and λ obs weight the relative importance of auxiliary losses.

IV. EXPERIMENTAL RESULTS

We focus on the 3-ON version of the Multi-ON task, where the agent deals with sequences of 3 objects. The time limit is fixed to 2500 environment steps, and there are 8 object classes. The agent receives a (256×256×4) RGB-D observation and the one-in-K encoded class of the current target object within the sequence. The discrete action space is composed of four actions: move forward 0.25m, turn left 30 • , turn right 30 • , and found, which signals that the agent considers the current target object to be reached. As the aim of the task is to focus on evaluating the importance of mapping, a perfect localization of the agent was assumed as in the protocol proposed in [START_REF] Wani | Multion: Benchmarking semantic map memory using multi-object navigation[END_REF].

Dataset and metricswe used the standard train/val/test split over scenes from the Matterport [START_REF] Chang | Matterport3d: Learning from rgb-d data in indoor environments[END_REF] dataset, ensuring no scene overlap between splits. There are 61 training scenes, 11 validation scenes, and 18 test scenes. The train split consists of 50, 000 episodes per scene, while there are 12, 500 episodes per scene in the val and test splits. Reported results on the val and test sets (Tables II andIII) were computed on a subset of 1, 000 randomly sampled episodes. Fig. 3 shows an example of episode (from the Mini-val set of the CVPR 2021 Multi-On Challenge) with RGB-D inputs.

We consider standard metrics of the field as given in [START_REF] Wani | Multion: Benchmarking semantic map memory using multi-object navigation[END_REF]:

• Success: percentage of successful episodes (all three objects reached in the right order in the time limit). • Progress: percentage of objects successfully found in the right order in an episode. • SPL: Success weighted by Path Length. This extends the original SPL metrics from [START_REF] Anderson | On evaluation of embodied navigation agents[END_REF] to the sequential multi-object case. • PPL: Progress weighted By Path Length. Note that for an object to be considered found, the agent must take the found action while being within 1.5m of the current goal. The episode ends immediately if the agent calls found in an incorrect location. For more details, we refer to [START_REF] Wani | Multion: Benchmarking semantic map memory using multi-object navigation[END_REF].

Implementation detailstraining and evaluation hyperparameters, as well as architecture details have been taken from [START_REF] Wani | Multion: Benchmarking semantic map memory using multi-object navigation[END_REF]. All reported quantitative results are obtained after 4 training runs (6 runs were computed for ProjNeuralMap with the three auxiliary for job scheduling reasons) for each model, during 70M steps (increased from 40M in [START_REF] Wani | Multion: Benchmarking semantic map memory using multi-object navigation[END_REF]). This amount of training time is standard when considering previous work targeting visual navigation with learningbased agents trained with RL. Ground-truth direction and distance measures are respectively split into K = 12 and L = 36 classes. Indeed, angle bins span 30 • , and distance bins span a unit distance on the egocentric map, that is 50 × 50 (the maximum distance between center and a grid corner is thus 35). The map used to compute ground-truth labels for auxiliary losses is the one fed to the OracleEgoMap agent. Training weights λ ϕ , λ d and λ obs are all fixed to 0.25. Each classification head is a single linear layer followed by a softmax activation function.

Do the auxiliary tasks improve the downstream objective?in Table II, we study the impact of the different auxiliary tasks on the 3-ON benchmark when added to the training objective of ProjNeuralMap, and their complementarity. Direction prediction significantly improves performance, adding distance prediction further increases all metrics by a large margin, outperforming the performance of (incomparable) OracleEgoMap. Both losses have thus a strong impact and are complementary, confirming the assumption that sense of direction and judgement of relative distance are two key skills for spatially navigating agents. The third loss about observed target objects brings a supplementary non-negligible boost in performance, showcasing the effectiveness of explicitly learning to remember, and its complementarity with distance and direction prediction.

Table III presents results on the test set, confirming the significant impact on each of the considered metrics. ProjNeuralMap with auxiliary losses matches the performance of (incomparable) OracleMap on Progress and Success, again outperforming OracleEgoMap when considering all metrics. OracleMap has higher PPL and SPL, but has also access to very strong privileged information.

Interestingly, OracleEgoMap also benefits from the use of the auxiliary tasks at training time. As such agent already has access to priviledged information about the position of seen objects, this might suggest the auxiliary losses improve its spatial reasoning capabilities.

Can an unstructured recurrent agent learn to map? we explore whether an agent without spatial inductive bias, i.e. the assumption that the representation of the environment must be a 2D map, can be trained to learn a mapping strategy, to encode spatial properties of the environment into its unstructured hidden representation. As shown in Table III, NoMap indeed strongly benefits from the auxiliary supervision (Success for instance jumping from 16.7% to 43.0%). Improvement is significant, outperforming ProjNeuralMap trained without auxiliary supervision, and closing the gap with OracleEgoMap. The quality of extra supervision can thus help to guide the learnt representation, mitigating the need for incorporating inductive biases into neural networks. When both are trained with our auxiliary losses, ProjNeuralMap still outperforms NoMap, indicating that spatial inductive bias still provides an edge.

Comparison with the state-of-the-artour method

Step 1

Agent's pos.

Step 7

Step 13

Step 27

Step 32

Step 46

Step 57

Step 102

Step 191

Step 212

Pred goal pos. corresponds to the winning entry of the CVPR 2021 Multi-On Challenge organized with the Embodied AI Workshop, shown in Table IV. Test-standard is composed of 500 episodes and Test-challenge of 1000 episodes. In the context of the Challenge, the ProjNeuralMap agent was trained for 80M steps with the auxiliary objectives, and then finetuned for 20M more steps with only the vanilla RL objective. The official challenge ranking is done with PPL, which evaluates correct mapping (quicker and more direct finding of objects), while mapping does not necessarily have an impact on success rate, which can be obtained by pure exploration. Visualization -Figure 3 illustrates an example trajectory from the agent trained with the auxiliary supervision in the context of the CVPR 2021 Multi-On Challenge. The agent starts the episode (Step 1) seeing the white object, which is not the first target to reach. It thus starts exploring the environment (Step 7), until seeing the pink target object (Step 13). Its prediction of the goal distance immediately improves, showing it is able to recognize the object within the RGB-D input. The agent then reaches the target (Step 27). The new target is now the white object (that was seen in Step 1). While it is still not within its current field of view, the agent can localize it quite precisely (Step 32), and go towards the goal (Step 46) to call the found action (Step 57). The agent must then explore again to find the last object (Step 102). When the yellow cylinder is seen, the agent can estimate its relative position (Step 191) before reaching it (Step 212) and ending the episode.

Information about observed targets, their relative distance and direction -Is such knowledge extracted by ProjNeuralMap without auxiliary supervision ? We perform a probing experiment by training three linear classifiers to predict this information from the contextual representation from the GRU unit, both for ProjNeuralMap agent initially trained with and without auxiliary losses. We generate rollout trajectories on 1000 training and validation episodes. It is important to note that, as both agents behave differently, linear probes are not trained and evaluated on the same data. Fig. 4 shows that linear probes trained on representations from our method perform better, and more consistently, suggesting the presence of more related spatial information.

Last minute information -We discovered a bug in the official Multi-ON code [START_REF] Wani | Multion: Benchmarking semantic map memory using multi-object navigation[END_REF] which in some cases provides too much information to the OracleEgoMap baseline. This bug also affected the supervision of our agent (during training only, the bug maintains validity of agent). The differences are small, do not change conclusions or method orders. New results for the values in Table III (test set) would be 52.3, 65.9, 36.4, 45.7.

V. CONCLUSION

In this work, we propose to guide the learning of mapping and spatial reasoning capabilities by augmenting vanilla RL training objectives with auxiliary tasks. We show that learning to predict the relative direction and distance of already seen target objects, as well as to keep track of those observed objects, improves significantly the performance on various metrics and that these gains are consistent over agents with or without spatial inductive bias. The proposed training strategy applied to a learning-based agent from the literature allowed us to win the CVPR 2021 Multi-ON challenge. Future work will investigate additional structure, for instance predicting multiple objects.

  Fig. 1.In the context of Deep-RL for Multi-Object Navigation, two auxiliary tasks predict the direction (left) and the distance (right) to the next object to retrieve if it has been observed during the episode. The green object (square) is the current target, and other targets exist and have already been found or might be required to be found later (ex: blue object / square). Red dot: position of the agent. White and grey cells, respectively, indicate free space and obstacles. Both, the angle ϕt and the distance dt between the center of the map (i.e. the agent) and the target at time t are discretized and associated with a class label. A third sub-task is to predict if the current target has already been within the agent's field of view during the episode.

Fig. 2 .

 2 Fig.2. To study the impact of our auxiliary losses on different agents[START_REF] Wani | Multion: Benchmarking semantic map memory using multi-object navigation[END_REF], we explore several input and inductive biases. All variants share basic observations ➀ (RGB-D image, target class, previous action). Variants also use a map ➁ produced with inverse projective mapping. Oracle variants receive ground truth maps ➂, where in one further variant unseen objects are removed ➃. These architectures have been augmented with classification heads implementing the proposed auxiliary tasks (green rectangle).

Fig. 3 .

 3 Fig. 3. Example agent trajectory (sample from competition Mini-val set). The agent properly explores the environment to find the pink object. It then successfully backtracks to reach the white cylinder, and finally goes to the yellow one after another exploration phase (see text for a detailed description). In columns 3 and 6, the relative direction and distance predictions are combined into a visualised blue point on top of the oracle egocentric map (Ground-truth object positions). The red point corresponds to the position of the agent. Note that these predictions are not used by the agent at inference time, and are only shown for visualisation purposes. The top down view and oracle egocentric map are also provided for visualisation only.

Fig. 4 .

 4 Fig. 4. Confusion matrices (validation set) of linear probes trained on representations from both ProjNeuralMap initially optimized with and without auxiliary supervision. Red lines indicate matrix diagonals.

TABLE I SUMMARY

 I OF ENV. REPRESENTATION IN SOTA BASELINE AGENTS.

	Agent	GRU	Map Map	Map	Full	Oracle	Oracle	Neural
		state	update	reading	visibility	occupancy	goals	features
	NoMap

  right) that was observed during the episode, d t = ||o t -e|| 2 . Again, distances are discretized into L bins, with d * t as groundtruth one-hot vector, and at time instant t, the probability distribution over classes dt is predicted from the hidden state h t through an MLP as p( dt ) = f d (h t ; θ d ) with parameters θ d .

TABLE II IMPACT

 II OF DIFFERENT AUXILIARY TASKS (VALIDATION PERFORMANCE). THE † COLUMN SPECIFIES COMPARABLE AGENTS. ± 3.7 70.2 ± 2.7 37.5 ± 2.0 45.9 ± 1.9 ✓ NoMap -16.7± 3.6 33.7± 3.3 13.1± 2.4 26.0± 1.7 ✓ ✓ 43.0± 4.7 58.2± 4.0 29.5± 1.8 39.9± 1.3 ✓

	Agent	Dir. Dist. Obs. Success Progress	SPL	PPL	†
	OracleMap *	--	-44.9± 1.7 55.7± 2.4 35.4± 1.4 43.7± 2.2 -
	OracleEgoMap * --	-27.5± 2.7 42.8± 2.8 21.3± 2.5 32.7± 2.9 -
		--	-21.8± 1.7 38.6± 1.3 15.4± 0.7 27.0± 0.7 ✓
	ProjNeuralMap	---✓	✓ 22.4± 2.9 40.2± 2.2 16.2± 2.7 28.9± 2.3 ✓ -27.3± 3.3 43.0± 3.6 19.2± 2.1 30.6± 2.4 ✓
		✓ -	-40.2± 4.2 55.9± 3.5 26.1± 2.2 36.4± 2.0 ✓
		✓ ✓	-44.3± 6.6 58.9± 4.9 29.0± 3.7 39.0± 2.2 ✓
		✓ ✓	✓ 49.2 ± 7.1 62.8 ± 5.2 32.0 ± 2.7 41.1 ± 1.1 ✓
			TABLE III
	CONSISTENCY OVER MULTIPLE MODELS (TEST SET). THE † COLUMN
		SPECIFIES COMPARABLE AGENTS.
	Agent	Aux. Sup. Success Progress	SPL	PPL	†
	OracleMap *	-	50.4± 3.5 60.5± 3.1 40.7± 2.2 48.8± 1.9 -
	OracleEgoMap *	-✓	32.8± 5.2 47.7± 5.2 26.1± 4.5 37.6± 4.7 -44.0± 7.1 55.1± 7.0 35.0± 5.2 43.8± 5.0 -
	ProjNeuralMap	-✓	25.9± 1.1 43.4± 1.0 18.3± 0.6 30.9± 0.7 ✓ 57.7

TABLE IV CVPR

 IV 2021 Multi-ON CHALLENGE LEADERBOARD. Test Challenge ARE THE OFFICIAL CHALLENGE RESULTS. Test Standard CONTAINS PRE-AND POST-CHALLENGE RESULTS. RANKING IS DONE WITH PPL. THE * SYMBOL DENOTES CHALLENGE BASELINES.

	Agent/Method	-Test Challenge -	-Test Standard -
		Success Progress SPL PPL Success Progress SPL PPL
	Ours (Aux. losses) 55	67	35 44	57	70	36 45
	SGoLAM	52	64	32 38	62	71	34 39
	VIMP	41	57	26 36	43	57	27 36
	ProjNeuralMap *	-	-	--	12	29	6 16
	NoMap *	-	-	--	5	19	3 13

Acknowledgement -We thank ANR for support through AI-chair grant "Remember" (ANR-20-CHIA-0018).