Probabilistic model checking mainly concentrates on techniques for reasoning about the probabilities of certain path properties or expected values of certain random variables. For the quantitative system analysis, however, there is also another type of interesting performance measure, namely quantiles. A typical quantile query takes as input a lower probability bound p ∈ ]0,1] and a reachability property. The task is then to compute the minimal reward bound r such that with probability at least p the target set will be reached before the accumulated reward exceeds r. Quantiles are well-known from mathematical statistics, but to the best of our knowledge they have not been addressed by the model checking community so far. In this paper, we study the complexity of quantile queries for until properties in discrete-time finite-state Markov decision processes with nonnegative rewards on states. We show that qualitative quantile queries can be evaluated in polynomial time and present an exponential algorithm for the evaluation of quantitative quantile queries. For the special case of Markov chains, we show that quantitative quantile queries can be evaluated in pseudo-polynomial time.

Cette étude s’inscrit dans le domaine de l’intelligence artificielle, plus précisément au croisement des deux domaines que sont la planification autonome en environnement probabiliste et la vérification formelle probabiliste. Dans ce contexte, elle pose la question de la maîtrise de la complexité face à l’intégration de nouvelles technologies dans les systèmes critiques : comment garantir que l’ajout d’une intelligence à un système, sous la forme d’une autonomie, ne se fasse pas au détriment de la sécurité ? Pour répondre à cette problématique, cette étude a pour enjeu de développer un processus outillé, permettant de concevoir des systèmes auto-adaptatifs critiques, ce qui met en œuvre à la fois des méthodes de modélisation formelle des connaissances d’ingénierie, ainsi que des algorithmes de planification sûre et optimale des décisions du système. / This study takes place in the broad field of Artificial Intelligence, specifically at the intersection of two domains : Automated Planning and Formal Verification in probabilistic environment. In this context, it raises the question of the integration of new technologies in critical systems, and the complexity it entails : How to ensure that adding intelligence to a system, in the form of autonomy, is not done at the expense of safety ? To address this issue, this study aims to develop a tool-supported process for designing critical, self-adaptive systems. Throughout this document, innovations are therefore proposed in methods of formal modeling and in algorithms for safe and optimal planning.

Cette thèse aborde différents aspects de la modélisation de la microstructure du marché et des problèmes de Market Making, avec un accent particulier du point de vue du praticien. Le carnet d’ordres, au cœur du marché financier, est un système de files d’attente complexe à haute dimension. Nous souhaitons améliorer la connaissance du LOB pour la communauté de la recherche, proposer de nouvelles idées de modélisation et développer des applications pour les Market Makers. Nous remercions en particuler l’équipe Automated Market Making d’avoir fourni la base de données haute-fréquence de très bonne qualité et une grille de calculs puissante, sans laquelle ces recherches n’auraient pas été possible. Le Chapitre 1 présente la motivation de cette recherche et reprend les principaux résultats des différents travaux. Le Chapitre 2 se concentre entièrement sur le LOB et vise à proposer un nouveau modèle qui reproduit mieux certains faits stylisés. A travers cette recherche, non seulement nous confirmons l’influence des flux d’ordres historiques sur l’arrivée de nouveaux, mais un nouveau modèle est également fourni qui réplique beaucoup mieux la dynamique du LOB, notamment la volatilité réalisée en haute et basse fréquence. Dans le Chapitre 3, l’objectif est d’étudier les stratégies de Market Making dans un contexte plus réaliste. Cette recherche contribueà deux aspects : d’une part le nouveau modèle proposé est plus réaliste mais reste simple à appliquer pour la conception de stratégies, d’autre part la stratégie pratique de Market Making est beaucoup améliorée par rapport à une stratégie naive et est prometteuse pour l’application pratique. La prédiction à haute fréquence avec la méthode d’apprentissage profond est étudiée dans le Chapitre 4. De nombreux résultats de la prédiction en 1- étape et en plusieurs étapes ont retrouvé la non-linéarité, stationarité et universalité de la relation entre les indicateurs microstructure et le changement du prix, ainsi que la limitation de cette approche en pratique. / This thesis addresses different aspects around the market microstructure modelling and market making problems, with a special accent from the practitioner’s viewpoint. The limit order book (LOB), at the heart of financial market, is a complex continuous high-dimensional queueing system. We wish to improve the knowledge of LOB for the research community, propose new modelling ideas and develop concrete applications to the interest of Market Makers. We would like to specifically thank the Automated Market Making team for providing a large high frequency database of very high quality as well as a powerful computational grid, without whom these researches would not have been possible. The first chapter introduces the incentive of this research and resumes the main results of the different works. Chapter 2 fully focuses on the LOB and aims to propose a new model that better reproduces some stylized facts. Through this research, not only do we confirm the influence of historical order flows to the arrival of new ones, but a new model is also provided that captures much better the LOB dynamic, notably the realized volatility in high and low frequency. In chapter 3, the objective is to study Market Making strategies in a more realistic context. This research contributes in two aspects : from one hand the newly proposed model is more realistic but still simple enough to be applied for strategy design, on the other hand the practical Market Making strategy is of large improvement compared to the naive one and is promising for practical use. High-frequency prediction with deep learning method is studied in chapter 4. Many results of the 1-step and multi-step prediction have found the non-linearity, stationarity and universality of the relationship between microstructural indicators and price change, as well as the limitation of this approach in practice.

Energy management systems (EMSs), implemented in the electronic control unit (ECU) of an actual vehicle with electri ed powertrain, is a much simpler version of the theoretically developed EMS. Such simpli cation is done to accommodate the EMS within the given memory constraint and computational capacity of the ECU. The simpli cation should ensure reasonable performance compared to theoretical EMS under real-life driving scenarios. The process of simpli cation must be effective to create a versatile and utilitarian EMS. The reinforcement learning-based controllers feature pro table characteristics in optimizing the performance of controllable physical systems as they do not mandatorily require a mathematical model of system dynamics (i.e. they are model-free). Quite naturally, it can aspired to testify such prowess of reinforcement learning-based controllers in achieving near-global optimal performance for energy management system (supervisory) of electri ed powertrains. Before deployment of any supervisory controller as a mainstream controller, they should be essentially scrutinized through various levels of virtual simulation platforms with an ascending order of physical system emulating-capability. The controller evolves from a mathematical concept to an utilitarian embedded system through a series of these levels where it undergoes gradual transformation to finally become apposite for a real physical system. Implementation of the control strategy in a Simulink-based forward simulation model could be the first stage of the aforementioned evolution process. This brief will delineate all the steps required for implementing an reinforcement learning-based supervisory controller in a forward simulation model of a hybrid electric vehicle. A novel framework of loss-minimization based instantaneous optimal strategy is introduced for the energy management system of a multi-mode hybrid electric powertrain in this brief. The loss-minimization strategy is flexible enough to be implemented in any architecture of electrified powertrains. It is mathematically proven that the overall system loss minimization is equivalent to the minimization of fuel consumption. An online simulation framework is developed in this article to evaluate the performance of a multi-mode electrified powertrain equipped with more than one power source. An electrically variable transmission with two planetary gear-set has been chosen as the centerpiece of the powertrain considering the versatility and future prospects of such transmissions. It is noteworthy to mention that a novel architecture topology selected for this dissertation is engendered through a series of rigorous screening process whose workflow is presented here with brevity. One of the legitimate concern of multi-mode transmission is it's proclivity to contribute discontinuity of power-flow in the downstream of the powertrain. Mode-shift events can be predominantly held responsible for engendering such discontinuity. Advent of dynamic coordinated control as a technique for ameliorating such discontinuity has been substantiated by many scholars in literature. Hence, a system-level coordinated control is employed within the energy management system which governs the mode schedule of the multi-mode powertrain in real-time simulation. / Thesis / Doctor of Philosophy (PhD)

No description available.

No description available.

La raréfaction des sources de production conventionnelles et leurs émissions nocives ont favorisé l’essor notable de la production renouvelable, plus durable et mieux répartie géographiquement. Toutefois, son intégration au système électrique est problématique. En effet, la production renouvelable est peu prédictible et issue de sources majoritairement incontrôlables, ce qui compromet la stabilité du réseau, la viabilité économique des producteurs et rend nécessaire la définition de solutions adaptées pour leur participation au marché de l’électricité. Dans ce contexte, le projet scientifique Winpower propose de relier par un réseau à courant continu les ressources de plusieurs acteurs possédant respectivement des fermes éoliennes offshore (acteurs EnR) et des centrales de stockage de masse (acteurs CSM). Cette configuration impose aux acteurs d’assurer conjointement la gestion du réseau électrique.Nous supposons que les acteurs participent au marché comme une entité unique : cette hypothèse permet aux acteurs EnR de tirer profit de la flexibilité des ressources contrôlables pour minimiser le risque de pénalités sur le marché de l’électricité, aux acteurs CSM de valoriser leurs ressources auprès des acteurs EnR et/ou auprès du marché et à la coalition de faciliter la gestion des déséquilibres sur le réseau électrique, en agrégeant les ressources disponibles. Dans ce cadre, notre travail s’attaque à la problématique de la participation au marché EPEX SPOT Day-Ahead de la coalition comme une centrale électrique virtuelle ou CVPP (Cooperative Virtual Power Plant). Nous proposons une architecture de pilotage multi-acteurs basée sur les systèmes multi-agents (SMA) : elle permet d’allier les objectifs et contraintes locaux des acteurs et les objectifs globaux de la coalition.Nous formalisons alors l’agrégation et la planification de l’utilisation des ressources comme un processus décisionnel de Markov (MDP), un modèle formel adapté à la décision séquentielle en environnement incertain, pour déterminer la séquence d’actions sur les ressources contrôlables qui maximise l’espérance des revenus effectifs de la coalition. Toutefois, au moment de la planification des ressources de la coalition, l’état de la production renouvelable n’est pas connue et le MDP n’est pas résoluble en l’état : on parle de MDP partiellement observable (POMDP). Nous décomposons le POMDP en un MDP classique et un état d’information (la distribution de probabilités des erreurs de prévision de la production renouvelable) ; en extrayant cet état d’information de l’expression du POMDP, nous obtenons un MDP à état d’information (IS-MDP), pour la résolution duquel nous proposons une adaptation d’un algorithme de résolution classique des MDP, le Backwards Induction.Nous décrivons alors un cadre de simulation commun pour comparer dans les mêmes conditions nos propositions et quelques autres stratégies de participation au marché dont l’état de l’art dans la gestion des ressources renouvelables et contrôlables. Les résultats obtenus confortent l’hypothèse de la minimisation du risque associé à la production renouvelable, grâce à l’agrégation des ressources et confirment l’intérêt de la coopération des acteurs EnR et CSM dans leur participation au marché de l’électricité. Enfin, l’architecture proposée offre la possibilité de distribuer le processus de décision optimale entre les différents acteurs de la coalition : nous proposons quelques pistes de solution dans cette direction. / Renewable Energy Sources (RES) has grown remarkably in last few decades. Compared to conventional energy sources, renewable generation is more available, sustainable and environment-friendly - for example, there is no greenhouse gases emission during the energy generation. However, while electrical network stability requires production and consumption equality and the electricity market constrains producers to contract future production a priori and respect their furniture commitments or pay substantial penalties, RES are mainly uncontrollable and their behavior is difficult to forecast accurately. De facto, they jeopardize the stability of the physical network and renewable producers competitiveness in the market. The Winpower project aims to design realistic, robust and stable control strategies for offshore networks connecting to the main electricity system renewable sources and controllable storage devices owned by different autonomous actors. Each actor must embed its own local physical device control strategy but a global network management mechanism, jointly decided between connected actors, should be designed as well.We assume a market participation of the actors as an unique entity (the coalition of actors connected by the Winpower network) allowing the coalition to facilitate the network management through resources aggregation, renewable producers to take advantage of controllable sources flexibility to handle market penalties risks, as well as storage devices owners to leverage their resources on the market and/or with the management of renewable imbalances. This work tackles the market participation of the coalition as a Cooperative Virtual Power Plant. For this purpose, we describe a multi-agent architecture trough the definition of intelligent agents managing and operating actors resources and the description of these agents interactions; it allows the alliance of local constraints and objectives and the global network management objective.We formalize the aggregation and planning of resources utilization as a Markov Decision Process (MDP), a formal model suited for sequential decision making in uncertain environments. Its aim is to define the sequence of actions which maximize expected actual incomes of the market participation, while decisions over controllable resources have uncertain outcomes. However, market participation decision is prior to the actual operation when renewable generation still is uncertain. Thus, the Markov Decision Process is intractable as its state in each decision time-slot is not fully observable. To solve such a Partially Observable MDP (POMDP), we decompose it into a classical MDP and an information state (a probability distribution over renewable generation errors). The Information State MDP (IS-MDP) obtained is solved with an adaptation of the Backwards Induction, a classical MDP resolution algorithm.Then, we describe a common simulation framework to compare our proposed methodology to some other strategies, including the state of the art in renewable generation market participation. Simulations results validate the resources aggregation strategy and confirm that cooperation is beneficial to renewable producers and storage devices owners when they participate in electricity market. The proposed architecture is designed to allow the distribution of the decision making between the coalition’s actors, through the implementation of a suitable coordination mechanism. We propose some distribution methodologies, to this end.

Problems involving optimal sequential making in uncertain dynamic systems arise in domains such as engineering, science and economics. Such problems can often be cast in the framework of Markov Decision Process (MDP). Solving an MDP requires computing the optimal value function and the optimal policy. The idea of dynamic programming (DP) and the Bellman equation (BE) are at the heart of solution methods. The three important exact DP methods are value iteration, policy iteration and linear programming. The exact DP methods compute the optimal value function and the optimal policy. However, the exact DP methods are inadequate in practice because the state space is often large and in practice, one might have to resort to approximate methods that compute sub-optimal policies. Further, in certain cases, the system observations are known only in the form of noisy samples and we need to design algorithms that learn from these samples. In this thesis we study interesting theoretical questions pertaining to approximate and learning algorithms, and also present an interesting application of MDPs in the domain of crowd sourcing. Approximate Dynamic Programming (ADP) methods handle the issue of large state space by computing an approximate value function and/or a sub-optimal policy. In this thesis, we are concerned with conditions that result in provably good policies. Motivated by the limitations of the PBE in the conventional linear algebra, we study the PBE in the (min, +) linear algebra. It is a well known fact that deterministic optimal control problems with cost/reward criterion are (min, +)/(max, +) linear and ADP methods have been developed for such systems in literature. However, it is straightforward to show that infinite horizon discounted reward/cost MDPs are neither (min, +) nor (max, +) linear. We develop novel ADP schemes namely the Approximate Q Iteration (AQI) and Variational Approximate Q Iteration (VAQI), where the approximate solution is a (min, +) linear combination of a set of basis functions whose span constitutes a subsemimodule. We show that the new ADP methods are convergent and we present a bound on the performance of the sub-optimal policy. The Approximate Linear Program (ALP) makes use of linear function approximation (LFA) and offers theoretical performance guarantees. Nevertheless, the ALP is difficult to solve due to the presence of a large number of constraints and in practice, a reduced linear program (RLP) is solved instead. The RLP has a tractable number of constraints sampled from the original constraints of the ALP. Though the RLP is known to perform well in experiments, theoretical guarantees are available only for a specific RLP obtained under idealized assumptions. In this thesis, we generalize the RLP to define a generalized reduced linear program (GRLP) which has a tractable number of constraints that are obtained as positive linear combinations of the original constraints of the ALP. The main contribution here is the novel theoretical framework developed to obtain error bounds for any given GRLP. Reinforcement Learning (RL) algorithms can be viewed as sample trajectory based solution methods for solving MDPs. Typically, RL algorithms that make use of stochastic approximation (SA) are iterative schemes taking small steps towards the desired value at each iteration. Actor-Critic algorithms form an important sub-class of RL algorithms, wherein, the critic is responsible for policy evaluation and the actor is responsible for policy improvement. The actor and critic iterations have deferent step-size schedules, in particular, the step-sizes used by the actor updates have to be generally much smaller than those used by the critic updates. Such SA schemes that use deferent step-size schedules for deferent sets of iterates are known as multitimescale stochastic approximation schemes. One of the most important conditions required to ensure the convergence of the iterates of a multi-timescale SA scheme is that the iterates need to be stable, i.e., they should be uniformly bounded almost surely. However, the conditions that imply the stability of the iterates in a multi-timescale SA scheme have not been well established. In this thesis, we provide veritable conditions that imply stability of two timescale stochastic approximation schemes. As an example, we also demonstrate that the stability of a widely used actor-critic RL algorithm follows from our analysis. Crowd sourcing (crowd) is a new mode of organizing work in multiple groups of smaller chunks of tasks and outsourcing them to a distributed and large group of people in the form of an open call. Recently, crowd sourcing has become a major pool for human intelligence tasks (HITs) such as image labeling, form digitization, natural language processing, machine translation evaluation and user surveys. Large organizations/requesters are increasingly interested in crowd sourcing the HITs generated out of their internal requirements. Task starvation leads to huge variation in the completion times of the tasks posted on to the crowd. This is an issue for frequent requesters desiring predictability in the completion times of tasks specified in terms of percentage of tasks completed within a stipulated amount of time. An important task attribute that affects the completion time of a task is its price. However, a pricing policy that does not take the dynamics of the crowd into account might fail to achieve the desired predictability in completion times. Here, we make use of the MDP framework to compute a pricing policy that achieves predictable completion times in simulations as well as real world experiments.

Cette thèse porte sur la résolution de problèmes de décision séquentielle sous incertitude,modélisés sous forme de processus décisionnels de Markov (PDM) dont l’espace d’étatet d’action sont tous les deux de grande dimension. La résolution de ces problèmes avecun bon compromis entre qualité de l’approximation et passage à l’échelle est encore unchallenge. Les algorithmes de résolution dédiés à ce type de problèmes sont rares quandla dimension des deux espaces excède 30, et imposent certaines limites sur la nature desproblèmes représentables.Nous avons proposé un nouveau cadre, appelé PDMF3, ainsi que des algorithmesde résolution approchée associés. Un PDMF3 est un processus décisionnel de Markov àespace d’état et d’action factorisés (PDMF-AF) dont non seulement l’espace d’état etd’action sont factorisés mais aussi dont les politiques solutions sont contraintes à unecertaine forme factorisée, et peuvent être stochastiques. Les algorithmes que nous avonsproposés appartiennent à la famille des algorithmes de type itération de la politique etexploitent des techniques d’optimisation continue et des méthodes d’inférence dans lesmodèles graphiques. Ces algorithmes de type itération de la politique ont été validés sur un grand nombre d’expériences numériques. Pour de petits PDMF3, pour lesquels la politique globale optimale est disponible, ils fournissent des politiques solutions proches de la politique globale optimale. Pour des problèmes plus grands de la sous-classe des processus décisionnels de Markov sur graphe (PDMG), ils sont compétitifs avec des algorithmes de résolution de l’état de l’art en termes de qualité. Nous montrons aussi que nos algorithmes permettent de traiter des PDMF3 de très grande taille en dehors de la sous-classe des PDMG, sur des problèmes jouets inspirés de problèmes réels en agronomie ou écologie. L’espace d’état et d’action sont alors tous les deux de dimension 100, et de taille 2100. Dans ce cas, nous comparons la qualité des politiques retournées à celle de politiques expertes. Dans la seconde partie de la thèse, nous avons appliqué le cadre et les algorithmesproposés pour déterminer des stratégies de gestion des services écosystémiques dans unpaysage agricole. Les adventices, plantes sauvages des milieux agricoles, présentent desfonctions antagonistes, étant à la fois en compétition pour les ressources avec la cultureet à la base de réseaux trophiques dans les agroécosystèmes. Nous cherchons à explorerquelles organisations du paysage (ici composé de colza, blé et prairie) dans l’espace etdans le temps permettent de fournir en même temps des services de production (rendementen céréales, fourrage et miel), des services de régulation (régulation des populationsd’espèces adventices et de pollinisateurs sauvages) et des services culturels (conservationd’espèces adventices et de pollinisateurs sauvages). Pour cela, nous avons développé unmodèle de la dynamique des adventices et des pollinisateurs et de la fonction de récompense pour différents objectifs (production, maintien de la biodiversité ou compromisentre les services). L’espace d’état de ce PDMF3 est de taille 32100, et l’espace d’actionde taille 3100, ce qui en fait un problème de taille conséquente. La résolution de ce PDMF3 a conduit à identifier différentes organisations du paysage permettant d’atteindre différents bouquets de services écosystémiques, qui diffèrent dans la magnitude de chacune des trois classes de services écosystémiques. / This PhD thesis focuses on the resolution of problems of sequential decision makingunder uncertainty, modelled as Markov decision processes (MDP) whose state and actionspaces are both of high dimension. Resolution of these problems with a good compromisebetween quality of approximation and scaling is still a challenge. Algorithms for solvingthis type of problems are rare when the dimension of both spaces exceed 30, and imposecertain limits on the nature of the problems that can be represented.We proposed a new framework, called F3MDP, as well as associated approximateresolution algorithms. A F3MDP is a Markov decision process with factored state andaction spaces (FA-FMDP) whose solution policies are constrained to be in a certainfactored form, and can be stochastic. The algorithms we proposed belong to the familyof approximate policy iteration algorithms and make use of continuous optimisationtechniques, and inference methods for graphical models.These policy iteration algorithms have been validated on a large number of numericalexperiments. For small F3MDPs, for which the optimal global policy is available, theyprovide policy solutions that are close to the optimal global policy. For larger problemsfrom the graph-based Markov decision processes (GMDP) subclass, they are competitivewith state-of-the-art algorithms in terms of quality. We also show that our algorithmsallow to deal with F3MDPs of very large size outside the GMDP subclass, on toy problemsinspired by real problems in agronomy or ecology. The state and action spaces arethen both of dimension 100, and of size 2100. In this case, we compare the quality of thereturned policies with the one of expert policies. In the second part of the thesis, we applied the framework and the proposed algorithms to determine ecosystem services management strategies in an agricultural landscape.Weed species, ie wild plants of agricultural environments, have antagonistic functions,being at the same time in competition with the crop for resources and keystonespecies in trophic networks of agroecosystems. We seek to explore which organizationsof the landscape (here composed of oilseed rape, wheat and pasture) in space and timeallow to provide at the same time production services (production of cereals, fodder andhoney), regulation services (regulation of weed populations and wild pollinators) andcultural services (conservation of weed species and wild pollinators). We developed amodel for weeds and pollinators dynamics and for reward functions modelling differentobjectives (production, conservation of biodiversity or trade-off between services). Thestate space of this F3MDP is of size 32100, and the action space of size 3100, which meansthis F3MDP has substantial size. By solving this F3MDP, we identified various landscapeorganizations that allow to provide different sets of ecosystem services which differ inthe magnitude of each of the three classes of ecosystem services.

In many optimization problems, the relationship between the objective and parameters is not known. The objective function itself may be stochastic such as a long-run average over some random cost samples. In such cases finding the gradient of the objective is not possible. It is in this setting that stochastic approximation algorithms are used. These algorithms use some estimates of the gradient and are stochastic in nature. Amongst gradient estimation techniques, Simultaneous Perturbation Stochastic Approximation (SPSA) and Smoothed Functional(SF) scheme are widely used. In this thesis we have proposed a novel multi-time scale quasi-Newton based smoothed functional (QN-SF) algorithm for unconstrained as well as constrained optimization. The algorithm uses the smoothed functional scheme for estimating the gradient and the quasi-Newton method to solve the optimization problem. The algorithm is shown to converge with probability one. We have also provided here experimental results on the problem of optimal routing in a multi-stage network of queues. Policies like Join the Shortest Queue or Least Work Left assume knowledge of the queue length values that can change rapidly or hard to estimate. If the only information available is the expected end-to-end delay as with our case, such policies cannot be used. The QN-SF based probabilistic routing algorithm uses only the total end-to-end delay for tuning the probabilities. We observe from the experiments that the QN-SF algorithm has better performance than the gradient and Jacobi versions of Newton based smoothed functional algorithms. Next we consider constrained routing in a similar queueing network. We extend the QN-SF algorithm to this case. We study the convergence behavior of the algorithm and observe that the constraints are satisfied at the point of convergence. We provide experimental results for the constrained routing setup as well. Next we study reinforcement learning algorithms which are useful for solving Markov Decision Process(MDP) when the precise information on transition probabilities is not known. When the state, and action sets are very large, it is not possible to store all the state-action tuples. In such cases, function approximators like neural networks have been used. The popular Q-learning algorithm is known to diverge when used with linear function approximation due to the ’off-policy’ problem. Hence developing stable learning algorithms when used with function approximation is an important problem. We present in this thesis a variant of Q-learning with linear function approximation that is based on two-timescale stochastic approximation. The Q-value parameters for a given policy in our algorithm are updated on the slower timescale while the policy parameters themselves are updated on the faster scale. We perform a gradient search in the space of policy parameters. Since the objective function and hence the gradient are not analytically known, we employ the efficient one-simulation simultaneous perturbation stochastic approximation(SPSA) gradient estimates that employ Hadamard matrix based deterministic perturbations. Our algorithm has the advantage that, unlike Q-learning, it does not suffer from high oscillations due to the off-policy problem when using function approximators. Whereas it is difficult to prove convergence of regular Q-learning with linear function approximation because of the off-policy problem, we prove that our algorithm which is on-policy is convergent. Numerical results on a multi-stage stochastic shortest path problem show that our algorithm exhibits significantly better performance and is more robust as compared to Q-learning. Future work would be to compare it with other policy-based reinforcement learning algorithms. Finally, we develop an online actor-critic reinforcement learning algorithm with function approximation for a problem of control under inequality constraints. We consider the long-run average cost Markov decision process(MDP) framework in which both the objective and the constraint functions are suitable policy-dependent long-run averages of certain sample path functions. The Lagrange multiplier method is used to handle the inequality constraints. We prove the asymptotic almost sure convergence of our algorithm to a locally optimal solution. We also provide the results of numerical experiments on a problem of routing in a multistage queueing network with constraints on long-run average queue lengths. We observe that our algorithm exhibits good performance on this setting and converges to a feasible point.