Jesus Gonzalez-Feliu

Mathieu Gardrat

Pascal Pluvinet

Christian Ambrosini

Urban goods movement estimation for public decision support: goals, approaches and applications

Introduction

It is usually considered that urban goods transport proceeds from a complex system (Gonzalez-Feliu and Routhier, 2012). It includes transport system, infrastructures and urban planning, firm's logistic strategies1 . The main stakes of urban goods movement (UGM) can be considered at different topics and scales: reliability of the different logistic chains, local traffic growth, local traffic congestion, urban centres economic support, environmental nuisances (noise, pollutant emissions), urban logistic centres optimal location, greenhouse gas saving, but also urban spread effects and changes in the consumer behaviour, among others. In order to deal with public authorities planning issues, a lot of varied modelling approaches can be carried out (European Commission, 1998;[START_REF] Dufour | French Experimental and Research Programme[END_REF] and, as we can observe from several works, a standard approach is not yet developed in UGM characterization [START_REF] Browne | Comparison of urban freight data collection in European countries[END_REF], mainly due to cultural and geographic reasons that make difficult to transfer approaches from an area to another [START_REF] Ambrosini | Objectives, methods and results of surveys carried out in the field of urban freight transport: an international comparison[END_REF].

Traditionally, public authorities acted on short-term scopes when dealing with UGM [START_REF] Gonzalez-Feliu | Models and Methods for the City Logistics: The Two-echelon Capacitated Vehicle Routing Problem[END_REF]; the actions seem to be carried out to deal with emergencies or short term issues without an aim of integration into city transport plans [START_REF] Muñuzuri | Solutions applicable by local administrations for urban logistics improvement[END_REF]. Moreover, although some countries or regions propose to include urban goods on such plans (CERTU-ADEME, 1998;Spinedi, 2008), this idea still remains more conceptual than really applied, and few cities include systematically urban goods into their plans if there is not an obligation to do it [START_REF] Lagrange | Comparison of regulations in EU concerning commercial/goods transport planning measures -Europe level[END_REF]. On another side, UGM start to be on the main issues of public decision makers, and the need to take into account on systemic transport plans is starting to be accepted by several public authorities, mainly in Germany and France. However, public decision makers have difficulties to define the most suitable tools and methods to carry out the effective integration of UGM in more general transport and land use planning actions.

This chapter aims to be a guide for researchers and practitioners on choosing the most suitable approach to deal with a target or goal in terms of urban goods public decision support, and to integrate them into transport plans. Therefore, this paper is neither a literature review nor a benchmarking framework but to propose a multidisciplinary analysis of schools and points of view for public policy decision support in order to propose a guide to practitioners in terms of approaches for integrating urban goods movement in strategic and/or tactical planning actions and tools. First, an overview of urban goods stakes and goals of public planning actions is proposed, with a special focus on why urban goods is less studied and integrated in public policy actions than people transport. Then, an overview on diagnosis techniques is presented. These techniques can be survey-based or derived from data generation tools. After that, a general framework for scenario simulation and assessment is introduced. Finally, a synthesis will lead into a guide for practitioners to understand and combine these approaches to deal with their expected objectives and targets.

Urban goods stakes in public planning actions

Since mid-90's, the public intervention on urban goods regulation and planning was limited to manage the emergencies or to understand urban goods movement. After 1994, several countries, like France, Italy, The Netherlands, Germany or the United Kingdom have developed a local, regional or national legislation that includes in some cases the urban goods traffic flow planning and management as a priority [START_REF] Zunder | Urban freight logistics in the European Union[END_REF].

In this section we suggest an overview of the main legislative actions that public authorities have developed, relating it to urban goods traffic flows. This section is neither an in-depth literature review on the field nor an analysis of public policy actions, but defines the application fields of policy-oriented urban goods modelling and simulation approaches and motivates its interests.

We will start by underscoring the lack of knowledge concerning urban goods traffic in public authorities. This leads in a restrictive implementation of urban goods movements in planning policies and thus a narrowed assessment capacity during the decision process. An enlightening example is the result of a European survey on urban goods modeling tools in 1999 that stated that 72% of the 43 questioned cities did not use any urban goods modeling tools [START_REF] Routhier | Du transport de marchandises en ville à la logistique urbaine[END_REF]. Though this example is aged, it is not unlikely that it stayed almost unchanged during all these years (Patier and Routhier, 2009a).

More importantly, we can question the use which can be done of the modeling tools by public authorities. Even if a small portion of cities are willing to use this type of tools, we have no data or means to verify if they are used properly. We can only assume that it is possible that some authorities won't use it at their full potential or out of the range of their primal purpose. Thus, even if more urban decision makers should use modeling and simulations approaches, the positive effects of such an improvement wouldn't be proportional in regard to the number of users. This problem can be seen from two different angles: firstly, the use (in the practice sense) is inappropriate, or secondly, the practice is appropriate, but the tool itself is inappropriate and was unsuitably chosen. This leads us to extract two important notions of this reflection: the pertinence and the practices of goods movement estimation tools. These two points are fundamental if local authorities want to start an integration of the urban goods movements in their development policies: the methodological and sensible choice of an approach/tool is a key to achieve an efficient policy. Therefore, we can see a high potential in the construction of a methodology which can help public authorities in choosing a modeling or simulation tool, and that can guide its users through good practices.

From the two previous notions we tackled above (pertinence and practices), we could add a last one, which would concern the available resources to implement the chosen solutions. It is indeed not hard to imagine that different cities possess different resources, speaking in terms of financial and human resources (quantity and skills). More restrictive, the resources determine the limits which the local authorities can't cross. We will shortly examine this particular point in the next section.

Defining the situations in which the modeling tools can be used properly is the basis of the approach we want to build. Three types of uses can be mentioned to start with:

• Diagnosis

• Global plans development and verification

• Local plans verification which can in fact be divided in two categories: regulations and urban development

We can effectively see that urban goods traffic estimation, modeling and simulation tools have a wide range of uses during the planning process. Indeed, we can firstly mention the diagnosis possibilities that estimation tools can offer. Here we can mention two types of tools: surveys and modeling tools. Surveys are integrated in the reality and render the facts of a particular situation (though French surveys demonstrated similarities in various cities).

Another possibility is the application of modeling tools. In fact, rather than surveying, some public authorities might prefer modeling the urban goods traffic, as it only requires the tool itself and relatively few data to calibrate it. These approaches can also be applied to test and develop global action plans. In this particular case, simulation tools should be adjoined to the diagnosis process. But this kind of tools can also be used for smaller geographical applications in terms of urban design and regulation.

Concerning the urban goods in planning actions, the last years have seen the development of innovative measures [START_REF] Bestufs | BESTUFS II Bibliographic Overview: D7[END_REF], carried by the European commission and a few governments and implemented by several cities across the European Union. However, the urban goods movements are still not taken into account by a large majority of cities, but here are a few examples of the urban goods applications in public planning actions. In France, according to the French law, urban trip plans have to include urban goods for cities with more than 100000 inhabitants (CERTU-ADEME, 1998), however this orientation does not insist on a positive organization of the UGM. A methodological work has been carried out in 1998 to integrate more efficiently the UGM in the urban trip plans. Even so, the correct application this methodology is questionable and does not make any consistent references to urban goods modeling tools. In the rest of Europe urban goods is exclusively a matter of concern for cities, and governments are usually not implicated in this subject (Dablanc, 2001). In Italy, a few main cities include the urban goods in their city plan, and the main measures concern cargo consolidation, access regulation and improvement of the vehicle fleet. In Germany, most of the main cities take into account the urban goods movements but there are also national rules concerning vehicle performances (emission standard labeling). The German approach tends to integrate all the stakeholders concerned by urban goods transports in the research of a consensus for the entire urban community. All these approaches are usually carried-out on a large geographical scale (urban areas covering several cities, regions…).Unfortunately it is possible to notice that local regulations can sometimes undermine the positive effects of regional approaches: the urban area is often divided in many different territories, each having its own local authorities (the example of the Ile de France region is the most demonstrative, with more than 1000 towns with many different regulations). Moreover, regulations at a European level tend to vary sensibly: Paris bases its urban goods transports regulations on the surface of the trucks, whereas London is more concerned with the weight, and other cities (Milan, Stockholm, Amsterdam…) with weight and length of the vehicle but with completely different standards (Dablanc, 2001). In this context of heterogeneity, an innovative methodology to determine the best approach for urban goods modeling is a positive initiative that could help building a common and synergic approach of the urban goods transport.

The final goal of this reflection is to help policy makers to choose the proper tool for a given task and use this tool in an appropriate way, according to its resources. But also to raise the awareness of city authorities on a fundamental subject that is urban goods transportation.

Diagnosis

In this section, different data collection techniques are described with their advantages and limits. Furthermore we question how simulation tools can be an alternative to traditional data collection methods, with a short description of each simulation model.

The first action to carry out to include urban goods and commercial transport in policy and planning strategies is to make a diagnosis of the current situation to have a basis for the discussion and development of such strategies. To do this, many policy makers are reliant on urban goods movement surveys [START_REF] Allen | Review of survey techniques used in urban freight studies[END_REF], which provides a little insight into relevant factors like the goods and service flows, the specific purpose of commercial vehicle trips, the involved establishment and the supply chain decisions related to these trips, among others [START_REF] Pluvinet | GPS data analysis for understanding urban goods movement[END_REF]. Traditionally traffic counts are the most common survey method for urban freight policy making support, since policy makers have the habits and experience on these techniques, already popular for people transport policy making. However, the variety of methods in people transport is wider, and in the last years, many urban freight transport studies attempt to go beyond vehicle traffic counts [START_REF] Allen | Review of survey techniques used in urban freight studies[END_REF]. Moreover, several categories of urban goods and commercial transport surveys have been identified recently [START_REF] Ambrosini | Objectives, methods and results of surveys carried out in the field of urban freight transport: an international comparison[END_REF][START_REF] Allen | Review of survey techniques used in urban freight studies[END_REF]Patier and Routhier, 2009a;[START_REF] Pluvinet | GPS data analysis for understanding urban goods movement[END_REF]. According to [START_REF] Allen | Review of survey techniques used in urban freight studies[END_REF], Urban Goods Movement (UGM) data can be collected using different techniques, which are mainly the following:

• General surveys: Each category of survey has its specificities, and leads to different application advantages and limits. To compare them and propose a discussion on the suitability and synergies between these techniques, we propose to build a synthesis that shows the potential of each category of survey to collect the main information needed for urban goods and commercial transport diagnosis and public policy decision support. The main aspects that we want to focus on are the following:

o
• Quantity and quality of collected data.

• Freight related information.

• Data sampling. Whatever survey method used, it is important to ensure a good sampling.

• Difficulty to respect data sampling.

• Costs.

• Implementation limits.

Each survey cannot give all types of information on urban goods transport organization. The general surveys are the most complete (and complex) surveys of the previous data collection method: they give global data on the freight activity in the cities and sometimes even beyond the urban areas (i.e. the US commodity flow surveys). Every type of data (in the above typology) is collected during these surveys, except from the external elements (category 4). This type of surveys is however the most expensive as it gathers fair amounts of resources (human and material) to survey the entire supply-chain related to urban goods movements. The inconvenient of this type of global survey is usually the lack of accuracy on urban freight operations: for example KiD, and MiD, commodity flow survey are not focused on the urban area but are national surveys (Warmouth et al., 2004). It is also difficult to generate the interest of the stakeholders in participating in such surveys: the involvement of all the participants is a key in building substantial data. New approaches such as the French surveys on the urban goods movements are specifically built for the urban area and therefore the most suitable to understand freight flows and their formation in the urban area (Patier and Routhier, 2009b).

Stakeholders' surveys derive from the previous category as they can in fact be parts of the general surveys. They are the core in understanding the organization of transport and freight operations in the urban environment. As each stakeholder represents a part of the supplychain, surveying one or the other stakeholder will give different (in quantity and quality) valuable information. The shippers and establishments surveys provide more information on shipment and handling operations, as freight operators and service provider surveys generate more information on the activity of carriers and vehicle operations, while still giving data on shipment and handling operation (maybe with lesser quality and quantity). This sort of surveys mobilizes heavy resources if done thoroughly, but is very accurate. Again, as well as in the previous category, the involvement of the surveyed stakeholders is an additional difficulty, but is fundamental if the goal is to build substantial sets of data.

The vehicles surveys can give precious information on the fleets, the characteristics, and delivery paths of the vehicle. It mainly concerns the "behaviours" of the vehicles and fleets in the urban area. While the collected data are mainly concerning the category 3 of the typology, it is also possible to gather precious information in the first and second categories, depending if it is a driver survey (which can give us information on pick-up/delivery operations and shipment) or if it is a GPS survey that can only provide the path taken, but with an extreme accuracy on speeds, accelerations and routes [START_REF] Pluvinet | GPS data analysis for understanding urban goods movement[END_REF]. Again we observe the importance of communication with the actors of the urban freight transport, if the goal is to obtain extended information. However this category is not necessarily the most expensive of all, because it is (partly) based on the observations of diaries or GPS data, which can be obtained with minimum human resources.

The last category (land use survey), is not fundamental as it does not really give information on freight operations, but helps understanding the environment in which urban goods movements take place. Indeed, the limit of these surveys is that they are quite disconnected from the organization of transport, and only give information on the use of the public road network, and the origin and destination of flows (Patier and Routhier, 2009a). But, it is still useful to complete the previous categories, with an environmental analysis, to understand the influence of external elements on urban freight operations.

We can observe that one type of survey is not enough to understand the system that urban goods movements represent. The combination of several types of surveys is necessary to have an extensive set of data to perform a full diagnosis of the urban goods transport in a city. We can also observe that the most "efficient" methods are also the most expensive and mobilize heavy human and material resources. Indeed, each method presents several limits. We think important to combine them in order to meet the survey targets: GPS-based techniques, more precise data can be obtained about a number of parameters, as routes, speeds, energy consumption, … whereas current mail-out/mail-back and face-to-face surveys give invaluable information about the behaviour of the stakeholders and of the logistics schemes.

As shown above, survey methods are expensive and policy makers do not always have the resources to carry out them with the detail level needed to ensure a minimum quantity and quality of results. To deal with this limit, a small group of tools are today available to assist policy makers. These tools are in general depending on a regional or national context and are not present in all countries.

In the mid of the 80's, [START_REF] Sonntag | A Computer Model of Urban Commercial Traffic, in Transport, Policy and Decision Making[END_REF] developed a simulation tool for commercial traffic diagnosis, WIVER [START_REF] Sonntag | A Computer Model of Urban Commercial Traffic, in Transport, Policy and Decision Making[END_REF] based on German surveys carried out at nearly 9000 premises (Berlin, Hamburg and Munich) and specific surveys of drivers on their traffic behaviour [START_REF] Ambrosini | Urban freight modeling: a review[END_REF]. The complexity of interactions explaining the generation of traffic required considerable data collection work. The determination of traffic O/D is obtained in four stages, in each area by: the calculation of the round origins, the selection of destinations in comparison with the origins, the connection between origins and destinations, and (4) route construction. These calculations made it possible to obtain the share of the commercial traffic in the total traffic (in terms of vehicle flows) and the map of O/D commercial traffic flows between different areas, becoming a diagnosis tool for commercial traffic as well as a quantification of urban platform impacts. [START_REF] Lohse | Travel Demand Modeling with Model EVA -Simultaneous Model for Trip Generation, Trip Distribution and Mode Choice[END_REF] transferred the WIVER model to a general framework backed up by a system theory and included in the software program VISEVA, which nowadays is integrated on the PTV traffic simulation tool VISSUM.

Also in Germany, [START_REF] Janssen | Development of a urban commercial transport model for smaller areas[END_REF] included a "goods and special transports" model in IVV Aachen urban transport planning software VENUS. That approach derives clearly from personal traffic modelling frameworks [START_REF] Ortuzar | Modelling Transport[END_REF]) using a classic 4-steps model (trip generation, gravitation-based trip distribution, modal split and traffic assignment). The tool can differentiate flows by vehicle types but the differentiation of the trip reasons is based on "trip purposes" e.g. industry-trade connections, trade-end user. Available time budgets, daily courses, distribution of stop time lengths and number of stops are used for the generation of trip chains.

In France, the National Program on Urban Goods Transport financed the joint development of three wide surveys and the development of a diagnosis tool, FRETURB, to understand and simulate the impacts of urban goods traffic [START_REF] Routhier | Mesurer l'impact du transport de marchandises en ville, le modèle de simulation FRETURB (version 1)[END_REF]. This approach introduces the vehicle movement as the statistical unit for urban goods movement characterisation [START_REF] Routhier | FRETURB, un modèle de simulation des transports de marchandises en ville[END_REF]. The vehicle movement is defined as a delivery or a pickup associated to a given establishment, a vehicle size, a mode of management and logistic behaviour). The software tool presents several modules. The "inter-establishment generation model" estimates the number of movements generated by each establishment of an area, and estimates the associated impacts in terms of travelled distances, running road occupancy rates and parking road occupancy rates [START_REF] Routhier | FRETURB V3, a Policy Oriented Software of Modeling Urban Goods Movement[END_REF]. The module's mathematical framework derives from empirical and statistical analyses carried out from the French surveys carried out on Bordeaux, Dijon and Marseille (Patier and Routhier, 2009b). A second module ("flow distribution estimation") allows estimating O/D matrices that can then be used for traffic assignment. These matrices allow distinguishing five types of vehicles, mainly related to their dimensions. Other modules that will allow simulating scenarios, taking into account end-consumers flows and estimating the environmental impacts are being tested (Gonzalez-Feliu et al., 2012). This tool requires a local establishment database and general demographic information as input data but no large local surveys are required. Available as software since 2000, this module is nowadays used in more than 20 French urban communities (including most of the main French cities like Paris, Lyon or Lille, among others).

CITY GOODS is the urban freight demand model based on the framework of [START_REF] Gentile | A Demand Model for Freight Movements Based on a Tree Classification of the Economic Activities Applied to City Logistic[END_REF], developed for the Emilia-Romagna Region in Italy. According to the authors, the model deals with two main questions. The first takes place when a given activity (a fortiori a given zone) generates movements belonging to different supply chains, and the second when a vehicle performs many deliveries or pick-ups in a tour. The goal of CITY GOODS is to estimate the number of goods-related operations generated by each zone. To do this, a simultaneous data collection methodology and the modelling architecture processes have been carried out, as on the French experience (Rosini, 2005). Then, a tree-based typology of economic activities has been identified [START_REF] Gentile | A Demand Model for Freight Movements Based on a Tree Classification of the Economic Activities Applied to City Logistic[END_REF]. The mathematical framework follows a four-step model, but the used unit is not the trip [START_REF] Janssen | Development of a urban commercial transport model for smaller areas[END_REF] but a mix of movement [START_REF] Routhier | FRETURB, un modèle de simulation des transports de marchandises en ville[END_REF] and the quantity of goods. The finished software tool is internal to Emilia Romagna region, but can be applied to any Italian city.

Although only four operational tools can be found nowadays, we can find several modelling approaches in scientific literature that have not lead on a user-friendly tool (for recent surveys on these approaches, see [START_REF] Ambrosini | Urban freight modeling: a review[END_REF][START_REF] Anand | City Logistics Modelling Efforts: Trends and Gaps -A Review[END_REF][START_REF] Comi | Urban Freight Transport Demand Modelling: a State of the Art[END_REF][START_REF] Gonzalez-Feliu | Models and Methods for the City Logistics: The Two-echelon Capacitated Vehicle Routing Problem[END_REF]Routhier, 2012). Some of these approaches have been applied to real situations and have been used for public support (Eriksson, 1997;Hunt and Stefan, 2008). We aim not to propose a deep review on such models but a quick classification seems necessary to understand the variety of approaches and the difficulties to produce a unified tool for urban goods diagnosis. The classification proposed below derives from that of Gonzalez-Feliu et al. (2012) and distinguishes four main types of models:

• Four-step derived models propose to estimate the urban goods movement phenomena by analogy to personal trip or interurban transport, by sequential models inspired on the classical four-step modelling framework [START_REF] Ortuzar | Modelling Transport[END_REF]. Although many models can be included on this category, we observe several sub-categories, which are: o Trip-based models [START_REF] Eriksson | Urban freight Transprt forecasting -an empirical approach[END_REF][START_REF] Janssen | Development of a urban commercial transport model for smaller areas[END_REF] are less used on UGM than on interurban transport, due to the fact that urban trips are included on multi-destination routes [START_REF] Gentile | A Demand Model for Freight Movements Based on a Tree Classification of the Economic Activities Applied to City Logistic[END_REF] but we find one commercial tool still used by practitioners derived from these frameworks, the VENUS software. These models are direct applications of a four-step model to freight trips and need specific survey data to be calibrated and censorial information to define explicative variables. o Commodity-based models, the most popular of the present category. These models use classical trip generation techniques and propose gravity approaches [START_REF] Boerkamps | Good Trip -A new approach for modelling and evaluation of urban goods distribution[END_REF] or discrete choice frameworks [START_REF] Russo | A modelling system to simulate goods movements at an urban scale[END_REF] for trip distribution and modal choice. o Delivery-based models [START_REF] Gentile | A Demand Model for Freight Movements Based on a Tree Classification of the Economic Activities Applied to City Logistic[END_REF][START_REF] Muñuzuri | Modeling peak-hour urban freight movements with limited data availability[END_REF][START_REF] Nuzzolo | Modelli di previsione della domanda merci in area urbana[END_REF] estimate O/D matrix similarly to trip-based models, but using the delivery as the modelling unit [START_REF] Comi | Urban Freight Transport Demand Modelling: a State of the Art[END_REF]. • Multi-agent simulations models (Wisejindawaat and Sano, 2003) use concepts derived from artificial intelligence and multi-agent modelling to represent the behaviour of the involved stakeholders.

• Tour-based or chain-based models [START_REF] Sonntag | A Computer Model of Urban Commercial Traffic, in Transport, Policy and Decision Making[END_REF][START_REF] Hunt | Tour-based microsimulation of urban commercial movements[END_REF][START_REF] Holguín-Veras | Integrated Origin-Destination Synthesis Model for Freight with Commodity-Based and Empty Trip Models[END_REF] are generation-route construction models generating the entire route then decomposing it in a set of trips. First, the number of tours or trip chains generated by each zone is estimated. In the tour generation phase, the origin location and the number of destinations or each tour are defined. Second, a route-construction algorithm or an origin/destination synthesis method is used to assign each tour origin to its destination locations.

• Bottom-up statistical behavioural models [START_REF] Routhier | FRETURB, un modèle de simulation des transports de marchandises en ville[END_REF][START_REF] Routhier | FRETURB V3, a Policy Oriented Software of Modeling Urban Goods Movement[END_REF], built in parallel to data collection for a better explanation of the chosen explained variable. In these models, a typology of establishments is proposed, and the number of movements (defined as pickup and/or delivery operations) is estimated for each establishment using a generation function. They do not produce directly O/D pairs but estimate the impacts of goods trips in terms of road occupancy rated within a section, zone or the entire area of study.

Finally, we aim to highlight that subcontracting urban goods diagnosis to researchers is a practice that seems more developed in North-America and Asia than in Europe, but can be a valid alternative to carrying out high cost surveys of buying a software tool for a single use. Another alternative is that of asking to a specialised consulting agency that will either use an existing tool or make adequate surveys. In this case, the costs remain also the discriminating variable, and the quality and quantity of the services are in general related to the price the public decision makers are disposed to pay for them.

Simulation

In order to include the particularities of urban goods movement in a long-term analysis, we suggest a methodological framework for the scenario construction. The main interest for using scenarios is that it allows decision makers to be pro-active in the planning process. This framework corresponds to the first phase of backcasting and will take into account the consequent actions to undertake at the politics and policy levels following the directions suggested by these scenarios. For this, Figure 1 sums up into a chart the main decision process in urban logistics long-term planning.

Figure 1 -Chart of the proposed simulation methodology

The stakes will define the main goals of the long-term analysis. To meet the established target, several strategic choices are possible (Politics). These choices become the main expected objectives that can be implemented through the appropriate policies. The most usual policies are related to:

Policy

Measures

Interactions and synergies

Impacts

SIMULATION

• the action on the land use (location of the warehouses, platforms, hyper and supermarkets and generally all type of industry), the effects of the high density; • the optimisation of the goods management (co-operation and consolidation, bin packing, full trucks, routing etc.) including the new logistics places and with the help of the new technologies; • the regulation by the public authorities (congestion charging and road pricing, incitements towards green behaviour); • the development of the e-commerce, home deliveries and relay points deliveries;

• the development of clean vehicles with zero emission.

External elements are those that will interact with the policies and measures, of which the impact cannot be directly controlled by public authorities. The most important external elements are the economic and the social contexts, at all scales (world-range, continental, national, regional, local, urban, suburban, etc.) and their trends can be hypothesised but not always correctly estimated. In the economic context, the petrol price fluctuations, the economic crisis and the new economies impacts have changed the established trends and have to be taken into account carefully because of this prediction difficulty.

The social context and more precisely the reactions of the inhabitants and the professionals to the changes proposed by the new policies have also to be studied. In any case, these elements become important in the analysis phases and in the scenario construction, where they are taken as facts. Moreover, the changes in the people behaviour have to be also taken into account, as the people practice of the city has an influence on the interactions of the urban system.

The urban form is the configuration of the urban area as a result of the politics and policy phases, and consists of the following elements:

• energy sources and motorization technologies;

• demographic and socio-economic characteristics of the population;

• demographic and socio-economic characteristics of the economic activities;

• organisation and management of the city operations.

From the elements listed above, different scenarios should be simulated. Obviously, interactions and synergies among the main elements of the urban form are expected. The simulation tools in long term issues for urban goods movement are in general mesoscopic models that are more detailed than macroeconomic models, and can be adapted to an urban area in order to estimate the main trends in a long-term horizon without long and difficult calculation processes. The simulation results can be progressively improved through an iterative feedback procedure.

How to choose the most pertinent method/tool for given objectives and resources?

A first conclusion of the proposed overview on methods and tools for policy making support can be that there is a wide variety of approaches, as well as it is for objectives and goals of policy makers. Moreover, the culture and specificities of each city increase the difficulty of proposing a unified and standard method [START_REF] Ambrosini | Objectives, methods and results of surveys carried out in the field of urban freight transport: an international comparison[END_REF] to deal with these objectives. In this section we propose to unify not the approaches for UGM planning decision support but a meta-method to choose the most suitable ones for a given target.

To choose the best method for a given objective, a policy maker has to take into account the following elements: the initial goals, the scope of application, the available data, the potential acceptability of stakeholders for a survey or interview, the cost and the aims of transferability of the researched method. Concerning the decision maker's goals, they will influence directly the type of method used and its granularity. For example, if the goal is to support a planning strategy, the and scope of application, a macroscopic prediction tool seems the most adapted, whereas to understand the potential breaks to the development of a new infrastructure a more microscopic method accompanied with data collection and analysis will be more suitable. Moreover, the scope of application has to be adapted to the nature of the entities to be studied in two dimensions, in space and time. For example, the goal of a town planner is to study road and rail transport infrastructures, the construction of logistic platforms, traffic management in existing structures or, lastly, congestion and the measurement of greenhouse gas emissions. On another hand, the goals of private carriers and other stakeholders like real estate companies are more related to profit and cost optimization, although the environmental component starts to be main stake also in the private sector.

Whatever the approach chosen, once the objective has been set, it is first necessary to define the variable to be observed and modeled; in other words, in our field this means identifying the factors generating mobility. For example, regarding the transport of persons, the object of observation used for decades has been the transport of an individual. It could also be the departure of each individual from their home or each motive for movement. Each of these choices has a certain number of advantages although results in a series of approximations that have be taken into account. In relation with the elements presented above, another important aspect to be taken into account is the granularity of the proposed method. The granularity of a model is essential to make the complexity of the phenomena to be modeled understandable without degrading the explanatory capacity of these data. More specifically, it appears important to avoid reducing the explanatory capacity of the data by over-aggregating or desegregating them, as long as the modeling method and the samples allow this. Regarding this, and according to the model, we observe three levels of data aggregation as a function of the model's objectives. Three approaches are predominant in literature: aggregated models, desegregated models and segmented models. Aggregated models are those that use data in an aggregated form, mainly to define O/D couples. Desegregated models are those that use much desegregated data, individuating elemental generation units like the establishment. Segmented models are those that are between the two other categories, using a zonal approach and activity clusters. Finally, micro-simulation produces desegregated data that allows traffic assignment.

The granularity of the chosen method is also related to the computational capacity of the hardware available and/or the cost of implementing coherent surveys to feed the databases. For example, a multi-agent model is disaggregated, so it needs more memory allocation and sometimes more parallel computing structures than an Econometric aggregated model does. Moreover, a Land-Use and Transportation Interaction (LUTI) model can require specific GIS software and graphic tools that require high computational power. To implement these tools a huge quantity of data is needed, which means expensive and complex surveys. A more macroscopic approach, or a very specific and local intervention will then need a low quantity of data, and specific surveys or macroscopic diagnosis tools will be enough and less expensive to meet the decision makers' goals. These aspects have to be taken into account when developing a model.

Last but not least, transferability and applicability is an important subject to think about.

Local specific action will not be aimed to be transferred, but strategic and tactical actions will justify the investment on a general tool and an internal formation of the employees. For example, the French land development department has bought standard surveys and simulation tools and asks each regional office to have a figure able to use them. Then, they can produce studies and expertise support to local authorities in their planning processes.

To summarize those issues and propose a guide to practitioners on how using the presented approaches, we propose a non-exhaustive table as show below:

Conclusions

This chapter explored the possible approaches that can support public policy decisions to integrate urban goods movement into strategic and tactical planning actions. Through an overview of methods and techniques we provide a set of advice and support elements to helps public policy makers in their choices concerning urban goods movement diagnosis and simulation. As shown in this chapter, the wide variety of methods and a lack of unification related to the different cultural and local contexts made the synthesis difficult and challenging. For these reasons, the non-exhaustive synthetic table proposed above will be a first step in decision support clarification, but we believe several further improvements can be still made.

The mixing of several techniques is a promising approach. However that needs to consider new challenges: to develop interaction procedures between each model in space, period and time, to develop data collection fitting with the global problem and to make possible the exchange between the various schools and languages of the stakeholders involved in the project. Moreover, the integration of new technologies and information sciences is fundamental to reduce costs and increase accuracy in urban goods diagnosis and simulation. Finally, few approaches are connected to GIS or other graphic interfaces. We believe that developing a tool that produces graphical results, mainly geo-located; will help public authorities on integrating urban goods in transport plans and to take conscience of the stakes and potential issues of this field.

  UGM surveys (French surveys on urban goods movements) o Commodity flow survey (ECHO, US commodity flow surveys) o Commercial transport surveys (MiD and KiD, Germany) • Stakeholder specific surveys o Establishment surveys o Shippers survey o Service provider survey o Freight operator / commercial agent survey • Vehicle specific surveys o Driver survey o Vehicle observation survey o Vehicle trip diaries o GPS survey • Land use specific surveys o Roadside interview survey o Parking survey o Traffic counts, used in conjunction with the above techniques to give complementary information.

9 LONG

 9

Table 1 . Several examples of public policy objective and suggested tools to integrate UGM in decision making and planning actions

 1

	Objectives	Scale	Current tools
	Understand the relations	Establishment, zone,	Bottom-up models, Quantitative
	between demand and	urban area	surveys
	supply
	Prediction of traffic to	Streets at peak or off-peak	4-step models, ODS models, Tour
	enhance traffic flows	hours	based models
	Estimate running road	Street, zone, urban area Any model + conversion procedures
	occupancy and
	environmental effects
	Estimate road occupancy	Section, zone / temporal Bottom-up models, vehicle counting
	impacts of stopped vehicles
	Understand the relations	Zone, urban area	Discrete choice model or catchment
	between pickups-deliveries		area model combined with UGM
	and shopping trips		model, specific surveys
	Simulate urban	Zone, urban area	None (Work in Progress)
	development scenarios

In this category we include transport companies, forwarders and suppliers.

Acknowledgments

The authors thank Jean-Louis Routhier, Florence Toilier and Danièle Patier (Laboratoire d'Economie des Transports, Lyon) for their help and experience support while writing this chapter.


Odalric-Ambrym Maillard
email: odalricambrym.maillard@gmail.com

Phuong Nguyen

Ronald Ortner
email: rortner@unileoben.ac.at

Daniil Ryabko
email: daniil@ryabko.net

Optimal Regret Bounds for Selecting the State Representation in Reinforcement Learning

We consider an agent interacting with an environment in a single stream of actions, observations, and rewards, with no reset. This process is not assumed to be a Markov Decision Process (MDP). Rather, the agent has several representations (mapping histories of past interactions to a discrete state space) of the environment with unknown dynamics, only some of which result in an MDP. The goal is to minimize the average regret criterion against an agent who knows an MDP representation giving the highest optimal reward, and acts optimally in it. Recent regret bounds for this setting are of order O(T 2/3 ) with an additive term constant yet exponential in some characteristics of the optimal MDP. We propose an algorithm whose regret after T time steps is O( √ T ), with all constants reasonably small. This is optimal in T since O( √ T ) is the optimal regret in the setting of learning in a (single discrete) MDP.

Introduction

In Reinforcement Learning (RL), an agent has to learn a task through interactions with the environment. The standard RL framework models the interaction of the agent and the environment as a finite-state Markov decision process (MDP). Unfortunately, the real world is not (always) a finite-state MDP, and the learner often has to find a suitable state-representation model: a function that maps histories of actions, observations, and rewards provided by the environment into a finite space of states, in such a way that the resulting process on the state space is Markovian, reducing the problem to learning in a finite-state MDP. However, finding such a model is highly non-trivial. One can come up with several representation models, many of which may lead to non-Markovian dynamics. Testing which one has the MDP property one by one may be very costly or even impossible, as testing a statistical hypothesis requires a workable alternative assumption on the environment. This poses a challenging problem: find a generic algorithm that, given several staterepresentation models only some of which result in an MDP, gets (on average) at least as much reward as an optimal policy for any of the Markovian representations. Here we do not test the MDP property but propose to use models as long as they provide high enough rewards.

Motivation. One can think of specific scenarios where the setting of several state-representation models is applicable. First, these models can be discretisations of a continuous state space. Second, they may be discretisations of the parameter space: this scenario has been recently considered [START_REF] Ortner | Online regret bounds for undiscounted continuous reinforcement learning[END_REF] for learning in a continuous-state MDP with Lipschitz continuous rewards and transition probabilities where the Lipschitz constants are unknown; the models are discretisations of the parameter space. A simple example is when the process is a second-order Markov process with discrete observations: in this case a model that maps any history to the last two observations is a Markov model; a detailed illustration of such an example can be found, e.g., in Section 4 of [START_REF] Hutter | Feature reinforcement learning: Part I. Unstructured MDPs[END_REF]. More generally, one can try and extract some high-level discrete features from (continuous, high-dimensional) observations provided by the environment. For example, the observation is a video input capturing a game board, different maps attempt to extract the (discrete) state of the game, and we assume that at least one map is correct. Some popular classes of models are context trees [START_REF] Mccallum | Reinforcement Learning with Selective Perception and Hidden State[END_REF], which are used to capture short-term memories, or probabilistic deterministic finite automata [START_REF] Vidal | Probabilistic finitestate machines[END_REF], a very general class of models that can capture both short-term and long-term memories. Since only some of the features may exhibit Markovian dynamics and/or be relevant, we want an algorithm able to exploit whatever is Markovian and relevant for learning. For more details and further examples we refer to [START_REF] Maillard | Selecting the state-representation in reinforcement learning[END_REF].

Previous work. This work falls under the framework of providing performance guarantees on the average reward of a considered algorithm. In this setting, the optimal regret of a learning algorithm in a finite-state MDP is O( √ T ). This is the regret of UCRL2 [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] and Regal.D [START_REF] Bartlett | REGAL: A regularization based algorithm for reinforcement learning in weakly-communicating MDPs[END_REF]. Previous work on this problem in the RL literature includes [START_REF] Kearns | Near-optimal reinforcement learning in polynomial time[END_REF][START_REF] Brafman | R-max -a general polynomial time algorithm for near-optimal reinforcement learning[END_REF][START_REF] Strehl | PAC model-free reinforcement learning[END_REF]. Moreover, there is currently a big interest in finding practical state representations for the general RL problem where the environment's states and model are both unknown, e.g. U-trees [START_REF] Mccallum | Reinforcement Learning with Selective Perception and Hidden State[END_REF], MC-AIXI-CTW [START_REF] Veness | A Monte-Carlo AIXI approximation[END_REF], ΦMDP [START_REF] Hutter | Feature reinforcement learning: Part I. Unstructured MDPs[END_REF], and PSRs [START_REF] Singh | Predictive state representations: A new theory for modeling dynamical systems[END_REF]. Another approach in which possible models are known but need not be MDPs was considered in [START_REF] Ryabko | On the possibility of learning in reactive environments with arbitrary dependence[END_REF].

For the problem considered in this paper, [START_REF] Maillard | Selecting the state-representation in reinforcement learning[END_REF] recently introduced the BLB algorithm that, given a finite set Φ of state-representation models, achieves regret of order |Φ|T 2/3 (where |Φ| is the number of models) in respect to the optimal policy associated with any model that is Markovian. BLB is based on uniform exploration of all representation models and uses the performance guarantees of UCRL2 to control the amount of time spent on non-Markov models. It also makes use of some internal function in order to guess the MDP diameter [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF]) of a Markov model, which leads to an additive term in the regret bound that may be exponential in the true diameter, which means the order T 2/3 is only valid for possibly very large T .

Contribution. We propose a new algorithm called OMS (Optimistic Model Selection), that has regret of order |Φ|T , thus establishing performance that is optimal in terms of T , without suffering from an unfavorable additive term in the bound and without compromising the dependence on |Φ|. This demonstrates that taking into consideration several possibly non-Markovian representation models does not significantly degrade the performance of an algorithm, as compared to knowing in advance which model is the right one. The proposed algorithm is close in spirit to the BLB algorithm. However, instead of uniform exploration it uses the principle of "optimism" for model selection, choosing the model promising the best performance.

Outline. Section 2 introduces the setting; Section 3 presents our algorithm OMS; its performance is analysed in Section 4; proofs are in Sections 5, and Section 6 concludes.

Setting

Environment. For each time step t = 1, 2, . . ., let H t := O × (A × R × O) t-1 be the set of histories up to time t, where O is the set of observations, A is a finite set of actions and R = [0, 1] is the set of possible rewards. We consider the problem of reinforcement learning when the learner interacts sequentially with some unknown environment: first some initial observation h 1 = o 1 ∈ H 1 = O is provided to the learner, then at any time step t > 0, the learner chooses an action a t ∈ A based on the current history h t ∈ H t , then receives the immediate reward r t and the next observation o t+1 from the environment. Thus, h t+1 is the concatenation of h t with (a t , r t , o t+1 ).

State representation models. Let Φ be a set of state-representation models. A state-representation model φ ∈ Φ is a function from the set of histories H := t 1 H t to a finite set of states S φ . For a model φ, the state at step t under φ is denoted by s t,φ := φ(h t ) or simply s t when φ is clear from context. For the sake of simplicity, we assume that S φ ∩ S φ ′ = ∅ for φ = φ ′ . Further, we set S := φ∈Φ S φ .

A particular role will be played by state-representation models that induce a Markov decision process (MDP). An MDP is defined as a decision process in which at any discrete time t, given action a t , the probability of immediate reward r t and next observation o t+1 , given the past history h t , only depends on the current observation o t . That is, P (o t+1 , r t |h t a t ) = P (o t+1 , r t |o t , a t ). Observations in this process are called states of the environment. We say that a state-representation model φ is a Markov model of the environment, if the process (s t,φ , a t , r t ), t ∈ N is an MDP. This MDP is denoted as M (φ). We will always assume that such MDPs are weakly communicating, that is, for each pair of states x 1 , x 2 there exists k ∈ N and a sequence of actions α 1 , . . . , α k ∈ A such that P (s k+1,φ = x 2 |s 1,φ = x 1 , a 1 = α 1 , . . . , a k = α k ) > 0. It should be noted that there may be infinitely many state-representation models under which an environment is Markov.

Problem description. Given a finite set Φ which includes at least one Markov model, we want to construct a strategy that performs as well as the algorithm that knows any Markov model φ ∈ Φ, including its rewards and transition probabilities. For that purpose we define for any Markov model φ ∈ Φ the regret of any strategy at time T , cf. [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF][START_REF] Bartlett | REGAL: A regularization based algorithm for reinforcement learning in weakly-communicating MDPs[END_REF][START_REF] Maillard | Selecting the state-representation in reinforcement learning[END_REF], as

∆(φ, T ) := T ρ ⋆ (φ) - T t=1 r t ,
where r t are the rewards received when following the proposed strategy and ρ ⋆ (φ) is the optimal average reward in φ, i.e., ρ ⋆ (φ

) := ρ(M (φ), π ⋆ φ ) := lim T →∞ 1 T E T t=1 r t (π ⋆ φ )
where r t (π ⋆ φ ) are the rewards received when following the optimal policy π ⋆ φ for φ. Note that for weakly communicating MDPs the optimal average reward indeed does not depend on the initial state. One could replace T ρ ⋆ (φ) with the expected sum of rewards obtained in T steps (following the optimal policy) at the price of an additional O( √ T ) term.

Algorithm

High-level overview. The OMS algorithm we propose (shown in detail as Algorithm 1) proceeds in episodes k = 1, 2, . . ., each consisting of several runs j = 1, 2, . . .. In each run j of some episode k, starting at time t = t k,j , OMS chooses a policy π k,j applying the optimism in face of uncertainty principle twice. First, in line 6, OMS considers for each model φ ∈ Φ a set of admissible MDPs M t,φ (defined via confidence intervals for the estimates so far), and computes a socalled optimistic MDP M + t (φ) ∈ M t,φ and an associated optimal policy π + t (φ) on M + t (φ) such that the average reward ρ(M + t (φ), π + t (φ)) is maximized. Then (line 7) OMS chooses the model φ k,j ∈ Φ which maximizes the average reward π k,j := π + t (φ k,j ) penalized by a term intuitively accounting for the "complexity" of the model, similar to the REGAL algorithm of [START_REF] Bartlett | REGAL: A regularization based algorithm for reinforcement learning in weakly-communicating MDPs[END_REF].

The policy π k,j is then executed until either (i) run j reaches the maximal length of 2 j steps (line 19), Algorithm 1 Optimistic Model Selection (OMS) Require: Set of models Φ 0 , parameter δ ∈ [0, 1].

1: Set t := 1, k := 0, and Φ := Φ 0 .

2: while true do 3:

k := k + 1, j := 1, sameEpisode := true 4:
while sameEpisode do 5:

t k,j := t 6:

∀φ ∈ Φ, use EVI to compute optimistic MDP M + t (φ) ∈ M t,φ and (near-)optimal policy π + t (φ) with approximate optimistic average reward ρ + t k,j (φ).

7:

Choose model φ k,j ∈ Φ such that

φ k,j = argmax φ∈Φ ρ + t k,j (φ)-pen(φ; t k,j ) . (1) 8: Define ρ k,j := ρ + t k,j (φ k,j ), π k,j := π + t k,j (φ k,j
).

9:

sameRun := true.

10:

while sameRun do 11:

Choose action a t := π k,j (s t ), get reward r t , observe next state s t+1 ∈ S k,j := S φ k,j .

12:

Set testFail := true iff the sum of the collected rewards so far from time t k,j is less than

ℓ k,j ρ k,j -lob k,j (t), (2)
where ℓ k,j := tt k,j + 1.

13:

if testFail then 14:

sameRun := false, sameEpisode := false 15: end while 25: end while (ii) episode k terminates when the number of visits in some state has been doubled (line 17), or (iii) the executed policy π k,j does not give sufficiently high average reward (line 12). Note that OMS assumes each model to be Markov, as long as it performs well. Otherwise the model is eliminated (line 15).

Φ := Φ \ {φ k,j } 16: if Φ = ∅ then Φ := Φ 0 end if 17: else if v k (s t , a t ) = N t k (s t ,
Details. We continue with some details of the algorithm. In the following, S φ := |S φ | denotes the number of states under model φ, S := |S| is the total number of states, and A := |A| is the number of actions. Further, δ t := δ/36t 2 is the confidence parameter for time t.

Admissible models. First, the set of admissible MDPs M t,φ the algorithm considers at time t for each model φ ∈ Φ is defined to contain all MDPs with state space S φ and with rewards r and transition probabilities p satisfying

p(•|s, a) -p t (•|s, a) 1 2 log(2 S φ S φ At/δt) Nt(s,a) , (3)
r(s, a)r t (s, a) Extended Value Iteration. For computing a nearoptimal policy π + t (φ) and a corresponding optimistic MDP M + t (φ) ∈ M t,φ (line 6), OMS applies for each φ ∈ Φ extended value iteration (EVI) [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] with precision parameter t -1/2 . EVI computes optimistic approximate state values u + t,φ = (u + t,φ (s)) s ∈ R S φ just like ordinary value iteration [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF] with an additional optimization step for choosing the transition kernel maximizing the average reward. The (approximate) average reward ρ + t (φ) of π + t (φ) in M + t (φ) then is given by

log(2S φ At/δt) 2Nt(s,a) , (4)
ρ + t (φ) = min r + t (s, π + t (φ, s)) + s ′ p + t (s ′ |s) u + t,φ (s ′ ) -u + t,φ (s), s ∈ S φ , (5)
where r + t and p + t are the rewards and transition probabilities of M + t (φ) under π + t (φ). It can be shown [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF]

that ρ + t (φ) ρ ⋆ (φ) -2/ √ t.
Penalization term. At time t = t k,j , we define the empirical value span of the optimistic MDP M + t (φ) as sp(u + t,φ ) := max s∈S φ u + t,φ (s)-min s∈S φ u + t,φ (s), and the penalization term considered in (1) for each model φ is given by pen(φ; t) := 2 -j/2 c(φ; t) sp(u + t,φ ) + 2 -j/2 c ′ (φ; t) + 2 -j sp(u + t,φ ), where the constants are given by

c(φ; t) := 2 2S φ A log(2 S φ S φ At/δ t ) + 2 2 log( 1 δt ), c ′ (φ; t) := 2 2S φ A log(2S φ At/δ t ) .
Deviation from the optimal reward. Let ℓ k,j := tt k,j + 1, and v k,j (s, a) be the total number of times a has been played in s during run j in episode k (or until current time t if j is the current run). Similarly, we write v k (s, a) for the respective total number of visits during episode k. (Note that by the assumption S φ ∩S φ ′ = ∅ for φ = φ ′ , the state implicitly determines the respective model.) Then for the test (2) that decides whether the chosen model φ k,j gives sufficiently high reward, we define the allowed deviation from the optimal average reward in the optimistic model for any t t k,j in run j as

lob k,j (t) := 2 s∈S k,j a∈A 2v k,j (s, a) log 2S k,j At k,j δt k,j 2sp + k,j s∈S k,j a∈A 2v k,j (s, a) log 2 S k,j S k,j At k,j δt k,j + 2sp + k,j 2ℓ k,j log(1/δ t k,j ) + sp + k,j , (6)
where sp + k,j := sp(u + t k,j ,φ k,j ) and S k,j := S φ k,j . Intuitively, the first two terms correspond to the estimation error of the transition kernel and the rewards, while the last one is due to stochasticity of the sampling process.

Main result

We now provide the main result of this paper, an upper bound on the regret of our OMS strategy. The bound involves the diameter of a Markov model φ, D(φ), which is defined as the expected minimum time required to reach any state starting from any other state in the MDP M (φ) [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF].

Theorem 1 Let φ ⋆ be an optimal model, i.e. φ ⋆ ∈ argmax ρ ⋆ (φ) | φ ∈ Φ, φ is Markovian . Then the regret ∆(φ ⋆ , T ) of OMS (with parameter δ) w.r.t. φ ⋆ after any T SA steps is upper bounded by

8D ⋆ S ⋆ + 4 √ S ⋆ A log 48S ⋆ AT 3 δ log 2T SA × AS + |Φ| T + AS + |Φ| log 2T SA + ρ ⋆ + D ⋆ AS + |Φ| log 2 2T
SA with probability higher than 1δ, where ρ ⋆ := ρ ⋆ (φ ⋆ ), S ⋆ := S φ ⋆ , and

D ⋆ := D(φ ⋆ ).
In particular, if for all φ ∈ Φ, S φ B, then S B|Φ| and hence with high probability

∆(φ ⋆ , T ) = Õ D ⋆ AB 3/2 |Φ|T .
Comparison with the BLB algorithm. Compared to the results obtained by [START_REF] Maillard | Selecting the state-representation in reinforcement learning[END_REF] the regret bound in Theorem 1 has improved dependence of T 1/2 (instead of T 2/3 ) with respect to the horizon (up to logarithmic factors). Moreover, the new bound avoids a possibly large constant for guessing the diameter of the MDP representation, as unlike BLB, the current algorithm does not need to know the diameter. These improvements were possible since unlike BLB (which uses uniform exploration over all models, and applies UCRL2 as a "black box") we employ optimistic exploration of the models, and do a more indepth analysis of the "UCRL2 part" of our algorithm.

On the other hand, we lose in lesser parameters: the multiplicative term in the new bound is S ⋆ A √ S S ⋆ A |Φ|B (assuming that all representations induce a model with no more than S φ B states), whereas the corresponding factor in the bound of [START_REF] Maillard | Selecting the state-representation in reinforcement learning[END_REF] is S ⋆ A|Φ|. Thus, we currently lose a factor √ AB. Improving on the dependency on the state spaces is an interesting question: one may note that the algorithm actually only chooses models not much more complex (in terms of the diameter and the state space) than the best model. However, it is not easy to quantify this in terms of a concrete bound.

Another interesting question is how to reuse the information gained on one model for evaluation of the others. Indeed, if we are able to propagate information to all models, a log(|Φ|) dependency as opposed to the current |Φ| seems plausible. However, in the current formulation, a policy can be completely uninformative for the evaluation of other policies in other models. In general, this heavily depends on the internal structure of the models in Φ. If all models induce state spaces that have strictly no point in common, then it seems hard or impossible to improve on |Φ|.

We also note that it is possible to replace the diameter in Theorem 1 with the span of the optimal bias vector just as for the REGAL algorithm [START_REF] Bartlett | REGAL: A regularization based algorithm for reinforcement learning in weakly-communicating MDPs[END_REF] by suitably modifying the OMS algorithm. However, unlike UCRL2 and OMS for which computation of optimistic model and respective (near-)optimal policy can be performed by EVI, this modified algorithm (as REGAL) relies on finding the solution to a constraint optimization problem, efficient computation of which is still an open problem.

Regret analysis of the OMS strategy

The proof of Theorem 1 is divided into two parts. In Section 5.1, we first show that with high probability all Markovian state-representation models will collect sufficiently high reward according to the test in (2). This also means that the regret of any Markov model is not too large. This in turn is used in Section 5.2 to show that also the optimistic model employed by OMS (which is not necessarily Markov) does not lose too much with respect to an optimal policy in an arbitrary Markov model. In our proof we use analysis similar to [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] and [START_REF] Bartlett | REGAL: A regularization based algorithm for reinforcement learning in weakly-communicating MDPs[END_REF].

Markov models pass the test in (2)

Assume that φ k,j ∈ Φ is a Markov model. We are going to show that φ k,j will pass the test on the collected rewards in (2) of the algorithm at any step t w.h.p.

Initial decomposition.

First note that at time t when the test is performed, we have

s∈S k,j a∈A v k,j (s, a) = ℓ k,j = t -t k,j + 1, so that ℓ k,j ρ k,j - t τ =t k,j r τ = s∈S k,j a∈A v k,j (s, a) ρ k,j -r t k,j :t (s, a) , (7)
where r t k,j :t (s, a) is the empirical average reward collected for choosing a in s from time t k,j to the current time t in run j of episode k. Let r + k,j (s, a) be the optimistic rewards of the model M + t k,j (φ k,j ) under policy π k,j and P + k,j the respective optimistic transition matrix. Set v k,j := (v k,j (s, π k,j (s))) s ∈ R S k,j , and let u + k,j := (u + t k,j ,φ k,j (s)) s ∈ R S k,j be the state value vector given by EVI. By (5) and noting that v k,j (s, a) = 0 when a = π k,j (s) or s / ∈ S k,j , we get

ℓ k,j ρ k,j - t τ =t k,j r τ = s,a v k,j (s, a) ρ + k,j (φ k,j ) -r + k,j (s, a) + s,a v k,j (s, a) r + k,j (s, a) -r t k,j :t (s, a) v ⊤ k,j P + k,j -I u + k,j + s,a v k,j (s, a) r + k,j (s, a) -r t k,j :t (s, a) . (8)
We continue bounding each of the two terms on the right hand side of ( 8) separately.

Control of the second term. Writing r(s, a) for the mean reward for choosing a in s (this is well-defined, since we assume the model is Markov), we have

r + k,j (s, a) -r t k,j :t (s, a) = r + k,j (s, a) -r t k,j (s, a) + r t k,j (s, a) -r(s, a) + r(s, a) -r t k,j :t (s, a) .
The terms of this decomposition are controlled. That is, using that M (φ k,j ) is an admissible model according to (4) with probability 1-δ t k,j (by applying the results of measure concentration in Appendix C.1 of [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] to the quantity r t k,j (s, a)), and the mere definition of r + k,j (s, a), and since N t k (s, a) N t (s, a), we deduce that with probability higher than 1δ t k,j , s,a v k,j (s, a) r + k,j (s, a)r t k,j (s, a)

+ r t k,j (s, a) -r(s, a) 2 s,a v k,j (s, a) 2N t k (s, a) log 2S k,j At k,j δt k,j s,a 2v k,j (s, a) log 2S k,j At k,j δt k,j . ( 9
)
On the other hand, using again the results of measure concentration in Appendix C.1 of [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF], and that v k,j (s, a) N t k (s, a) t k,j , we deduce by a union bound over S k,j At k,j events that with probability higher than 1δ t k,j we get

s,a v k,j (s, a) r(s, a) -r t k,j :t (s, a) s,a v k,j (s, a) 2v k,j (s, a) log 2S k,j At k,j δt k,j s,a 2v k,j (s, a) log 2S k,j At k,j δt k,j . (10)
Control of the first term. For the first term in (8), let us first notice that, since the rows of P + k,j sum to 1, P + k,j -I u + k,j is invariant under a translation of the vector u + k,j . In particular, we can replace u + k,j with the quantity h + k,j , where

h + k,j (s) := u + k,j (s) -min u + k,j (s) | s ∈ S k,j .
Then, we make use of the decomposition

v ⊤ k,j P + k,j -I u + k,j = (11) v ⊤ k,j P + k,j -P k,j h + k,j + v ⊤ k,j P k,j -I h + k,j ,
where P k,j denotes the transition matrix corresponding to the MDP M (φ k,j ) under policy π k,j . Since both matrices are close to the empirical transition matrix P t k,j at time t k,j , we can control the first term of this expression.

First part of the first term. Indeed, since sp + k,j = h + k,j ∞ , we have for the first term in (11), using the decomposition

p + k,j (•|s) -p k,j (•|s) = p + k,j (•|s) - p t k,j (•|s) + p t k,j (•|s) -p k,j (•|s
) together with a concentration result and the definition of p + k,j , that with probability higher than 1

-δ t k,j v ⊤ k,j P + k,j -P k,j h + k,j (12)
= s,a,s ′ v k,j (s, a) p + k,j (s ′ |s) -p k,j (s ′ |s) h + k,j (s ′ ) s,a v k,j (s, a) p + k,j (•|s) -p k,j (•|s) 1 • h + k,j ∞ s,a 2 v k,j (s, a) 2 log(2 S k,j S k,j At k,j /δt k,j ) Nt k (s,a) h + k,j ∞ 2 sp + k,j s,a 2v k,j (s, a) log 2 S k,j S k,j At k,j δt k,j
.

Second part of the first term. The second term of ( 11) can be rewritten using a martingale difference sequence. That is, let e s ∈ R S k,j be the unit vector with coordinates 0 for all s ′ = s. Following [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] we set

X τ := p(•|s τ , a τ ) -e ⊤ sτ+1 h + k,j and get v ⊤ k,j P k,j -I h + k,j (13)
= t τ =t k,j p(•|s τ , a τ ) -e ⊤ sτ h + k,j = e ⊤ st+1 -e ⊤ st k,j + t τ =t k,j p(•|s τ , a τ ) -e ⊤ sτ+1 h + k,j = t τ =t k,j X τ + h + k,j (s t+1 ) -h + k,j (s t k,j ) = t τ =t k,j X τ + u + k,j (s t+1 ) -u + k,j (s t k,j ) .
Now the sequence {X τ } t k,j τ t is a martingale difference sequence with

|X τ | p(•|s τ , a τ ) -e ⊤ sτ+1 1 sp + k,j 2sp + k,j .
Thus, an application of Azuma-Hoeffding's inequality (cf. Lemma 10 and its application in Jaksch et al.

(

)) to (13) yields v ⊤ k,j P k,j -I h + k,j 2sp + k,j 2ℓ k,j log(1/δ t k,j ) + sp + k,j 2010
with probability higher than 1δ t k,j . Together with (12) this concludes the control of the first term of (8).

Putting all steps together. Combining (8), ( 9), ( 10), ( 11), ( 12), and ( 14), we deduce that at each time t of run j in episode k, any Markovian model φ k,j passes the test in (2) with probability higher than 1 -4δ t k,j . Further, it passes all the tests in run j with probability higher than 1 -4δ t k,j 2 j .

Regret analysis

Next, let us consider a model φ k,j ∈ Φ, not necessarily Markovian, that has been chosen at time t k,j . Let t+1 be the time when one of the three stopping conditions in the algorithm (lines 12, 17, and 19) is met. Thus OMS employs the model φ k,j between t k,j and t + 1, until a new model is chosen after the step t + 1. Noting that r τ ∈ [0, 1] and that the total length of the run is (t + 1)t k,j + 1 = ℓ k,j + 1 we can bound the regret ∆ k,j of run j in episode k by

∆ k,j := (ℓ k,j + 1)ρ ⋆ - t+1 τ =t k,j r τ ℓ k,j ρ ⋆ -ρ k,j + ρ ⋆ + ℓ k,j ρ k,j - t τ =t k,j r τ .
Since by assumption the test in (2) has been passed for all steps τ ∈ [t k,j , t], we have

∆ k,j ℓ k,j ρ ⋆ -ρ k,j + ρ ⋆ + lob k,j (t), (15)
and we continue bounding the terms of lob k,j (t).

Stopping criterion based on the visit counter. Since s,a v k,j (s, a) = ℓ k,j 2 j , by Cauchy-Schwarz inequality s,a v k,j (s, a) 2 j/2 S k,j A. Plugging this into the definition (6) of lob k,j , we deduce from (15) that ∆ k,j ℓ k,j ρ ⋆ρ k,j + ρ ⋆ (16) +sp + k,j + 2 j/2 sp + k,j c(φ k,j ; t k,j ) + 2 j/2 c ′ (φ k,j ; t k,j ) .

Selection procedure with penalization. Now, by definition of the algorithm, for any optimal Markov model φ ⋆ defined in the statement of Theorem 1, whenever M (φ ⋆ ) is admissible, i.e. M (φ ⋆ ) ∈ M t k,j ,φ ⋆ and was not eliminated during all runs before run j in episode k, we have ρ k,jpen(φ k,j ;

t k,j ) ρ + k,j (φ ⋆ ) - pen(φ ⋆ ; t k,j ) ρ ⋆ -pen(φ ⋆ ; t k,j ) -2t -1/2 k,j , or equiva- lently ρ ⋆ -ρ k,j pen(φ ⋆ ; t k,j ) -pen(φ k,j ; t k,j ) + 2t -1/2 k,j 2 -j/2 c(φ ⋆ ; t k,j ) sp(u + t k,j ,φ ⋆ ) +2 -j/2 c ′ (φ ⋆ ; t k,j ) + 2 -j sp(u + t k,j ,φ ⋆ ) -2 -j/2 c(φ k,j ; t k,j ) sp + k,j -2 -j/2 c ′ (φ k,j ; t k,j ) -2 -j sp + k,j + 2t -1/2 k,j . (17)
Noting that ℓ k,j 2 j and recalling that when M (φ ⋆ ) is admissible, the span of the corresponding optimistic model is less than the diameter of the true model, i.e. sp(u + t k,j ,φ ⋆ ) D ⋆ , see [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF], and we obtain from ( 16), ( 17), and a union bound that

∆ k,j ρ ⋆ + D ⋆ + 2 j/2 D ⋆ c(φ ⋆ ; t k,j ) + 2 j/2 c ′ (φ ⋆ ; t k,j ) + 2 j+1 t -1/2 k,j (18)
with probability higher than

1 - k ′ ,j ′ ;t k ′ ,j ′ <t k,j 4δ t k ′ ,j ′ 2 j ′ -2δ t k,j . (19)
The sum in ( 19) comes from the event that φ ⋆ passes all tests (and is admissible) for all runs in all episodes previous to time t k,j , and 2δ t k,j comes from the event that φ ⋆ is admissible at time t k,j . We conclude in the following by summing ∆ k,j over all runs and episodes.

Summing over runs and episodes. Let J k be the total number of runs in episode k, and let K T be the total number of episodes up to time T . Noting that c(φ ⋆ ; t k,j ) c(φ ⋆ ; T ) and c ′ (φ ⋆ ; t k,j ) c ′ (φ ⋆ ; T ) as well as using that 2t k,j 2 j (so that 2 j+1 t

-1/2 kj 2 √ 2 • 2 j/2
), summing (18) over all runs and episodes gives

∆(φ ⋆ , T ) = K T k=1 J k j=1 ∆ k,j ρ ⋆ + D ⋆ K T k=1 J k (20) + D ⋆ c(φ ⋆ ; T ) + c ′ (φ ⋆ ; T ) + 2 √ 2 K T k=1 J k j=1 2 j/2 ,
with probability higher than 1 -

K T k=1
J k j=1 4δ t k,j 2 j , where we used a union bound over all events considered in (19) for the control of all the ∆ k,j terms, avoiding redundant counts (such as the admissibility of φ ⋆ at time t k,j ). Now, using the definition of δ t k,j and the fact that 2t k,j 2 j , we get that

4δ t k,j 2 j = 2 j δ 9t 2 k,j 2 j δ 2t k,j (t k,j + 2 j ) = δ 2t k,j - δ 2(t k,j + 2 j ) t k,j +2 j -1 t=t k,j δ 2t 2 ,
where the last inequality follows by a series-integral comparison, using that t → t -2 is a decreasing function. Thus, we deduce that the bound (20) is valid with probability at least 1 -

∞ t=1 δ 2t 2
1δ for all T , and it remains to bound the double sum k j 2 j/2 .

From the number of runs... First note that by definition of the total number of episodes K T we have

T K T k=1 J k -1 j=1 2 j = K T k=1 2 J k -2 , (21)
which implies also that we have the bound

K T k=1 J k j=1 2 j = 2 K T k=1 2 J k -2 + 2K T 2T + 2K T .
Further, by Jensen's inequality we get

K T k=1 J k -1 j=1 2 j/2 K T k=1 J k K T k=1 J k j=1 2 j K T k=1 J k 2T + 2K T . (22)
Now, to bound the total number of runs K T k=1 J k , using Jensen's inequality and (21), we deduce

K T k=1 J k = K T k=1 log 2 (2 J k ) K T log 2 1 K T K T k=1 2 J k K T log 2 T K T + 2 K T log 2 2T K T , (23
) and thus it remains to deal with K T .

... to the number of episodes. First recall that an episode is terminated when either the number of visits in some state-action pair (s, a) has been doubled (line 17 of the algorithm) or when the test on the accumulated rewards has failed (line 12). We know that with probability at least 1δ the optimal Markov model is not eliminated from Φ, while non-Markov models failing the test are deleted from Φ. Therefore, with probability 1δ the number of episodes terminated with a model failing the test is upper bounded by |Φ| -1.

Next, let us consider the number of episodes which are ended since the number of visits in some stateaction pair (s, a) has been doubled. Let K(s, a) be the number of episodes which ended after the number of visits in (s, a) has been doubled, and let T (s, a) be the number of steps in these episodes. As it may happen that in an episode the number of visits is doubled in more than one state-action pair, we assume that K(s, a) and T (s, a) count only the episodes/steps where (s, a) is the first state-action pair for which this happens. It is easy to see that K(s, a) 1 + log 2 T (s, a) = log 2 2T (s, a) for T (s, a) > 0. Then the bound s∈S a∈A log 2 2T (s, a) on the total number of these episodes is maximal under the constraint s∈S a∈A T (s, a) = T when T (s, a) = T SA for all (s, a). This shows that the total number of episodes K T is upper bounded by

K T SA log 2 2T SA + |Φ| -1 (24)
with probability 1δ, provided that T SA.

Putting all steps together. Combining (20), ( 22) and ( 23) we get ∆(φ ⋆ , T )

ρ ⋆ + D ⋆ K T log 2 2T K T + D ⋆ c(φ ⋆ ; T ) + c ′ (φ ⋆ ; T ) + 2 √ 2 2K T log 2 2T K T T + K T .
Hence, by ( 24) and the definition of c, c ′ , the regret of OMS is, with probability higher than 1δ, bounded by ∆(φ ⋆ , T )

ρ ⋆ + D ⋆ SA + |Φ| log 2 2 ( 2T SA ) + 2D ⋆ 2S ⋆ A log 2 S ⋆ 24S ⋆ AT 3 δ + 2D ⋆ 2 log 24T 2 δ + 2 2S ⋆ A log 48S ⋆ AT 3 δ + 2 √ 2 × log 2 2T SA SA + |Φ| 2T + SA + |Φ| log 2 2T
SA , and we may conclude the proof with some minor simplifications.

Outlook

The first natural question about the performance guarantees obtained is whether they are optimal. We know from the corresponding lower-bounds for learning MDPs [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] that the dependence on T we get for OMS is indeed optimal. Among other parameters, perhaps the most important one is the number of models |Φ|; here we conjecture that the |Φ| dependence we obtain is optimal, but this remains to be proven. Other parameters are the size of the action and state spaces for each model; here we lose with respect to the precursor BLB algorithm (see the remark after Theorem 1), and thus have room for improvement. It may be possible to obtain a better dependence for OMS at the expense of more sophisticated analysis. Note, however, that so far there are no known algorithms for learning even a single MDP that would have known optimal dependence on all these parameters. Another important direction for future research is infinite sets Φ of models; perhaps, countably infinite sets is the natural first step, with separable -in a suitable sense -continuously-parametrized general classes of models being a foreseeable extension. A problem with the latter formulation is that one would need to formalize the notion of a model being close to a Markovian model and quantify the resulting regret.

  where p t (•|s, a) and r t (s, a) are respectively the empirical transition probabilities and mean rewards (at time t) for taking action a at state s, and N t (s, a) is the number of times action a has been chosen in state s up to time t. (If a hasn't been chosen in s so far, we set N t (s, a) to 1.) It can be shown (cf. Appendix C.1 of[START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF]) that the mean rewards r and the transition probabilities p of a Markovian state-

representation φ satisfy (3) and (4) at time t for all s ∈ S φ and a ∈ A, each with probability at least 1δ t , making Markov models admissible with high probability.

Acknowledgments

This work was supported by the French National Research Agency (ANR-08-COSI-004 project EXPLO-RA), by the European Community's Seventh Framework Programme (FP7/2007-2013) under grant agreement 270327 (CompLACS) and 216886 (PASCAL2), the Nord-Pas-de-Calais Regional Council and FEDER through CPER 2007-2013, the Austrian Science Fund (FWF): J 3259-N13, and the Australian Research Council Discovery Project DP120100950, NICTA.