Cuong Le Van
email: levan@univ-paris1.fr

Katheline Schubert
email: schubert@univ-paris1.fr

Tu Anh

Cuong Le Van + †

Tu Anh Nguyen

With Exhaustible Resources, Can a Developing Country Escape From the Poverty Trap ?

Keywords: optimal growth, exhaustible resource, convex-concave technology, poverty trap, competitive equilibrium with tax/subsidy. JEL Classification: Q32, C61

This paper studies the optimal growth of a developing non-renewable natural resource producer, which extracts the resource from its soil, and produces a single consumption good with man-made capital. Moreover, it can sell the extracted resource abroad and use the revenues to buy an imported good, which is a perfect substitute of the domestic consumption good. The domestic technology is convex-concave, so that the economy may be locked into a poverty trap. We study the optimal extraction and depletion of the exhaustible resource, and the optimal paths of accumulation of capital and of domestic consumption. We show that the extent to which the country will optimally escape from the poverty trap and the exhaustible resource will be a blessing depends on the characteristics of its technology and of the revenues from the resource function, on its impatience, on the level of its initial stock of capital, and on the abundance of the natural resource. If the marginal productivity of capital at the origin is greater than the sum of the social discount rate and the depreciation rate, the country will accumulate capital along the entire growth path, and will escape from the poverty trap, whatever its initial stocks of capital and resource, and provided that the marginal revenue obtained from the exportation of the resource is finite at the origin. On the contrary, if the marginal productivity of capital is lower than the depreciation rate whatever the level of capital, and if moreover the initial stock of capital is small, then the country will never accumulate; it will consume the revenues obtained from selling abroad the extracted resource, until there is

Introduction

The standard literature on growth and exhaustible resources, initiated by Dasgupta and Heal [START_REF] Dasgupta | The Optimal Depletion of Exhaustible Resources[END_REF] in the seventies, deals with developed economies, or a world economy, relying on a non-renewable natural resource as a factor of production. Capital and resource are imperfect substitutes in the production process. The resource input is necessary in the sense that there is no production without it, but unessential in the sense that its productivity at the origin is unbounded. When the social planner adopts a social welfare function of the discounted utilitarian type, the shadow price of the resource stock follows the Hotelling's rule, the resource is asymptotically depleted, and consumption asymptotically vanishes.

The problematic of this paper is different. We are concerned here with a developing non-renewable natural resource producer -an oil producing country for instance-, which extracts the resource from its soil in its primary sector, and produces a single consumption good with man-made capital in its secondary sector. Moreover, it can sell the extracted resource abroad 1 . The revenues are then used to buy an imported good, which is a perfect substitute of the domestic consumption good. The resource is unnecessary in the preceeding sense: domestic production is possible without it.

The question we want to address is the following: Can the ownership of non-renewable natural resources allow a poor country to make the transition out of a poverty trap? We suppose that the production function is convex for low levels of capital and concave for high levels. The conditions of occurrence of a poverty trap are then fulfilled (Dechert and Nishimura [START_REF] Dechert | A complete characterization of optimal growth paths in an aggregate model with a non-concave production function[END_REF], Azariadis and Stachurski [START_REF] Azariadis | Poverty Traps in Handbook of Economic Growth[END_REF]): the country, if initially poor, may be unable to pass beyond the trap level of capital, that is to say to develop. But the country can also extract its resource, sell it abroad, and use the revenues to import the good. The natural resource is a source of income, which, together with the income coming from domestic production, can be used to consume, or to accumulate capital. The idea is that a poor country with abundant natural resources could extract and sell an amount of resource which would enable it to accumulate a stock of capital sufficient to overcome the weakness of its initial stock. We want to know on what circumstances would such a scenario optimally occur.

We study in this paper the optimal extraction and depletion of the exhaustible resource, and the optimal paths of accumulation of capital and of domestic consumption. We take into account the characteristics of the domes-tic technology, the shape of the foreign demand for the exhaustible resource, and of course the initial abundance of the resource and the initial level of development of the country.

We show that the extent to which the country will optimally escape from the poverty trap and the exhaustible resource will be a blessing depends on the characteristics of its technology and of the revenues from the resource function, on its impatience, on the level of its initial stock of capital, and on the abundance of natural resource. The technology is convex-concave, so a poverty trap exists. If the marginal productivity of capital at the origin is greater than the sum of the social discount rate and the depreciation rate, the country will accumulate capital along the entire growth path, and will escape from the poverty trap, whatever its initial stocks of capital and resource, and provided that the marginal revenue obtained from the exportation of the resource is finite at the origin. On the contrary, if the marginal productivity of capital is lower than the depreciation rate whatever the level of capital, and if moreover the initial stock of capital is small, then the country will never accumulate; it will consume the revenues obtained from selling abroad the extracted resource, until there is no resource left and the economy collapses.

Finally, we show that any optimal path may be decentralized in a competitive equilibrium. Due to the existence of increasing returns in production for low levels of capital, it is necessary to introduce a tax/subsidy scheme to ensure that the competitive equilibrium exists. This scheme is based upon the difference between the values of the input and output.

The remaining of the paper is organized as follows. Section 2 presents the model. Section 3 gives the properties of the optimal growth paths. We prove in section 4 the existence of a competitive equilibrium. Section 5 provides a summary of the main results and concludes.

The model

We consider a country which possesses a stock of a non-renewable natural resource S. This resource is extracted at a rate R t , and then sold abroad at a price P t , in terms of the numeraire, which is the domestic single consumption good. The inverse demand function for the resource is P (R t ). The revenue from the sale of the natural resource, φ(R t ) = P (R t )R t , is used to buy a foreign good, which is supposed to be a perfect substitute of the domestic good, used for consumption and capital accumulation. The domestic production function is F (k t ), supposed to be convex for low levels of capital and then concave. The depreciation rate is δ. We define the function f (k t ) = F (k t ) + (1 -δ)k t , and we shall, in the following, name it for simplicity the technology. We are interested in the optimal growth of this country which, if its initial capital is low, can be locked into a poverty trap (Dechert and Nishimura [START_REF] Dechert | A complete characterization of optimal growth paths in an aggregate model with a non-concave production function[END_REF]). Will the revenues coming from the extraction of the natural resource allow it to escape from the poverty trap? Or, on the contrary, will the existence of the natural resource, which allows the country to consume without producing, destroy any incentive to accumulate?

Formally, we have to solve problem (P)

max +∞ t=0 β t u(c t ), β ∈ (0, 1)
under the constraints

∀t, c t ≥ 0, k t ≥ 0, R t ≥ 0, c t + k t+1 ≤ f (k t ) + φ(R t ), +∞ t=0 R t ≤ S, S > 0, k 0 ≥ 0 are given.
We denote by Z(k 0 , S) the Value-function of Problem (P). We make the following assumptions: H1 The utility function u is strictly concave, strictly increasing, continuously differentiable in R + , and satisfies u(0) = 0, u (0) = +∞. H2 The production function F is continuously differentiable in R + , strictly increasing, strictly convex from 0 to k I , strictly concave for k ≥ k I , and F (+∞) < δ. Moreover, it satisfies F (0) = 0. H3 The revenue function φ is continuously differentiable, concave, strictly increasing from 0 to R ≤ +∞, and strictly decreasing for R > R. It also satisfies φ(0) = 0. Throughout this paper, an infinite sequence (x t ) t=0,...,+∞ will be denoted by x. An optimal solution to Problem (P) will be denoted by (c * , k * , R * ). We say that the sequences c, k, R are feasible from k 0 if they satisfy the constraints:

∀t, c t ≥ 0, k t ≥ 0, R t ≥ 0 c t + k t+1 ≤ f (k t ) + φ(R t ), +∞ t=0 R t ≤ S,
and k 0 is given.

Let Ω(k 0 , S) denote the set of (k, R) feasible from k 0 and S, i.e.,

∀t, 0 ≤ k t+1 ≤ f (k t ) + φ(R t ), 0 ≤ R t +∞ t=0 R t ≤ S, k 0 ≥ 0 is given.
We first list some preliminary results necessary for the main results of our paper.

Lemma 1

The Value-function Z is continuous in k 0 , given S.

Proof : We first prove that the correspondence Ω is compact-valued and continuous in k 0 , for the product topology, given S.

To prove that Ω(k 0 , S) is compact, take a sequence {k n , R n } which converges to {k , R} for the product topology. First, observe that for any feasible k we have

∀t, 0 ≤ k t+1 ≤ f (k t ) + φ(R t ) ≤ f (k t ) + max{φ( R), φ(S)}.
Therefore, k will be in a compact set for the product topology (see e.g. Le Van and Dana [5]). Second,

∀n, ∀t, 0 ≤ k n t+1 ≤ f (k n t ) + φ(R n t ),
hence, by taking the limits we get

∀t, 0 ≤ k t+1 ≤ f (k t ) + φ(R t ).
We have proved that the set of feasible k is closed for the product topology. It is obvious that the set of feasible R belongs to a fixed compact set. To prove that this set is closed, observe that ∀N, ∀n N t=0 R n t ≤ S. Taking the limit we get ∀N, ∀n

N t=0 R t ≤ S. That implies +∞ t=0 R t ≤ S.
Summing up, we have proved that Ω(k 0 , S) is compact.

It is easy to check that Ω is upper hemi-continuous in k 0 . It is less easy for the lower hemi-continuity of Ω. We will prove that, actually, Ω is lower hemi-continuous. Let k n 0 → k 0 as n goes to +∞ and (k, R) ∈ Ω(k 0 , S). We have to show there exists a subsequence still denoted by (k n , R n ), for short, which converges to (k, R) and satisfies (k n , R n ) ∈ Ω(k n 0 , S), ∀n. We have three cases. Case 1 :

0 ≤ k t+1 < f (k t ) + φ(R 0 ), ∀t < T -1 0 ≤ k t ≤ f (k t-1 ) + φ(R t-1 ), ∀t ≥ T.
There exists N such that for any n ≥ N , we have k 1 < f (k n 0 ) + φ(R 0 ). Define, for any n ≥ N , any t, k n t = k t , R n t = R t and the proof is done. Case 2 :

k t+1 = f (k t ) + φ(R t ), ∀t ≤ T -1, k T +1 < f (k T ) + φ(R T ), k t+1 ≤ f (k t ) + φ(R t ), ∀t ≥ T + 1.
Define, for t = 0, ..., T -1 and for any n, k n t+1 = f (k n t ) + φ(R t ). Obviously, k n t → k t for t = 0, ..., T -1. Hence, there exists N such that for any n ≥ N , k T +1 < f (k n T ) + φ(R T ). The sequences (k n 0 , k n 1 , ..., k n T , k T +1 , k T +2 , ...) and R n =R, for every n, satisfy the required conditions. Case 3 :

∀t, k t+1 = f (k t ) + φ(R t ).
It suffices to take k n t+1 = f (k n t ) + φ(R t ) for every t, every n. The second step is to prove that the intertemporal utility function is continuous on the feasible set for the product topology. But the proof is standard (see e.g. Le Van and Dana [5]).

The third step is to apply the Maximum Theorem to conclude that Z is continuous in k 0 .

Lemma 2 There exists a constant A which depends on k 0 , R, and S, such that for any feasible sequence (c, k, R), we have ∀t,

0 ≤ c t ≤ A, 0 ≤ k t ≤ A.
Moreover, Problem (P) has an optimal solution. If k I = 0, then the solution is unique.

Proof : It is obvious that R t ≤ S, ∀t. Now, if R < +∞ then for any t, we have c t + k t+1 ≤ f (k t ) + φ( R). And if R = +∞ then for all t, c t + k t+1 ≤ f (k t ) + φ(S). Since f (+∞) < 1, from Le Van and Dana [START_REF] Van | Dynamic Programming in Economics[END_REF], page 17, there exists a constant A which depends on k 0 , R (if R < +∞) or on k 0 , S such that ∀t, 0 ≤ c t ≤ A, 0 ≤ k t ≤ A.

We have already proved that the set of feasible sequences is compact for the product topology and the intertemporal utility function is continuous on the feasible set for the same topology. Hence, there exists a solution to Problem (P). When k I equals 0, because of the strict concavity of the technology and the utility function u, the solution will be unique.

Properties of the optimal paths

We now study the properties of the optimal paths.

In the following, the superscript * denotes the optimal value of the variables. Proposition 1 states that along the optimal path consumption is always strictly positive and the extraction always less than R, the maximum of the revenue function; moreover, if the marginal revenue is infinite when the extraction becomes very small, the resource will not be exhausted in finite time.

Proposition 1 For any t, c * t > 0 and R * t < R. If φ (0) = +∞, then R * t > 0 for all t. Obviously, R * t → 0 as t → +∞.
Proof : Let V denote the Value-function. Observe that V (k 0 ) > 0 for any k 0 ≥ 0, since the sequence c defined by c 0 = f (k 0 ) + φ(S) and c t = 0 for any

t > 0 is feasible. Hence V (k 0 ) ≥ u(c 0 ) > 0. That implies c * t > 0, ∀t, by the Inada condition u (0) = +∞.
Let us prove that R * t < R for all t. If R = +∞, the proof is obvious. So, assume R < +∞. We cannot have R * t > R for some t, since u is strictly increasing and φ is strictly decreasing for R > R. We cannot have

R * t = R for all t since +∞ t=0 R * t = S. If there exists T with R * T = R, we can suppose R * T +1 < R.
Without loss of generality, take T = 0. So

c * 0 + k * 1 = f (k 0 ) + φ( R) c * 1 + k * 2 = f (k * 1 ) + φ(R * 1 ), with R * 1 < R. Choose ε > 0 small enough such that R * 1 + ε < R and R -ε > 0. Let c 0 + k * 1 = f (k 0 ) + φ( R -ε) c 1 + k * 2 = f (k * 1 ) + φ(R * 1 + ε) and c t = c * t , ∀t ≥ 2. Let ε = +∞ t=0 β t u(c t ) - +∞ t=0 β t u(c * t ). We have ε = u(c 0 ) -u(c * 0 ) + β[u(c 1 ) -u(c * 1 )] ≥ u (c 0 )[φ ( R -ε)(-ε)] + βu (c 1 )[φ (R * 1 + ε)(ε)] ≥ ε[βu (c 1 )φ (R * 1 + ε) -u (c 0 )φ ( R -ε)]. Let ε → 0. Then lim ε→0 ε ≥ βu (c * 1 )φ (R * 1 ) > 0.
Thus ε > 0 for ε small enough. That is a contradiction to the optimality of c * . Now consider the case φ (0) = +∞. First assume R * t = 0, ∀t. Then let

c 0 = f (k 0 ) -k * 1 + S > c * 0 c t = f (k * t ) -k * t+1 = c * t , for t ≥ 1. Then +∞ t=0 u(c t ) > +∞ t=0 u(c * t ): a contradiction. Hence if R * T = 0 we can assume that R * T +1 > 0. Without loss of generality, take T = 0. So c * 0 = f (k 0 ) -k * 1 c * 1 = f (k * 1 ) -k * 2 + φ(R * 1 ), with 0 < R * 1 < R. Let ε ∈ (0, R * 1 ). Define c 0 = f (k 0 ) -k * 1 + φ(ε) c 1 = f (k * 1 ) -k * 2 + φ(R * 1 -ε) c t = c * t , ∀t ≥ 2. Then ε = +∞ t=0 β t u(c t ) - +∞ t=0 β t u(c * t ) = u(c 0 ) -u(c * 0 ) + β[u(c 1 ) -u(c * 1 )] ≥ u (c 0 )φ(ε) + βu (c 1 )[φ(R * 1 -ε) -φ(R * 1 )] ≥ [u (c 0 )φ (ε) -βu (c 1 )φ (R * 1 -ε)]ε.
Notice that lim ε→0 ε ε = +∞ which implies ε > 0 for ε small enough: a contradiction.

Proposition 2 gives the Euler conditions of our problem, in the case where the marginal revenue at the origin is finite, which we will favor in the remaining of the paper. Notice that in the case of an interior solution, equations (E1) and (E2) allow us to obtain the Hotelling's rule:

φ (R * t+1 ) φ (R * t ) = f (k * t+1 ). (1)
Proposition 2 Let k 0 ≥ 0. Assume φ (0) < +∞. Then we have the following Euler conditions:

(i) ∀t, f (k * t+1 ) ≤ u (c * t ) βu (c * t+1 ) (E1) with equality if k * t+1 > 0, (ii) ∀t, ∀t , β t u (c * t )φ (R * t ) = β t u (c * t )φ (R * t ), (E2) if R * t > 0, R * t > 0, and
(iii) ∀t, ∀t , β t u (c * t )φ (R * t ) ≤ β t u (c * t )φ (R * t ), (E2 ) if R * t = 0, R * t > 0. Proof : (i) Given t, k * t+1 solves : max y u(f (k * t ) + φ(R * t ) -y) + βu(f (y) + φ(R * t+1 ) -k * t+2 ) s.t. 0 ≤ y ≤ f (k * t ) + φ(R * t ) 0 ≤ y. Since c * t = f (k * t ) + φ(R * t ) -k * t+1 > 0, one easily gets (E1).
(ii) Since S > 0, there exists t with R * t > 0. Fix some T such that there exists

t ≤ T with R * t > 0. Then (R * 0 , ..., R * T ) solve max (R 0 ,...,Rt) T t=0 β t u(f (k * t ) + φ(R t ) -k * t+1 ) s.t. T t=0 R t ≤ S - +∞ τ =T +1 R * τ 0 ≤ R t , ∀t = 0, ..., T k * t+1 -f (k * t ) ≤ φ(R t ), ∀t = 0, ..., T.
Since φ is concave and u is strictly concave, (R * 0 , ..., R * T ) will be the unique solution. Moreover, since c * t > 0 for every t, the third constraints system will not be binding. There exist therefore λ ≥ 0 and µ t ≥ 0, t = 0, ..., T such that (R * 0 , ..., R * T ) maximize

T t=0 β t u(f (k * t ) + φ(R t ) -k * t+1 ) -λ T t=0 R t -S + +∞ τ =T +1 R * τ + T t=0 µ t R t ,
with µ t R * t = 0, ∀t = 0, ..., T . One easily obtains (E2) and (E2 ).

Proposition 3 shows that, even if the initial capital stock equals 0, if the marginal productivity of capital at the origin is large enough, then, thanks to the exhaustible resource, the country will accumulate from some date on. More precisely, the marginal productivity at the origin of the production function F must be larger than the depreciation rate δ.

Proposition 3 Let k 0 ≥ 0. Assume φ (0) < +∞. If f (0) > 1, then there exists T ≥ 1 with k * t > 0 for any t ≥ T .
Proof : Since f (0) > 1, we can choose > 0 such that f (0) > 1 + . Assume that there exists an infinite sequence {k * t ν } ν such that k * t ν = 0, for any ν, and hence correspondently

R * t ν > 0. Because +∞ t=o R * t = S we have R * t ν -→ 0 as ν -→ +∞. Since R * t ν -→ 0 and R * t ν -1
either equals 0 or converges to 0, there exists T such that

φ (R * t ν ) φ (R * t ν -1 ) < 1 + if t ν ≥ T .
We can write down the optimal consumptions at time t ν and t ν -1 as follows:

c * t ν -1 = φ(R * t ν -1 ) + f (k * t ν -1 ) c * t ν = φ(R * t ν ) -k * t ν +1
We have

u(c * t ν -1 -y) + βu(c * t ν + f (y)) ≤ u(c * t ν -1 )) + βu(c * t ν ), for all y ∈ [0, c * t ν -1 ], thus -u (c * t ν -1 ) + βu (c * t ν )f (0) ≤ 0,
and we get a contradiction

1 + < f (0) ≤ u (c * t ν -1 ) βu (c * t ν ) ≤ φ (R * t ν ) φ (R * t ν -1 ) < 1 + .
So, there must exist T ≥ 1 such that k * t > 0 for all t ≥ T .

In Proposition 4, we show that thanks to the exhaustible resource, the country will accumulate at any period, provided that the marginal productivity of capital at the origin is larger than the sum of the social discount rate and the depreciation rate, ρ + δ, with ρ = 1 β -1. Notice that when the initial capital stock is equal to 0, the same economy without natural resources never takes-off (Dechert and Nishimura [START_REF] Dechert | A complete characterization of optimal growth paths in an aggregate model with a non-concave production function[END_REF]). So, when the technology is "good" enough, the natural resource is a blessing allowing the economy to escape from the poverty trap.

Proposition 4 Let k 0 ≥ 0. Assume f (0) > 1 β . Then k * t > 0 for any t ≥ 1.
Proof : Assume k * 1 = 0. Then we have

c * 0 = f (k 0 ) + φ(R * 0 ) c * 1 + k * 2 = φ(R * 1 ).
The following Euler conditions hold:

-u (c * 0 ) + βu (c * 1 )f (0) ≤ 0 u (c * 0 )φ (R * 0 ) -βu (c * 1 )φ (R * 1 ) ≤ 0. This implies 1 < 1 β < f (0) ≤ u (c * 0 ) βu (c * 1 ) ≤ φ (R * 1 ) φ (R * 0 )
.

¿From these inequalities, we get u (c * 0 ) > u (c * 1 ), φ (R * 1 ) > φ (R * 0 ) or equiva- lently, c * 1 > c * 0 and R * 0 > R * 1 .
A contradiction arises:

φ(R * 1 ) ≥ φ(R * 1 ) -k * 2 = c * 1 > c * 0 = f (k 0 ) + φ(R * 0 ) ≥ φ(R * 0 ) > φ(R * 1 ).
Therefore, k * 1 > 0. By induction, k * t > 0 for all t ≥ 1.

We want to show now that the natural resource will be exhausted in finite time if the marginal productivity of capital at the origin is high enough. Before proving that, let us introduce an intermediary step.

Consider Problem (Q)

U (k 0 ) = max +∞ t=0 β t u(c t ), β ∈ (0, 1) under the constraints ∀t, c t ≥ 0, k t ≥ 0, c t + k t+1 ≤ f (k t ), k 0 ≥ 0 is given.
Let ϕ denote the optimal correspondence of (Q), i.e., k 1 ∈ ϕ(k 0 ) iff we have

k 1 ∈ [0, f (k 0 )] and U (k 0 ) = u(f (k 0 ) -k 1 ) + βU (k 1 ) = max{u(f (k 0 ) -y) + βU (y) : y ∈ [0, f (k 0 )]}.
Next consider Problem (Q a ) where a is a sequence of non-negative real numbers which satisfies +∞ t=0 a t < +∞:

W (k 0 , (a t ) t≥0 ) = max +∞ t=0 β t u(c t ), β ∈ (0, 1) under the constraints ∀t, c t ≥ 0, k t ≥ 0, c t + k t+1 ≤ f (k t ) + a t , k 0 ≥ 0 is given.
Obviously, W (k 0 , 0) = U (k 0 ), and W (k 0 , (a t ) t≥0 ) ≥ U (k 0 ). We also have the Bellman equation: for all k 0 ,

W (k 0 , (a t ) t≥0 ) = max{u(f (k 0 ) -y + a 0 ) + βW (y, (a t ) t≥1 ) : y ∈ [0, f (k 0 ) + a 0 ]}.
Let ψ(., (a t ) t≥0 ) denote the optimal correspondence associated with (Q a ), i.e.,

k 1 ∈ ψ(k 0 , (a t ) t≥0 ) iff W (k 0 , (a t ) t≥0 ) = u(f (k 0 ) -k 1 + a 0 ) + βW (k 1 , (a t ) t≥1 ) and k 1 ∈ [0, f (k 0 ) + a 0 ].
We have the following lemma.

Lemma 3 Let k n 0 → k 0 and a n → 0 in l ∞ when n converges to infinity. If, for any n, k n 1 ∈ ψ(k n 0 , a n ) and k n 1 → k 1 as n → +∞, then k 1 ∈ ϕ(k 0 ).
Proof : We first prove that W (k n 0 , a n ) → U (k 0 ) as n → +∞. We have:

∀n, W (k n 0 , (a n t ) t≥0 ) ≥ U (k n 0 ), hence lim inf n→+∞ W (k n 0 , (a n t ) t≥0 ) ≥ lim n→+∞ U (k n 0 ) = U (k 0 ).
We now prove that lim sup

n→+∞ W (k n 0 , (a n t ) t≥0 ) ≤ U (k 0 ). Let α > 0.
There exists N such that, for any n ≥ N , we have f (k n 0 ) + a n 0 ≤ f (k 0 ) + α and k n 0 ≤ α. Let kα be the largest value of k which satisfies f ( kα ) + α = kα . Using the same argument as in Le Van and Dana [START_REF] Van | Dynamic Programming in Economics[END_REF], page 17, one can show that, for any feasible sequences from k n 0 , c n , k n of (Q a n ), for any n ≥ N , any t, we have

c n t ≤ max{ kα , k 0 + α}, k n t ≤ max{ kα , k 0 + α}. Let c * n , k * n be the optimal sequences from k n 0 of Problem (Q a n ). Let ε > 0. There exists T such that ∀n, W (k n 0 , (a n t ) t≥0 ) ≤ t=T t=0 β t u(c * n t ) + ε.
For t = 0, ...T , we can suppose that c * n t → ct and k * n t+1 → kt+1 . Since for t = 0, ...T , we have c * n t + k * n t+1 = f (k * n t ) + a n t , we obtain ct + kt+1 = f ( kt ) for t = 0, ..., T . Define c = (c 0 , ..., cT , 0, 0, ..., 0, ...). We get

lim sup n→+∞ W (k n 0 , (a n t ) t≥0 ) ≤ t=T t=0 β t u(c t ) + ε = t=+∞ t=0 β t u(c t ) + ε ≤ U (k 0 ) + ε.
This inequality holds for any ε > 0. We have proved lim sup

n→+∞ W (k n 0 , a n ) ≤ U (k 0 ). Now, let k n 1 ∈ ψ(k n 0 , a n ) and suppose k n 1 → k 1 as n → +∞. We have W (k n 0 , (a n ) t≥0 ) = u(f (k n 0 ) -k n 1 + a n 0 ) + βW (k n 1 , (a n ) t≥1 ),
and

k n 1 ∈ [0, f (k n 0 ) + a n 0 ]
. Taking the limits we get

U (k 0 ) = u(f (k 0 ) -k 1 ) + βU (k 1 ), with k 1 ∈ [0, f (k 0 )]. That proves k 1 ∈ ϕ(k 0 ).
Proposition 5 states that if the marginal revenue of the resource at the origin is finite and the marginal productivity of capital greater than the depreciation rate, then the stock of resource will be exhausted in finite time.

Proposition 5 Assume φ (0) < +∞ and f (0) > 1. Then there exists T ∞ such that, for all t ≥ T ∞ , we have R * t = 0.

Proof : ¿From Proposition 3, there exists T such that ∀t ≥ T , k * t > 0.

Step 1. We will show that there exists T such that R * T = 0. If not, for any t ≥ T we have the Euler conditions:

βu (c * t+1 )f (k * t+1 ) = u (c * t ), (2)
βu (c * t+1 )φ (R * t+1 ) = u (c * t )φ (R * t ).
Hence

f (k * t+1 ) = u (c * t ) βu (c * t+1 ) = φ (R * t+1 ) φ (R * t ) . Since φ (R * t+1 ) φ (R * t ) → 1, we have f (k * t+1
) → 1, as t → +∞. Under our assumptions there exists a unique k which satisfies

f ( k) = 1. Thus k * t+1 → k. In this case, for t large enough, u (c * t+1 ) > u (c * t ) ⇔ c * t > c * t+1 . The sequence c * converges to c. If c > 0, we have f ( k) = 1 β : a contradiction. So, c = 0. Since ∀t, c * t+1 + k * t+2 = f (k * t+1 ) + φ(R * t+1 ), we have k = f ( k) with f ( k) = 1
, and that is impossible. Hence, there must be T with R * T = 0. Step 2. Assume there exists three sequences (c

* t ν ) ν , (k * t ν ) ν , (R * t ν ) ν which satisfy ∀ν, c * t ν -1 + k * t ν = f (k * t ν -1 ) c * t ν + k * t ν +1 = f (k * t ν ) + φ(R * t ν ), with R * t ν > 0. Hence ∀ν, f (k * t ν ) = u (c * t ν -1 ) βu (c * t ν ) ≤ φ (R * t ν ) φ (0) < 1.
Therefore, ∀ν, k * t ν > k. Observe that there exists λ > 0 such that ∀ν,

β tν u (c * t ν )φ (R * t ν ) = λ. This implies c * t ν → 0 as ν → +∞. From Lemma 2, k * t ν ≤ A, ∀ν. One can suppose k * t ν → k ≥ k > 0 and k * t ν +1 → k = f ( k). From Lemma 3, k ∈ ϕ( k). This implies c * t ν → c = f ( k) -k = 0.
But, since k > 0, we must have c > 0 (see Le Van and Dana [5]). This contradiction implies the existence of T ∞ such that for all t ≥ T ∞ , we have R * t = 0.

Remark 1 When the function f is concave, the proof will be very short. Indeed, from Le Van and Saglam [6], the sequence

(β t u (c * t )) t satisfies +∞ t=0 β t u (c * t ) < +∞. Since there exists λ > 0 such that β tν u (c * t ν )φ (R * t ν ) = λ, we have β tν u (c * t ν ) → λ φ (0) > 0. This excludes +∞ t=0 β t u (c * t )
to be bounded from above.

In the following corollary, we prove that, even when the initial capital equals 0, thanks to the natural resource, the country may take-off if the marginal productivity of capital at the origin is larger than the sum of the discount and depreciation rates. But, when this productivity is low, the natural resource cannot prevent the economy to collapse in the long term.

Corollary 1 Let k 0 ≥ 0. Assume φ (0) < +∞. (a) If f (0) > 1 β , then k * t → k s where k s is defined by f (k s ) = 1 β . (b) If f is concave and 1 < f (0) ≤ 1 β , then k * t → 0.
Proof : ¿From Proposition 5, we know that R * t = 0 for t ≥ T ∞ . The optimal sequence (k * t ) t≥T∞ solves problem (Q) with initial data k * T∞ > 0. Assertion (a) follows from Dechert and Nishimura [START_REF] Dechert | A complete characterization of optimal growth paths in an aggregate model with a non-concave production function[END_REF], while assertion (b) follows, e.g., from Le Van and Dana [START_REF] Van | Dynamic Programming in Economics[END_REF].

We now show that the country may never accumulate in physical capital if the marginal productivity is very low, and the initial capital stock is small. Proposition 6 Assume φ (0) < +∞ and f (k I ) < 1.

(a) Let k 0 ≥ 0. Then there exists T with k * t = 0, ∀t ≥ T . (b) There exists ε > 0 such that, if k 0 ≤ ε, then k * t = 0, ∀t.

Proof : (a) There must be t 0 with R * t 0 > 0. We claim that R * t > 0, ∀t > t 0 . Assume R * t 0 +1 = 0. Then we have the Euler conditions

f (k * t 0 +1 ) = u (c * t 0 ) βu (c * t 0 +1 ) ≥ φ (0) φ (R * t 0 ) > 1,
which is impossible. Hence R * t 0 +1 > 0. By induction, R * t > 0, ∀t > t 0 . Thus, for t ≥ t 0 , we have the FOC:

f (k * t+1 ) = u (c * t ) βu (c * t+1 ) = φ (R * t+1 ) φ (R * t ) , if k * t+1 > 0.
If there exists an infinite sequence (k * tν +1 ) ν with k * tν +1 > 0, ∀ν, then from the previous FOC we have lim

ν→+∞ f (k * tν +1 ) = 1: a contradiction since ∀ν, f (k * tν +1 ) ≤ f (k I ) < 1. Therefore, k * t = 0 for any t large enough. (b) Consider Problem (R): S(k 0 , S) = max +∞ t=0 β t u(c t ) under the constraints 0 ≤ c 0 ≤ f (k 0 ) + φ(R 0 ) ∀t ≥ 1, 0 ≤ c t ≤ φ(R t ), 0 ≤ R t +∞ t=0 R t ≤ S.
We first prove the claim for k 0 = 0. Let (R * t , c * t ) t be the solution. We have

+∞ t=0 R * t = S and c * t = φ(R * t ), ∀t.
There exists λ such that ∀t,

β t u (φ(R * t ))φ (R * t ) =
λ. Let (k t , R t ) t be a solution to the initial problem. We have

+∞ t=0 R t = S. Consider = +∞ t=0 β t [u(φ(R * t )) -u(φ(R t ) + f (k t ) -k t+1 )] .
We have

≥ +∞ t=0 β t u (φ(R * t ))φ (R * t )(R * t -R t ) + +∞ t=0 β t u (φ(R * t ))(k t+1 -f (k t )) ≥ λ( +∞ t=0 R * t - +∞ t=0 R t ) + +∞ t=0 β t u (φ(R * t ))(k t+1 -f (k t )) ≥ +∞ t=0 β t u (φ(R * t ))(k t+1 -f (k t )). Recall that ∀t, R * t+1 < R * t . Since u (φ(R * t ))φ (R * t ) = βu (φ(R * t+1 ))φ (R * t+1 ) we have u (φ(R * t )) > βu (φ(R * t+1 )), ∀t.
From part (a), there exists T such that

k t = 0, ∀t ≥ T + 1. Therefore ≥ T t=1 β t u (φ(R * t ))(k t -f (k t )).
Since f (k) < 1 and f (0) = 0, we have f (k) < k. Thus, > 0. This is a contradiction. Now, let k 0 > 0. Then we have β t u (φ(R * t ))φ (R * t ) = λ for some λ > 0 and t ≥ 1, and

u (φ(R * 0 )+f (k 0 ))φ (R * 0 ) ≤ βu (φ(R * 1 ))φ (R * 1 )
with equality if R * 0 > 0. The same computations as above give

≥ T t=2 β t u (φ(R * t ))(k t -f (k t )) + u (f (k 0 ) + φ(R * 0 ))k 1 -βu (φ(R * 1 ))f (k 1 ). When k 0 = 0 we have u (φ(R * 0 )) > βu (φ(R * 1 )). But R * 0 and R * 1 are continuous in k 0 . Hence, when k 0 ≤ ε with ε small enough, we still have u (f (k 0 )+φ(R * 0 )) > βu (φ(R * 1 )
). A contradiction arises as before.

We expect that, when the marginal productivity of capital is low, the country will never accumulate if the stock of non-renewable resource is very large. The result is true if we assume R = +∞. To simplify the proof we will use some explicit forms of the functions u and φ.

Proposition 7 Assume φ (0) < +∞ and f (k I ) < 1. Assume also R = +∞, φ(R) = aR, a > 0 and u(c) = c θ θ with 0 < θ < 1. Let k 0 > 0 be given. Then we have k * t = 0, ∀t, when S is large enough.

Proof : Let (R * t ) t=0,...,+∞ be the solution. We have

∀t ≥ 1, µ 0 + a (f (k 0 ) + aR * 0 ) θ-1 = β t a(aR * t ) θ-1 (3)
where µ 0 ≥ 0, and

µ 0 R * 0 = 0. ( 4
)
We obtain

∀t ≥ 1, R * t = β (1-θ)t a µ 0 + a (f (k 0 ) + aR * 0 ) θ-1 a 1 θ-1 +∞ t=0 R * t = R * 0 + β 1-θ a(1 -β 1-θ ) µ 0 + a (f (k 0 ) + aR * 0 ) θ-1 a 1 θ-1
,

and µ 0 R * 0 = 0.
R * 0 , and when R * 0 = 0, µ 0 will be determined by the contraint S = +∞ t=0 R * t . It is obvious that µ 0 is a decreasing function of S, while R * 0 is an increasing function of S. Thus, when S is high enough, we have µ 0 = 0 and R * 0 > 0. Hence, from relation (3), we get (f

(k 0 ) + aR * 0 ) θ-1 = β(aR * 1 ) θ-1 , i.e. u (f (k 0 ) + aR * 0 ) = βu (aR * 1 )
. Using the proof of Proposition 6, we conclude that the optimal path (k * t ) equals 0.

We now study the long term of our economy with an exhaustible resource. Obviously, in the long term, the exhaustible resource is depleted.

We know, from Dechert and Nishimura [START_REF] Dechert | A complete characterization of optimal growth paths in an aggregate model with a non-concave production function[END_REF], that if f (0)

< 1 β < max{ f (k) k : k > 0}, then there exists k c (< k I < k, with f ( k) = 1), such that if k 0 < k c
then any solution k to Problem (Q) converges to 0, and if k 0 > k c , then it converges to a high steady state k s fulfilling f (k s ) = 1 β . In other words, we have a poverty trap. We will show, under some more assumptions, that if S is high enough the poverty trap can be passed over in our model. We need a preliminary lemma.

Lemma 4 Consider the following problem:

max +∞ t=0 β t u(c t )
under the constraints

c 0 + k 1 ≤ f (k 0 ) c 1 + k 2 ≤ f (k 1 ) + a, a ≥ 0, c t + k t+1 ≤ f (k t ) ∀t, 0 ≤ c t , 0 ≤ k t , k 0 > k I .
Proof : ¿From Proposition 5, there exists T ∞ such that:

c * T∞-2 + k * T∞-1 = f (k * T∞-2 ) + φ(R * T∞-2 ) c * T∞-1 + k * T∞ = f (k * T∞-1 ) + φ(R * T∞-1 ) c * T∞ + k * T∞+1 = f (k * T∞ ) c * t + k * t+1 = f (k * t ), ∀t ≥ T ∞ + 1. Case 1: We have R * T∞-1 ≥ R. Let k * 0 satisfy f (k * 0 ) = f (k * T∞-1 ) + φ(R * T∞-1 ). Then, k * 0 > k I .
The sequence {k * t } t≥T∞ is optimal for the growth model with initial capital k * 0 > k I . It will converge to the steady state

k s since k I > k c . Case 2: We have R * T∞-1 ≤ R and R * T∞-2 ≤ R. We have, from the Euler conditions f (k * T∞-1 ) ≤ φ (R * T∞-1 ) φ (R * T∞-2 ) = 1 hence, k * T∞-1 ≥ k > k I (f ( k) = 1
) and as before, the optimal path converges to the steady state.

Case 3: We have R * T∞-1 ≤ R and R * T∞-2 ≥ R. Let k * 0 satisfy f (k * 0 ) = f (k * T∞-2 ) + φ(R * T∞-2 ). Then, k * 0 > k I . From Lemma 4, we have k * T∞-1 > k I .
As before, the optimal path converges to the steady state.

In the following proposition we drop the assumption that the technology φ is linear in a neighborhood of 0. But we will strengthen the assumptions on the marginal productivity of capital.

Proposition 9 Assume there exists R ∈ (0, R) such that, if k 0 satisfies f (k 0 ) = φ( R), then k 0 > k I . Assume moreover that f (k I ) = +∞ and φ (0) φ ( e R) < f (0) ≤ 1 β ≤ max{ f (k) k : k > 0}. Let k 0 ≥ 0. The optimal sequence, k * t → k s as t → +∞, if S is high enough.
Proof : We just consider Case 2 in the proof of the previous Proposition : R * T∞-1 ≤ R and R * T∞-2 ≤ R. We have, from the Euler conditions

f (k * T∞-1 ) ≤ φ (R * T∞-1 ) φ (R * T∞-2 ) ≤ φ (0) φ ( R) < f (0). Observe that f (k) > f (0) for k ∈ [0, k s ]. Hence k * T∞-1 > k s > k I .
The optimal sequence {k * t } t≥T∞ converges therefore to k s .

In the following proposition, we assume R = +∞.

Proposition 10 Assume R = +∞, φ(R) = aR, a > 0 and 1 < f (0) ≤ 1 β ≤ max{ f (k) k : k > 0}. Let k 0 ≥ 0. The optimal sequence, k * t → k s as t → +∞, if S is high enough.
Proof : Let ( S ν ) be a sequence which converges to +∞. We consider two cases. Case 1: For any ν, the optimal sequence (R

* ν t ) verifies, R * ν 0 = S ν . Let k ν 0 satisfy f (k ν 0 ) = f (k 0 ) + aS ν . For ν large enough, k ν 0 > k c . An optimal sequence (k * ν t )
is also an optimal sequence for the convex-concave optimal growth-model with initial endowment equal to k ν 0 . Since this one is larger than the critical value k c , the optimal path (k * ν t ) will converge to the high steady state k s . And the proof is over. Case 2. From Proposition 5, there exists T ∞ such that:

c * T∞-2 + k * T∞-1 = f (k * T∞-2 ) + aR * T∞-2 c * T∞-1 + k * T∞ = f (k * T∞-1 ) + aR * T∞-1 c * T∞ + k * T∞+1 = f (k * T∞ ) c * t + k * t+1 = f (k * t ), ∀t ≥ T ∞ + 1. We have f (k * T∞-1 ) ≤ u (c * T∞-2 ) βu (c * T∞-1 ) ≤ φ (R * T∞-1 ) φ (R * T∞-2 ) = 1.
We cannot have k * T∞-1 = 0, since f (0) > 1. Hence k * T∞-1 ≥ k which is the unique point with f

( k) = 1. Moreover, k > k s > k c . Let k 0 satisfy f (k 0 ) = f (k * T∞-1 ) + aR * T∞-1 . Then, k 0 > k * T∞-1 > k s > k c . The sequence (k * t ), t = T ∞ -1, .
.., +∞ is also an optimal solution to the convex-concave optimal growth-model with initial endowment equal to k 0 . Since k 0 > k c , the path (k * t ), t = T ∞ -1, ..., +∞ converges to the high steady state.

Remark 2 Proposition 10 shows that the overshooting effect exists when S is large enough. Indeed, if we are in Case 1 of the proof, then when S is large, the value k 0 defined by f (k 0 ) = f (k 0 ) + φ(S) will be larger than k s . From Dechert and Nishimura [START_REF] Dechert | A complete characterization of optimal growth paths in an aggregate model with a non-concave production function[END_REF], the optimal path (k * t ) will be decreasing and converges to k s . If we are in Case 2, then, from the proof, there exists k * T∞-1 > k s . Remark 3 We will make a small change in H2 by dropping the assumption f (+∞) < 1. Assume f (k) = Ak, A > 1 and φ(R) = aR. Then it is optimal to exhaust the resource at period 0. Indeed, the Euler conditions will be:

A = f (k * t+1 ) ≤ φ (R * t+1 ) φ (R * t ) if R * t+1 > 0 and A = f (k * t+1 ) ≥ φ (0) φ (R * t ) = 1 if R * t+1 = 0.
¿From these inequalities, since A > 1, we cannot have R * t+1 > 0, for some t ≥ 0 since

φ (R * t+1 ) φ (R * t ) = 1. Hence R * t+1 = 0, ∀t ≥ 0, and R * 1 = S. Observe that k * t → +∞ if A > 1
β . However, it seems not realistic to completely exhaust the resource in one period. Actually, in our discrete time model, one period may be many years. Our story tells that, in developed countries which possess non-renewable resources, it is optimal to exhaust it quickly in order to build a large initial capital stock and then converge faster to the steady state.

Competitive Equilibrium With Tax/Subsidy

In our intertemporal economy, there is a single firm which produces, with a technology represented by the function f , an aggregate good which can be consumed or used as physical capital. This firm also imports this aggregate good. The importations are covered by the exportation of the natural resource that the firm extracts. Since we face increasing returns for low levels of capital, we will define an equilibrium with a tax/subsidy scheme to firms, which will be supported by the consumer or redistributed to her as a lump sum transfer. The scheme is defined as follows. If the value of the input is larger than the value of the output, then firms will receive a subsidy equal to the difference. A tax will be defined analogously in the reverse case.

Let {k t } t=1,2,..,+∞ be a firm production plan. Formally, if (p t ) is the sequence of prices of the aggregate good, r is the price of initial capital stock k 0 , and {σ t (.)} t is a system of subsidy, then firm solves the problem

Π = max (kt),(Rt) +∞ t=0 p t (f (k t ) -k t+1 ) -rk 0 + +∞ t=0 σ t (k t ) + +∞ t=0 p t φ(R t )
considering the tax/subsidy scheme as given, and under the constraints: (

∀t, 0 ≤ k t+1 ≤ f (k t ) + φ(R t ), 0 ≤ R t , +∞ t=0 R t ≤ S,
1) c * ∈ l ∞ + , k * ∈ l ∞ + , R * ∈ l ∞ + , p * ∈ l 1 + , r * ≥ 0, {p * , r * } = {0 , 0}. (2
) Given {p * , r * , σ * (.)}, {k * , R * } solve the problem of the firm, i.e.

Π * = max (kt),(Rt) +∞ t=0 p * t (f (k t ) -k t+1 ) -r * k 0 + +∞ t=0 σ * t (k t ) + +∞ t=0 p * t φ(R t ) = +∞ t=0 p * t (f (k * t ) -k * t+1 ) -r * k 0 + +∞ t=0 σ * t (k * t ) + +∞ t=0 p * t φ(R * t ) .
(3) Given {p * , r * , σ * (.)}, c * solve the consumer's problem:

+∞ t=0 β t u(c * t ) = max (ct) +∞ t=0 β t u(c t ) under the constraints +∞ t=0 p * t c t ≤ Π * + r * k 0 - +∞ t=0 σ * t (k * t ). (
) Market Clearing: ∀t, c * t + k * t+1 = f (k * t ) + φ(R * t ), 4
Proposition 11 Assume H1, H2, H3, φ (0) > 1 and k 0 > 0. Moreover, we assume (i) either f (0) > 1 β , (ii) or the assumptions in Proposition 8 or Proposition 9 are fulfilled. Let {c * , k * , R * } be a solution to our problem (P). Define:

∀t, p * t = β t u (c * t ), r * = p * 0 f (k * 0 ), and σ * t (k) = p * t f (k * t )k -p * t f (k).
Then the list {c * , k * , R * , p * , r * , σ * (.)} is a competitive equilibrium. Moreover, the equilibrium profit of the firm is positive.

Proof : Obviously, {c * , k * , R * } ∈ l ∞ ×l ∞ ×l ∞ . We now prove that {(β t u (c * t )) t } ∈ l 1 . Indeed, under our assumptions, the optimal path {k * t } t converges to the high steady state k s and the optimal consumptions converge to

c s = f (k s ) -k s > 0. Hence +∞ t=0 β t u (c * t ) < +∞.
We now prove that, given {p * , r * , σ * (.)}, {k * , R * }, solve the problem of the firm. First, observe that there exists λ > 0 and a non-negative sequence µ such that ∀t,

p * t φ (R * t ) = β t u (c * t )φ (R * t ) = λ -µ t , and µ t R * t = 0,
and from Euler conditions:

∀t, p * t f (k * t ) = p * t-1 .
Now, take a feasible sequence from k 0 , (k 0 , k 1 , ..., k t , ...) and let

T = T t=0 p * t (f (k * t ) -k * t+1 ) -r * k 0 + T t=0 σ * (k * t ) + T t=0 p * t φ(R * t ) - T t=0 p * t (f (k t ) -k t+1 ) -r * k 0 + T t=0 σ * (k t ) + T t=0 p * t φ(R t ) .
Then we have:

T ≥ T t=1 p * t f (k * t ) -p * t-1 (k * t -k t ) -p * T (k * T +1 -k T +1 ) + T t=0 p * t φ (R * t )(R * t -R t ) = -p * T (k * T +1 -k T +1 ) + λ T t=0 (R * t -R t ) - T t=0 µ t R * t + T t=0 µ t R t ≥ -p * T k * T +1 + λ T t=0 (R * t -R t ). Since +∞ t=0 R * t = S ≥ +∞ t=0 R t , we have lim T T ≥ lim T {-p * T k * T +1 }. But k * T +1 converges to k s . Since +∞ t=0
p * t < +∞, we have p * t → 0. Therefore, lim T T ≥ 0. We now prove that, given {p * , r * , σ * (.)}, c * solves the consumer's problem. Indeed, let c satisfy

+∞ t=0 p * t c t ≤ Π * + r * k 0 - T t=0 σ * (k * t ).
We have p * t φ(R t ) for any feasible sequences (k 0 , k 1 , ..., k t , ...), (R 0 , R 1 , ..., R t , ...). The sequences (k 0 , 0, ..., 0, ..

Summary of the main results and conclusion

We summarize below the main results, according to the characteristics of the technology.

(a) High marginal productivity of capital Assume φ (0) < +∞ and F (0) > ρ + δ. Then the optimal capital path (k * t ) converges to the high steady state k s , with F (k s ) = ρ + δ. The stock of non-renewable resource is exhausted in finite time. (b) Intermediate marginal productivity of capital Assume φ (0) < +∞ and δ < F (0) ≤ ρ + δ ≤ max{ F (k) k + 1 -δ : k > 0}. The stock of non-renewable resource is exhausted in finite time.

(b.1) If the production function F is concave, then the optimal capital path converges to zero.

(b.2) If the production function is convex-concave, the revenue function is linear (i.e. the price is inelastic with respect to the demand) in a neighborhood of the origin, the initial resource stock is large enough and F (k I ) = +∞, then the optimal capital stock converges to the high steady state k s .

(b.3) We drop the assumption that φ is linear in a neighborhood of the origin. We maintain the conditions that the initial resource stock is large and F (k I ) = +∞. If the maximum of the revenue function R is large and the marginal productivity of capital at the origin F (0) is high enough,but less than the sum of the social discount rate ρ nd the depreciation rate δ, then the optimal capital stock converges to the high steady state k s . (c) Low marginal productivity of capital Assume φ (0) < +∞ and F (k) < δ, ∀k. (c.1) There exists T such that k * t = 0, ∀t > T . (c.2) The optimal capital path vanishes for any k 0 small enough. (c.3) Assume that the revenue function is linear and the utility function CRRA. Given k 0 , the optimal capital path vanishes when the initial resource stock S is large.

We have then shown that exhaustible resources can, under certain circumstances among which the most important is a high marginal productivity of capital at the origin compared with the social discount rate, allow a developing economy to escape from the poverty trap. The initial abundance of the resource and the value of the maximum marginal revenue that can be obtained by selling abroad the resource extracted are also determining. If the initial resource stock is large and if it is possible to extract a large amount of resource immediately, it is possible to escape from the poverty trap even if the marginal productivity of capital at the origin is intermediate. On the contrary, in the same case but with a low marginal productivity of capital, the economy consumes first its resource and then collapses when it it exhausted.

Finally, we prove, by using a tax/subsidy scheme for firms, that any optimal path may be decentralized in a competitive equilibrium.

Definition 1

 1 and k 0 is given.There is one representative consumer who owns the firm and the initial capital stock k 0 . Her problem is max(ct) +∞ t=0 β t u(c t ) under the constraints +∞ t=0 p t c t ≤ Π + rk 0 -+∞ t=0 σ t (k t ),and c t ≥ 0, ∀t. Let us recall that l ∞ = {x : sup t |x t | < +∞} and l 1 = {p : +∞ t=0 |p t | < +∞}. The list {c * , k * , R * , p * , r * , σ * (.)}, is a competitive equilibrium of our economy if:

  ) and (R * t ) t=10,..,+∞ are feasible. Therefore,Π * ≥ p * 0 f (k 0 ) -r * k 0 + p * 0 f (k 0 ) -p * 0 f (k 0 ) + +∞ t=0 p * t φ(R * t ) > 0 since p * 0 f (k 0 ) -r * k 0 + [p * 0 f (k 0 ) -p * 0 f (k 0 )] = 0,from the very definition of r * .

  , market clearing condition is obviously satisfied. To prove that the profit, at equilibrium, of the firm is positive, observe thatΠ * ≥ ) -k t+1 ) -r * k 0 +

	+∞ t=0 t (c Finally+∞ β t u(c * t ) -+∞ t=0 β t u(c t ) ≥ +∞ t=0 β t u (c * t )(c * t -c t ) = +∞ p * t=0 p * t (f (k t +∞ t=0 +∞ σ * t (k t )+ t=0
	t=0

* t -c t ) ≥ 0 since +∞ t=0 p * t c * t = Π * + r * k 0 -T t=0 σ * (k * t ).

In the same spirit, Eliasson and Turnowsky[START_REF] Eliasson | Renewable resources in an endogenously growin economy: balanced growth and transitional dynamics[END_REF] study the growth of a small economy exporting a renewable resource to import consumption goods, with a reference to fish for Iceland, or forestry products for New-Zealand.

Assume f (k I ) = +∞. Then, for any a ≥ 0, we have a unique solution {k * 1 (a), ..., k * t (a), ....}. Moreover, k * 1 (a) > k I , k * 1 (a) decreases while f (k * 1 (a)) + a increases, when a increases.

Proof : Under the assumption that f (0) < 1 β < max{ f (k) k : k > 0}, when k 0 > k I and a = 0, any optimal path will be bounded below by k I (see Dechert and Nishimura [START_REF] Dechert | A complete characterization of optimal growth paths in an aggregate model with a non-concave production function[END_REF]). We just consider the feasible paths which are bounded below by k I . In this case, the constraints will be strictly concave, since the function f is strictly concave for k > k I . Hence the solution will be unique. Moreover the Value function is strictly concave and differentiable when a = 0.

Since

> k I , it will still be true when a > 0 small enough. We have the Bellman equation

Assume that a increases and f (k * 1 (a))+a decreases. In this case, k * 1 (a) decreases, and the left-hand side of (5) decreases. But the right-hand side increases since V (k) and f (k) are decreasing functions for k > k I . We have a contradiction.

It is easy to check that k * 1 (a) decreases when a is small and increases. Assume there exists a, the maximum value of a such that k * 1 (a) ≥ k I . Let a converge to a. In this case, k * 1 (a) converges to k I . For a < a, we have the Euler condition:

.

Taking the limits we get a contradiction:

Hence, for all a ≥ 0, k * 1 (a) > k I . We can prove as before, when a is small, that k * 1 (a) decreases while f (k * 1 (a)) + a increases, when a increases.

Proposition 8 Assume there exists R ∈ (0, R) such that φ(R) = aR, a > 0 when 0 ≤ R ≤ R, and

Define k 0 by f (k 0 ) = φ( R). Assume k 0 > k I . Assume moreover that f (k I ) = +∞. Let k 0 ≥ 0. The optimal sequence, k * t → k s as t → +∞, if S is high enough.


Javier Couto
email: jcouto@fing.edu.uy

Jean-Luc Minel
email: jminel@u-paris10.fr

A linguistic and navigational knowledge approach to text navigation

We present an approach to text navigation conceived as a cognitive process exploiting linguistic information present in texts. We claim that the navigational knowledge involved in this process can be modeled in a declarative way with the Sextant language. Since Sextant refers exhaustively to specific linguistic phenomena, we have defined a customized text representation. These different components are implemented in the text navigation system NaviTexte. Two applications of NaviTexte are described.

Introduction

Text navigation has several interpretations. Usually, this term refers to hypertext systems, which offer the possibility to activate hyperlinks, moving the reading point from a text unit (source) to another one (target), this change being intra or intertextual. From our point of view, this conception presents some limitations. First, the hyperlink activation is not assisted. In other words, imprecise, poor or no information is provided to the reader before s/he activates the link. Second, the reader does not know where the movement will be carried out in the text (before or after the reading point or outside the text), which generates the "lost in hyperspace" problem [START_REF] Edwards | Lost in hyperspace: cognitive mapping and navigation in a hypertext environment[END_REF]. Finally, hyperlinks are embedded in the hypertext. Therefore, there is no clearly distinction between text constituents and navigation knowledge. In addition, by not explicitly modeling this knowledge, it is not reusable.

Different solutions have been proposed to address the problems mentioned. Some researchers [START_REF] Danielson | Web navigation and the behavorial effects of constantly visible maps[END_REF] have tried to mitigate the lost in hyperspace problem offering global maps where the reading point is clearly identified. Adaptive hypertext [START_REF] Mathe | A User-Centered Approach to Adaptive Hypertext based on an Information Relevance Model[END_REF][START_REF] Brusilovsky | Methods and techniques of adaptive hypermedia[END_REF] relying on user model, proposes to modify the way the text is shown on the screen. Dynamic hypertext [START_REF] Bodner | Dynamic hypertext: querying and linking[END_REF] computes the value of hyperlinks using several criteria such as text similarity or predefined relations. In this approach, a hyperlink is defined as a query returning a text node.

In some way, our conception of text navigation is related to the notion of computed query, but rather than taking into account criteria depending on the reader, the target is computed by exploiting linguistic information in texts. Moreover, the queries are not placed in texts but they are encapsulated as knowledge by a specific language (Sextant), which allows isolating the navigational knowledge to create knowledge bases. Both texts and queries (navigational knowledge) are interpreted by NaviTexte, which manages the interactions with a reader.

The remainder of this paper is organized as follows. In the next section, we discuss our approach to text navigation. The third section describes a navigational knowledge modeling language called Sextant. The fourth section details the text navigation system NaviTexte. The fifth section describes two applications of NaviTexte. Then we address the evaluation aspects of our approach. At last, conclusions are presented.

Defining text navigation

Our conception of text navigation lies in the hypothesis that navigating through texts is the expression of a cognitive process related to specific knowledge [START_REF] Minel | Filtrage sémantique. Du résumé à la fouille de textes[END_REF][START_REF] Couto | Navigation textuelle: Représentation des textes et des connaissances[END_REF]. More precisely: we claim that a reader moves through texts applying some knowledge to exploit linguistic information present in texts (e.g. discursive markers). Moreover, we claim that this knowledge may be articulated in a declarative way (cf. Sec. 3) relying on information in texts coded, on the one hand, by its structure, and, on the other hand, by specific annotations.

The main difference between classic hypertext and our conception of navigation lies on the status of texts and on the definition of navigational knowledge. In the case of hypertext, the visualization of a text is unique and navigational knowledge is encoded (embedded) in the text. In our approach, there are several ways to visualize a text [START_REF] Couto | Modélisation des connaissances pour une navigation textuelle assistée. La plate-forme logicielle NaviTexte[END_REF], each way called text view, and for each view, different navigational knowledge may be defined. As a consequence, the navigation is not guided by the author, compared to hypertext navigation where s/he determines the links, but it is the result of an interpretation process made by the reader, relying on text structure and annotations. Our conception of navigation (cf. Fig. 1) relies on four elements: i) a text representation allowing linguistic specific phenomena and annotations (see [START_REF] Couto | Modélisation des connaissances pour une navigation textuelle assistée. La plate-forme logicielle NaviTexte[END_REF]; ii) a language to model navigational knowledge (cf. Sec. 3); iii) an agent (an individual or a software) able to encode such knowledge; iv) a system, called NaviTexte, to interpret and apply knowledge to a specific text (cf. Sec. 4).

Modeling navigational knowledge: the Sextant language

To allow the unambiguous isolation of navigational knowledge we need a formal modeling language. We want to model the knowledge applied by a reader to move through texts, claiming that this knowledge exploits linguistic information present in texts. We do not say that this is the only way a reader may move through texts (e.g. strolling courses proposed by [START_REF] Géry | Un modèle d'hyperdocument en contexte pour la recherche d'information structurée sur le Web[END_REF] is a counterexample), but we say that this is the kind of way than we are going to model. Different views of a text and the fact that each view contains specific indications of the possible reading courses constitute the heart of the language.

Knowledge modules ant text views

A text view may be a full view or a partial view focused in some specific phenomena present in the text (for example a view of all discourse referents).

The constituent elements of a view are formalized in a view description, which contains the type of view, its parameters, the creation constraints (i.e. conditions to verify by the TU of the view) and the navigation operations (see next section). At present, four types of view have been defined: plaintext, tree, graph and temporality. The three firsts types are described in [START_REF] Couto | Modélisation des connaissances pour une navigation textuelle assistée. La plate-forme logicielle NaviTexte[END_REF]. The last one graphically represents temporality in texts and a complete description is in (Battistelli et al., 2006).

Several view descriptions may be gathered by the encoder in an entity called navigational knowledge module. The creation of a view may be conceptualized as the application of a view description to a specific text. Thus, the application of a module implies the creation of a set of text views.

The navigation operation

The notion of computed query mentioned in section 1 is formalized in Sextant as a navigation operation, which links a source TU to a target TU. In classic hypertext systems one must explicitly connect the specific source to the specific target. For example, if a reader wants, for all definitions in a scientific paper, to move from one to the following one, several hyperlinks must be defined. In our approach we specify the source and the target using conditions. As a result, we can abstract, for example, the navigational knowledge that states "go from one definition to the following one", being "definition" one of the TU annotations.

We can specify several conditions for the source and the target. We say that a navigation operation is available for a TU if this TU verifies the source conditions. A text navigation system should find the TU that verifies the target conditions. As several TU in the text may verify them, we need a way of disambiguation. This is done by the orientation parameter, which specifies the direction of the target search by using one of these options: first, last, forward(i), backward(i). First and last indicate that the search of the target is absolute: the TU to select will be the first (respectively the last) TU that verify the conditions. Forward(i) and backward(i) indicate that the search is carried out relatively to the source (before or after) and indexed by the integer i. For example, "forward(3)" is interpreted as the third TU, after the source, of all the TU verifying the target conditions.

The conditions language

The conditions language is an important component of Sextant ant it is composed by basic conditions, TU elements existence conditions, hierarchical conditions and non-hierarchical conditions.

Basic conditions concern TU's attributes and annotations. For this kind of condition we use a notation close to the pattern notion. We define an operator called TU, having five operands that correspond to the following properties: type, number, level, annotations and string. With the three first operands and the fifth one, we denote constraints of equality, inequality, order, prefix, suffix and substring occurrence. The fourth operand is used to indicate the existence or non-existence of annotations, whether it is an annotation name, a value or a name-value pair.

For TU elements existence conditions, we define operators without operands to verify if a TU has annotations, string, title, parent and children.

For conditions dealing with hierarchical relationship between different TU, a set of unary operators have been defined, taking a basic condition as an argument. For example, the isAscendant operator verifies if a TU is the ascendant of another TU specified by a basic condition. The other operators are: isParent, isChild, isSibling, isDescendant, hasInTitle, isInTitle. We would like to draw attention to the fact that these operators allow to move through the hierarchy of TU from a starting TU [START_REF] Couto | Modélisation des connaissances pour une navigation textuelle assistée. La plate-forme logicielle NaviTexte[END_REF].

Non-hierarchical conditions concern constructed units' attributes and annotations as well as TU constitution.

All conditions may be combined using the classic logic operators OR, AND and NOT. Figure 2 presents an example of a language expression that formulates the following condition: TU of type "NP", having an annotation of name "discourse referent", for which it exists, among its descendants, a TU of type "paragraph" not having an annotation of name "semantic label" whose value is "conclusion". This condition means: noun phrases being a discourse referent that does not occur in a concluding paragraph.

NaviTexte: a text navigation system

Several adaptive navigation systems have been proposed [START_REF] Benyon | Developing Adaptive Systems to Fit Individual Aptitudes[END_REF][START_REF] Kaplan | Adaptive Hypertext Navigation Based On User Goals and Context[END_REF][START_REF] Boyle | MetaDoc: An Adaptive Hypertext Reading System[END_REF][START_REF] Brusilovsky | ISIS-Tutor: An adaptive hypertext learning environment[END_REF][START_REF] Brusilovsky | ELM-ART: An Intelligent Tutoring System on World Wide Web[END_REF]. While they are goal specific (learning, tutoring, reading, etc.), NaviTexte [START_REF] Couto | Modélisation des connaissances pour une navigation textuelle assistée. La plate-forme logicielle NaviTexte[END_REF]) is a generic text navigation system implementing our approach. This means that, depending on texts and knowledge modules, NaviTexte may be used, for example, as a learning, tutoring or reading system. Another important difference is that NaviTexte gives the user the liberty to navigate through the text following its own interests (the system propose -the reader chooses), while the mentioned systems try to maintain a user stuck to a given route (the user choosesthe system propose) [START_REF] Höök | Evaluating Adaptive Navigation Support[END_REF].

NaviTexte consists of sub-systems dealing with: text representation, navigational knowledge, visual representation and user interaction. The first one builds a text representation in memory from a text annotated manually or by dedicated software [START_REF] Cunningham | GATE: A Framework and Graphical Development Environment for Robust NLP Tools and Applications[END_REF][START_REF] Bilhaut | Indexation discursive pour la navigation. intradocumentaire: cadres temporels et spatiaux dans l'information géographique[END_REF]. The second sub-system loads and compiles the knowledge modules. The result of this compilation is a graph of potential navigation courses that in practice is calculated as needed and stored in optimization data structures. The third sub-system calculates and displays different text views and the fourth one manages the user interaction.

The reader has the possibility to load and unload several texts and knowledge modules in the same work session. A complete description of NaviTexte may be found in [START_REF] Couto | Modélisation des connaissances pour une navigation textuelle assistée. La plate-forme logicielle NaviTexte[END_REF].

Applications of NaviTexte

Building an application with NaviTexte requires a set of texts and navigational knowledge modules. Both text representation and Sextant language have XML implementations with dedicated editors to use in case of a manual text annotation and a human knowledge encoder, respectively (cf. Fig. 1).

So far four applications have been developed: alternative automatic summarization [START_REF] Couto | Navigation textuelle: Représentation des textes et des connaissances[END_REF], the NaviLire project [START_REF] Couto | Naviguer pour apprendre[END_REF]Lunquist et al., 2006), re-reading Madame Bovary [START_REF] Couto | Navigation textuelle: Représentation des textes et des connaissances[END_REF] and temporality in texts (Battistelli et al., 2006). We present two of them to illustrate NaviTexte's potential.

NaviLire: a text linguistics application

For the past thirty years, text linguistic researchers have worked on describing linguistic markers of textual coherence in order to bring out principles of text structuring [START_REF] Lundquist | La cohérence textuelle, syntaxe, sémantique, pragmatique[END_REF]. A set of concepts and models of textual interpretation has been worked out, including for example, anaphora, connectors, mental spaces, etc. In particular, these studies have shown that even for languages apparently close like French and Danish, texts are not organized in the same way [START_REF] Lundquist | Noms, verbes et anaphores (in)fidèles. Pourquoi les Danois sont plus fidèles que les Français[END_REF]. Consequently, text linguistics has important implications in foreign language teaching, especially from a contrastive point of view, when language pairs are analyzed through texts used in authentic communication situations. It seems that the teaching of text linguistics contributes to sharpen the attention of students towards the building of well-formed texts and to stimulate their own text production. Therefore, a tool that allows the student to perceive text units that contribute to and maintain text coherence and to navigate between them, can be supposed to be an important didactic tool for teaching reading of foreign language texts, as well as producing written texts in the foreign language.

In the reading process, the student has to deal with two basic types of cognitive problems. First, s/he has to identify discourse referents in a text and choose the correct relations between the noun phrases that refer to them. Second, s/he has to identify the function and orientation intended by the sender. In the NaviLire project, navigation operations assisting the student are defined used Sextant and the texts are manually annotated by a text linguistics expert.

Navigation as an alternative to automatic summarization

Many automatic summarization systems have been proposed [START_REF] Mani | Automatic Summarization[END_REF][START_REF] Minel | Filtrage sémantique. Du résumé à la fouille de textes[END_REF]. All these systems, based on the principle of phrase, proposition or group extraction, have been confronted to two problems intrinsic to the extraction procedure: i) the rupture of text cohesion, like in cases of anaphora where the corresponding discourse referent is missing; ii) the adaptation of the summary to reader specific needs. Actually, there are no completely satisfying solutions to these problems. An alternative approach is to consider the summarizing process as a reading course belonging to the reader [START_REF] Minel | Filtrage sémantique de textes. Problèmes, conception et réalisation d'une plate-forme informatique[END_REF][START_REF] Crispino | Construction automatique de résumés. Une approche dynamique[END_REF]. Thereby, instead of extracting text fragments, we propose specific reading courses, whose specifications are based on propositions of (Endres-Niggermeyer et al., 1995) and on practice observations made in the frame of the automatic summarization system SERAPHIN evaluation [START_REF] Minel | How to appreciate the Quality of Automatic Text Summarization[END_REF] and the Filtext framework [START_REF] Minel | Résumé automatique par filtrage sémantique d'informations dans des textes, Présentation de la plate-forme FilText[END_REF]. These works showed that professional summarizers are interested by discourse categories that they retrieve by exploiting text organization and lexical markers. They also showed that these professionals navigate through texts using heuristics acquired by experience. For example, they begin by reading the conclusion, and then they continue by looking, in the introduction, for nominal groups that occurred in the conclusion. This is the knowledge we have modeled with Sextant.

A specific reading course specifies, on the one hand, the kind of discursive category searched by a reader (e.g. a conclusion, a definition, an argument, a hypothesis, etc.1 ) and on the other hand, the course in which the segments that linguistically enunciate these categories (typically phrases) must be presented to the reader.

To carry out these reading courses, it is necessary to locate the discursive categories involved and mark them in the text. For this purpose, we used ContextO [START_REF] Minel | Résumé automatique par filtrage sémantique d'informations dans des textes, Présentation de la plate-forme FilText[END_REF]. A reading course example is presented in Fig. 3. The reading point is positioned over the first TU, a phrase in this case, annotated "Thematic Announcement". When the user clicks over the TU, NaviTexte recommends her/him four navigation operations. The first one suggests bringing her/him to the following "Thematic Announcement". The others ones suggest going to the first "Conclusion", the first "Recapitulation" and the first "Argument". For a given TU, each navigation operation available has three possible states (and there is a visual semantic associated to states), depending if it has been executed (bold font and "*" prefix) or not (normal font and no prefix), and if it exists a TU target (clickable menu option) or not (non-clickable menu option).

Figure 3. Automatic summarization courses. These kinds of suggestions (i.e. showing available navigation operations for a TU) are made all over the reading process. Consequently, along her/his reading continuum, the reader is assisted by the display of a specific set of signs, and there is no rupture of cohesion because s/he is able to continually see all the text (Battistelli and Minel, 2006).

Evaluations

There are few studies of adaptive navigation in hypermedia systems and most of them are focused in measures such as the number of visited nodes or the task completion time [START_REF] Höök | Evaluating Adaptive Navigation Support[END_REF]. Are we interested in this kind of measures? Being NaviTexte a generic text navigation system, we think that what it has to be evaluated are the different applications. Each application requires pertinent measures. For example, in NaviLire, the number of nodes or the time factor seems less useful that the comprehension of the text analyzed.

So far, NaviLire has been put into practice on a small scale only, viz. in the teaching of French texts and text linguistics to Danish language students in the 4th year of Language and Communication studies at the Copenhagen Business School. A pilot experiment was carried out in order to evaluate the effects of using the program.

The first results are based on forty answers, of which 35 concern questions about the content of the text. These results show that the navilistes (people using NaviLire) have a better comprehension performance than the papiristes (people using paper and pencil) for 14 questions, an identical performance for 16 other questions, and a poorer performance for 5 questions (cf. [START_REF] Lundquist | NaviLire, Teaching French by Navigating in Texts[END_REF] Evaluations of the alternative automatic summarization approach are ongoing. Our main problem is that automatic summarization evaluations, well known as difficult to carry out, typically compare to summaries made by professional summarizers [START_REF] Mani | Automatic Summarization[END_REF][START_REF] Minel | Filtrage sémantique. Du résumé à la fouille de textes[END_REF]. On the one hand, since we do not create a summary, we do not have an object to compare. On the other hand, since we have modeled the professional heuristics, we cannot compare the behavior of our system to theirs because it is exactly what it has been modeled.

Conclusions and future work

We have presented our approach to text navigation conceived as a cognitive process that exploits linguistic information present in texts. We have defined it and explained the main differences with the hypertext navigation approach. The four elements needed to implement our approach are described: a text representation, the navigation knowledge modeling language Sextant, the knowledge encoding agents (via applications) and the NaviTexte system.

Two distinct applications of NaviTexte have been presented, showing the versatility of our approach. The quantitative results of our experimentation with Danish students learning French confirm the improvement obtained by using text navigation.

A long term consequence of modeling navigational knowledge is the creation of knowledge bases exchangeable and reusable. Actual collaborations are reusing the knowledge coming from the NaviLire project into others e-learning projects.

We think that our approach may have a significant impact on the way text is being read when its amount or nature does not allow sequential reading (e.g. the Web). Related to last works in Web Wise, we plan to couple our approach to Semantic Web approaches to exploit existing annotations.

Figure 1 .

 1 Figure 1. Elements of text navigation.

Figure 2 .

 2 Figure 2. Conditions language example.

Table 1 )

 1 .

	#questions	%

Table 1 .

 1 Comparison of navilistes and papiristes

For more details on different categories or on what empirical basis were these types derived, see(Minel et al.,

2001).


Jean Yves Audibert
email: audibert@certis.enpc.fr

Rémi Munos
email: remi.munos@inria.fr

Csaba Szepesvári

Use of variance estimation in the multi-armed bandit problem

An important aspect of most decision making problems concerns the appropriate balance between exploitation (acting optimally according to the partial knowledge acquired so far) and exploration of the environment (acting sub-optimally in order to refine the current knowledge and improve future decisions). A typical example of this so-called exploration versus exploitation dilemma is the multi-armed bandit problem, for which many strategies have been developed. Here we investigate policies based the choice of the arm having the highest upper-confidence bound, where the bound takes into account the empirical variance of the different arms. Such an algorithm was found earlier to outperform its peers in a series of numerical experiments. The main contribution of this paper is the theoretical investigation of this algorithm. Our contribution here is twofold. First, we prove that with probability at least 1 -β, the regret after n plays of a variant of the UCB algorithm (called β-UCB) is upper-bounded by a constant, that scales linearly with log(1/β), but which is independent from n. We also analyse a variant which is closer to the algorithm suggested earlier. We prove a logarithmic bound on the expected regret of this algorithm and argue that the bound scales favourably with the variance of the suboptimal arms.

Introduction and notations

A K-armed bandit problem (K ≥ 2) is defined by random variables X k,t (1 ≤ k ≤ K, t ∈ N + ), where each k is the index of an "arm" of the bandit and t represents time. Successive plays of arm k yield rewards X k,1 , X k,2 , . . . which are independent and identically distributed (i.i.d.) according to an unknown distribution. Independence also holds for rewards across the different arms, i.e. for any t ∈ N + and 1 ≤ k < k ′ ≤ K, (X k,1 , . . . , X k,t ) and (X k ′ ,1 , . . . , X k ′ ,t ) are independent. Let µ k and σ 2 k be respectively the (unknown) expectation and variance of the rewards coming from arm k. For any k ∈ {1, . . . , K} and t ∈ N, let X k,t and V k,t be their respective empirical estimates:

X k,t 1 t t i=1 X k,i and V k,t 1 t t i=1 (X k,i -X k,t ) 2 ,
where by convention X k,0 0 and V k,0 0. An optimal arm is an arm having the best expected reward k * ∈ argmax k∈{1,...,K} µ k .

For the sake of simplicity we assume that there is a single optimal arm. The proofs and hence the results hold when there are multiple such arms. We denote quantities related to the optimal arm by putting * in the upper index. In particular, µ * = max k µ k . The expected regret of an arm k is ∆ k µ * -µ k .

A policy is a way of choosing the next arm to play based on the sequence of past plays and obtained rewards. More formally, it is a mapping from ∪ t∈N {1, . . . , K} t ×R t into {1, . . . , K}.

Let T k (t) be the number of times arm k is chosen by the policy during the first t plays. Let I t denote the arm played by the policy at time t.

We define the cumulative regret of the policy up to time n as Rn nµ * -n t=1 X t,TI t (t) . We also define the cumulative pseudo-regret

R n = K k=1 T k (n)∆ k .
The expected cumulative regret of the policy up to time n is

R n nµ * -E n t=1 X t,TI t (t) = K k=1 E[T k (n)]∆ k .
2 The β-UCB policy

The algorithm

Assume that the rewards are bounded. Then, without loss of generality, we may assume that all the rewards are almost surely in [0, 1]. Let 0 < β < 1 be some fixed confidence level. Consider the sub-confidence levels β s defined as

β s β 4Ks(s+1) (1) Let B k,s X k,s + 2V k,s log(β -1 s ) s + 16 log(β -1 s ) 3s ∧ 1
with the convention 1/0 = +∞. β-UCB policy: At time t, play an arm maximizing B k,T k (t-1) .

Let us now explain the choice of B k,T k (t-1) . The quantity essentially comes from the following theorem.

Theorem 1 Let X 1 , . . . , X t be i.i.d. random variables taking their values in [0; 1]. Let µ = EX 1 be their common expected value. Consider the empirical expectation µ t and standard deviation σ t ≥ 0 defined respectively as

µ t = t i=1 X i t and σ 2 t = t i=1 (X i -µ t ) 2 t .
With probability at least 1 -β, we have

µ ≤ µ t + σ t 2 log(3β -1 ) t + 16 log(3β -1 ) 3t . ( 2
)
and µ ≥ µ t -σ t 2 log(3β -1 ) t -16 log(3β -1 ) 3t . (3)
Proof 1 See Section A.1.

Note that (2) is useless for t ≤ 5 since its r.h.s. is larger than 1. We may apply Theorem 1 to the rewards X k,1 , . . . , X k,s and the confidence level 3β s . Since 1≤k≤K;t≥1 3β k,t = 3β/4, it gives that with probability at least 1 -3β/4 ≥ 1 -β, for any s ∈ N and k ∈ {1, . . . , K}, we have µ k ≤ B k,s .It means that with confidence level β, for any time t ≥ 1, after the first t -1 plays, the user of the policy knows that the expected reward of arm k is upper bounded by B k,T k (t-1) . The user of the β-UCB policy chooses his plays only through these upper confidence bounds (UCB).

Properties of the β-UCB policy

We start with a deviation inequality for the number of plays of non-optimal arms.

Theorem 2 For any non-optimal arm k (i.e. ∆ k > 0), consider u k the smallest integer such that

u k log[4Ku k (u k +1)β -1 ] > 8σ 2 k ∆ 2 k + 16 ∆ k . ( 4
)
With probability at least 1 -β, the β-UCB policy plays any non-optimal arm k at most u k times.

Proof 2 See Section A.2.

This means that with high probability, the number of plays of non-optimal arms is bounded by some quantity independent of the total number of plays.

Theorem 2 directly leads to upper bounds on the cumulative regret of the policy up to time n and on its expected value.

Since u k depends on the parameter β, we will now write it u k,β . The following lemma gives more explicit bounds on u k,β .

Lemma 1 Let w k = 8σ 2 k ∆ 2 k + 16 ∆ k . We have u k,β ≤ 5w k log(w k Kβ -1 )and u k,β ≤ w k log(4Kβ -1 ) + 2w k log 6w k log(w k Kβ -1 ) .
The first bound is the simplest but the least accurate. In the second one, the leading term is the first one (when β goes to 0).

Proof 3 See Section A.3.

Theorem 3 With probability at least 1 -β, for any time n, the cumulative regret of the β-UCB policy satisfies

K k=1 T k (n)∆ k ≤ k∈K [u k,β ∧ n]∆ k (5)
Besides for any positive integer n, the expected cumulative regret of the 1/n-UCB up to time n satisfies

K k=1 E[T k (n)]∆ k ≤ k∈K (1 + u k,1/n ) ∧ n ∆ k ≤ C 1 k∈K σ 2 k ∆ k + 1 log(Kn) ∧ n∆ k ≤ C 2 log(2n) k =k * 1 + σ 2 k ∆ k (6)
for some universal constants C 1 and C 2 .

Proof 4 The first assertion is a direct consequence of Theorem 2. For the second assertion, the first inequality comes from

T k (n) ≤ n and ET k (n) ≤ P[T k (n) > u k ]n + P[T k (n) ≤ u k ]u k .
The second inequality uses Lemma 1. The third inequality follows by considering two cases: either K > n (i.e. not enough time to explore all the arms), then the property is trivial, or K ≤ n which implies log(Kn) ≤ 2 log(n) for any n ≥ 1.

3 Bounds for the expected regret

Adaptive β-UCB

As far as results in expectation are concerned (see second part of Theorem 3), we need to take β dependent on the time horizon (i.e. the total number of arms to be drawn) to obtain a regret bound of order C log n.

Schematically an algorithm which needs to know its time horizon to have a (log n)cumulative regret bound up to time n can be modified into an adaptive algorithm having the same cumulative regret bound (up to a multiplicative constant close to 1). This is done by the doubling trick (see [3, p.33] and references within) in which we cut the time space into intervals of length 2 2 k . For each of this epoch, we launch the algorithm independently of what happens in the other epochs. The policy knows its time horizon and leads to a cumulative regret for epoch k of order 2 k . Summing these regrets up to some time horizon T = 2 2 K , we obtain a cumulative regret of order K i=1 2 i = 2 K+1 -1, hence of order log T . For the β-UCB policy, we need neither to restart at each epoch the policy nor to cut the time space in epochs. Indeed, it suffices to take β = 1/t at time t. To decrease β when the number of arms already drawn increases is natural: when the time t increases, the exploitation of an almost optimal arm becomes more and more detrimental to the quality of the policy, so we want to be a bit more sure that the optimal one is not in other arms. Consequently, we need to have better upper confidence bound, which means that β should be taken smaller. For this adaptive policy, one can show using the time cutting argument presented above that the results given in (6) still holds.

UCB-tuned policy

Define the confidence sequences of arm k c

(k) t,s 2V k,s log(4t p ) s + 16 log(4t p ) 3s .
The following figure describes the UCB-tuned policy:

UCB-tuned policy: At time t, play an arm maximizing

X k,T k (t-1) + c (k) t,T k (t-1) ∧ 1.
A slight variation (with different confidence sequences) was proposed in Section 4 of [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF]. In their experimental study these authors have found that this algorithms outperforms most previous algorithms under a wide range of conditions. However, no theoretical analysis of this algorithm has been attempted so far. (Theorem 4 of [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF], which is a closely related result that applies to normally distributed payoffs only, is not a complete proof since it relies on some conjectures.) The next theorem shows that with p > 2, the regret of the above algorithm scales with the logarithm of the number of steps. A crucial feature of this result is that instead of scaling with 1/∆ j , the regret scales with σ 2 j /∆ j . This shows that the performance of UCB-tuned is less sensitive to whether the assumed payoff range is a good match to the true range of payoffs.

Theorem 4 Let p > 2. For any time n, the expected regret of the UCB-tuned policy is bounded by

R n ≤ 16 log(4) + p log(n) k =k * 1 + σ 2 k 2∆ k + 2 1 + 1 p -2 k =k * ∆ k .

A Proofs of the results

A.1 Proof of Theorem 1

The following inequality is a direct consequence of Bernstein's inequality (see e.g. [2, p.124]).

Lemma 2 Let W 1 , . . . , W t be i.i.d. random variables taking their values in [0; 1]. Let E = EW 1 and V = E(W 1 -E) 2 be the expectation and variance of these random variables. For any ǫ > 0, with probability at least 1 -ǫ, the empirical mean Ē = (

t i=1 X i )/t satisfies Ē < E + 2V log(ǫ -1 ) t + 2 log(ǫ -1 ) 3t . (7)
To prove Theorem 1, we apply Lemma 2 for ǫ = β/3 and three different i.i.d. random variables:

W i = X i , W i = 1 -X i and W i = 1 -(X i -EX 1 ) 2 . Let σ denote the standard deviation of X 1 : σ 2 E(X i -EX 1 ) 2 . Introduce V Var (X 1 -EX 1 ) 2 .
We obtain that with probability at least 1 -β, we simultaneously have

|µ t -µ| ≤ σ 2 log(3β -1 ) t + 2 log(3β -1 ) 3t ∧ 1 (8) and σ 2 ≤ σ 2 t + (µ -µ t ) 2 + 2V log(3β -1 ) t + 2 log(3β -1 ) 3t . (9)
Let δ be the r.h.s. of (8) and L log(3β -1 )/t Noting that V ≤ σ 2 , we have

σ 2 ≤ σ 2 t + δ 2 + δ ≤ σ 2 t + 2δ, hence successively σ 2 -2σ √ 2L -4L/3 -σ 2 t ≤ 0, and σ ≤ √ 2L + σ 2 t + 10L/3 ≤ σ t + ( √ 2 + 10/3) √ L.
Plugging this inequality in (8), we obtain

µ ≤ µ t + σ t √ 2L + 2 + 20/3 + 2/3 L ≤ µ t + σ t √ 2L + 16L/3
The reverse inequality is obtained in a similar way.

A.2 Proof of Theorem 2

Let l t log(β -1 t ) (remember that β t = β/(4kt(t + 1))). Consider the event E on which

∀t ∈ N + ∀k ∈ {1, . . . , K}    X k,t -µ k < 2σ 2 k lt t + 2lt 3t V k,t -σ 2 k < 8σ 2 k lt t + 4lt 3t ( 10
)
Let us show that this event holds with probability at least 1 -β.

Proof 5 We apply Lemma 2 with ǫ = β t and different i.i.d. random variables:

W i = X k,i , W i = 1 -X k,i , W i = (X k,i -µ k ) 2 and W i = 1 -(X k,i -µ k ) 2 .
We use that the variance of the last two random variables is bounded by

E[(X k,1 -µ k ) 4 ] ≤ σ 2 k and that the empirical expectation of (X k,i -µ k ) 2 is 1 t t i=1 (X k,i -µ k ) 2 = V k,t + (X k,t -µ k ) 2 .
We obtain that for any t ∈ N + and k ∈ {1, . . . , K}, with probability at least

1 -β t    X k,t -µ k < 2σ 2 k lt t + 2lt 3t V k,t + (X k,t -µ k ) 2 -σ 2 k < 2σ 2 k lt t + 2lt 3t Since |X k,t -µ k | ≤ 1, this last inequality leads to V k,t -σ 2 k < X k,t -µ k + 2σ 2 k lt t + 2lt
3t , which gives the second inequality of (10). Using an union bound, all these inequalities hold simultaneously with probability at least

1 -4 K k=1 t≥1 β t = 1 -β.
Now let us prove that on the event E, we have µ k ≤ B k,t and

B k,t ≤ µ k + σ k 8l t t + 8l t t (11)
Proof 6 For sake of simplicity, let us temporarily drop the k indices: e.g. B k,t , µ k , σ 2 k and V k,t respectively become B t , µ, σ 2 and V t . Introduce L t = lt t . By (10),

σ 2 -V t < √ 8σ 2 L t + 4Lt 3 . Let q(σ) = σ 2 -σ √ 2L t + (-V t - 4Lt
3 ). Since q(σ) is negative only between its two roots, the largest root gives a bound on the values σ can take when q(σ) < 0 (the "square root trick"):

σ < √ 2L t + V t + 10Lt 3 ≤ √ V t + (1 + 5/3) √ 2L t .
Plugging this inequality in the first inequality of (10), we obtain

µ t -µ < √ 2V t L t + 16Lt
3 , and in particular µ ≤ B t . For the second part of the assertion, we use

µ t ≤ µ + σ √ 2L t + 2Lt 3 V t ≤ σ 2 + σ √ 8L t + 4Lt 3 ≤ σ + √ 2L t 2
and obtain B t ≤ µ + 2σ √ 2L t + 8L t , which is the announced result.

Let Ǩ be the set of non-optimal arms: Ǩ = k ∈ K : ∆ k > 0 . For any integers u k where k ∈ Ǩ, we have

P[∃k ∈ Ǩ T k (t) > u k ] = P[∃k ∈ Ǩ T k (t) > u k ; E] + P[∃k ∈ Ǩ T k (t) > u k ; E c ] ≤ P ∃k ∈ Ǩ ∃s < t T k (s) = u k and I s+1 = k; E + P(E c ) ≤ P ∃k ∈ Ǩ ∃s < t T k (s) = u k and B k,T k (s) ≥ B k * ,T * k (s) ; E + β ≤ P ∃k ∈ Ǩ ∃s < t B k,u k ≥ µ k * or B k * ,T * k (s) < µ k * ; E + β ≤ P ∃k ∈ Ǩ B k,u k ≥ µ k * ; E + P ∃r < t B k * ,r < µ k * ; E + β ≤ P ∃k ∈ Ǩ µ k + 8σ 2 k l k,u k u k + 8l k,u k u k ≥ µ k * + 0 + β (12)
The probability in this last r.h.s. is equal to zero provided that the u k 's are large enough. Precisely, we want u k such that

t k = l k,u k /u k satisfies 8t 2 k + 2 2σ 2 k t k -∆ k < 0, equivalently dropping the k indices: t < ( √ 2σ 2 + 8∆ - √ 2σ
2 )/8. We get

u lu > 64 ( √ 2σ 2 +8∆- √ 2σ 2 ) 2 = 1 ∆ 2 √ 2σ 2 + 8∆ + √ 2σ 2 2 .
This inequality is at least satisfied when u lu > 8σ 2 ∆ 2 + 16 ∆ , which ends the proof.

A.3 Proof of Lemma 1

Proof 7 By the definition of u k , we have

u k -1 log[4Ku k (u k -1)β -1 ] ≤ w k .This implies u k ≤ 1 + w k log[4Ku 2 k β -1 ]. ( 13
)
Basic computations leads to u k ≤ w 2 k Kβ -1 . This very rough upper bound can be used to have a tight upper bound of u k . Indeed, after some simple computations using that w k ≥ 16, the first two recursive uses of (13) gives u k ≤ 5w k log(w k Kβ -1 ) and u k ≤ w k log(4Kβ -1 ) + 2w k log 6w k log(w k Kβ -1 ) , which are the announced results.

B Proof of Theorem 4 (UCB-tuned's regret)

The choice of this confidence sequence is such that, for any fixed arm index k, any pairs (s, t) satisfying 1 ≤ s ≤ t, the following holds:

P(µ k ≤ X k,s + c (k) t,s ) ≥ 1 -t -p , P(X k,s + c (k) t,s ≤ µ k + d (k) t,s ) ≥ 1 -t -p .
(14) Here

d (k) t,s 8σ 2 k log(4t p ) s + 8 log(4t p ) s .
Indeed, following the proof of Theorem 2, we derive that with probability 1 -β, we have for any fixed k,

X k,t -µ k < 2σ 2 k log(4β -1 ) t + 2 log(4β -1 ) 3t and V k,t -σ 2 k < 8σ 2 k log(4β -1 ) t + 4 log(4β -1 ) 3t . (15)
¿From this we deduce, similarly to what is done in the proof of Theorem 2, that for any s ≥ 1, with probability 1 -β, we have the two inequalities

µ k ≤ X k,s + 2V k,s log(4β -1 ) s + 16 log(4β -1 ) 3s ≤ µ k + 8σ 2 k log(4β -1 ) s + 8 log(4β -1
) s and (14) follows when choosing β = t -p . Now, pick a suboptimal arm, k (i.e., µ k < µ * ). Then defining u k,n ≥ 1 an integer-valued sequence that will be selected later, we have:

T k (n) = n t=1 I{I t =k} ≤ u k,n -1 + n t=1 I{I t =k,T k (t)≥u k,n } ≤ u k,n -1 + n t=1 I n X * T * (t) +c * t,T * (t) ≤X k,T k (t) +c (k) t,T k (t) ,T k (t)≥u k,n o ≤ u k,n -1 + n t=1 I n X * T * (t) +c * t,T * (t) ≤µ * o + n t=1 I n X k,T k (t) +c (k) t,T k (t) -d (k) t,T k (t) ≥µ k o + n t=1 I n µ * <µ k +d (k) t,T k (t) ,T k (t)≥u k,n o (16) ≤ u k,n -1 + n t=1 t s=1 I {X * s +c * t,s ≤µ * } + n t=1 t s=1 I n X k,s +c (k) t,s -d (k) t,s ≥µ k o + n t=1 t s=u k,n I n d (k) t,s >∆ k o (17)
where (16) follows as follows: Assume that X *

T * (t) + c * t,T * (t) > µ * and X k,T k (t) + c (k) t,T k (t) - d (k) t,T k (t) < µ k , and X * T * (t) + c * t,T * (t) ≤ X k,T k (t) + c (k) t,T k (t) . Then µ * < X * T * (t) + c * t,T * (t) ≤ X k,T k (t) +c (k) t,T k (t) < µ k +d (k)
t,T k (t) and so under these conditions we must have µ * < µ k +d (k) ∆ k and summing the three terms of (17) yields the logarithmic expected number of times a suboptimal arm is chosen:

E[T k (n)] ≤ log(4n p ) 8σ 2 k ∆ 2 k + 16 ∆ k + 2 + 2 p -2 ,
and the logarithmic bound on the expected regret:

R n ≤ log(4) + p log(n)

k =k * 8σ 2 k ∆ k + 16 + (2 + 2 p -2 ) k =k * ∆ k .

  t,T k(t) . The two first sums in the expression (17) are upper-bounded, in expectation, by -p = 2 t≥1 t -p+1 ≤ 2(1 + 1/(p -2)) (bounding the sum by an integral) for p > 2. Now, the last sum in (17) equals zero for some appropriate value of u k,n . Indeed, thanks to the increasing monotonicity of d > ∆ k for any 1 ≤ u k,n ≤ s ≤ t ≤ n implies the eventd (k)n,u k,n > ∆ k . But this last event never holds for a large enough value of u k,n . Indeed, using the same argument as in the proof of Theorem 2, i.e. the fact that < ∆ k for all 1 ≤ u k,n ≤ s ≤ t ≤ n, and the third term of the sum in (17) is zero. Thus, defining u k,n 1 + log(4n p )

	t≥1	t s=1	P(X	* s + c * t,s ≤ µ * ) + P(X k,s + c	(k) t,s -d (k) t,s ≥ µ k )
	which, from (14), is upper-bounded by 2 t≥1 s=1 t (k) t •,s and the decreasing monotonicity of d (k) t,• , the event
					(k) d t,s 8σ 2 l u	+	8l u	< ∆
	whenever u/l > 8σ 2 /∆ 2 + 16/∆, we deduce that for
				u k,n log(4n p )	>	8σ 2 k ∆ 2 k	+	16 ∆ k
	we have d (k) n,u k,n < ∆ k thus d (k) t,s 8σ 2 k k ∆ 2	+ 16