JournalTOCs

Foundations and Trends® in Optimization
Number of Followers: 2

Full-text available via subscription

Subscription journal
ISSN (Print) 2167-3888 - ISSN (Online) 2167-3918
Published by Now Publishers Inc

[28 journals]

Constrained Reinforcement Learning with Average Reward Objective:
Model-Based and Model-Free Algorithms
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: Abstract Reinforcement Learning (RL) serves as a versatile frameworkfor sequential decision-making, finding applications acrossdiverse domains such as robotics, autonomous driving, recommendationsystems, supply chain optimization, biology,mechanics, and finance. The primary objective of these applicationsis to maximize the average reward. Real-worldscenarios often necessitate adherence to specific constraintsduring the learning process. This monograph focuses on the exploration of various modelbasedand model-free approaches for Constrained RL withinthe context of average reward Markov Decision Processes(MDPs). The investigation commences with an examinationof model-based strategies, delving into two foundationalmethods – optimism in the face of uncertainty and posteriorsampling. Subsequently, the discussion transitionsto parametrized model-free approaches, where the primaldual policy gradient-based algorithm is explored as a solutionfor constrained MDPs. The monograph provides regretguarantees and analyzes constraint violation for each of thediscussed setups. For the above exploration, we assume the underlying MDP tobe ergodic. Further, this monograph extends its discussionto encompass results tailored for weakly communicatingMDPs, thereby broadening the scope of its findings andtheir relevance to a wider range of practical scenarios. Suggested CitationVaneet Aggarwal, Washim Uddin Mondal and Qinbo Bai (2024), "Constrained Reinforcement Learning with Average Reward Objective: Model-Based and Model-Free Algorithms", Foundations and Trends® in Optimization: Vol. 6: No. 4, pp 193-298. http://dx.doi.org/10.1561/2400000038
  PubDate: Wed, 21 Aug 2024 00:00:00 +020
Stochastic Optimization Methods for Policy Evaluation in Reinforcement
Learning
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: Abstract This monograph introduces various value-based approachesfor solving the policy evaluation problem in the online reinforcementlearning (RL) scenario, which aims to learnthe value function associated with a specific policy undera single Markov decision process (MDP). Approaches varydepending on whether they are implemented in an on-policyor off-policy manner: In on-policy settings, where the evaluationof the policy is conducted using data generated fromthe same policy that is being assessed, classical techniquessuch as TD(0), TD(λ), and their extensions with functionapproximation or variance reduction are employed in this setting.For off-policy evaluation, where samples are collectedunder a different behavior policy, this monograph introducesgradient-based two-timescale algorithms like GTD2,TDC, and variance-reduced TDC. These algorithms are designedto minimize the mean-squared projected Bellmanerror (MSPBE) as the objective function. This monographalso discusses their finite-sample convergence upper boundsand sample complexity. Suggested CitationYi Zhou and Shaocong Ma (2024), "Stochastic Optimization Methods for Policy Evaluation in Reinforcement Learning", Foundations and Trends® in Optimization: Vol. 6: No. 3, pp 145-192. http://dx.doi.org/10.1561/2400000045
  PubDate: Thu, 15 Aug 2024 00:00:00 +020
Numerical Methods for Convex Multistage Stochastic Optimization
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: Abstract Optimization problems involving sequential decisions in a stochastic environment were studied in Stochastic Programming (SP), Stochastic Optimal Control (SOC) and Markov Decision Processes (MDP). In this monograph, we mainly concentrate on SP and SOC modeling approaches. In these frameworks, there are natural situations when the considered problems are convex. The classical approach to sequential optimization is based on dynamic programming. It has the problem of the so-called “curse of dimensionality”, in that its computational complexity increases exponentially with respect to the dimension of state variables. Recent progress in solving convex multistage stochastic problems is based on cutting plane approximations of the cost-to-go (value) functions of dynamic programming equations. Cutting plane type algorithms in dynamical settings is one of the main topics of this monograph. We also discuss stochastic approximation type methods applied to multistage stochastic optimization problems. From the computational complexity point of view, these two types of methods seem to be complementary to each other. Cutting plane type methods can handle multistage problems with a large number of stages but a relatively smaller number of state (decision) variables. On the other hand, stochastic approximation type methods can only deal with a small number of stages but a large number of decision variables. Suggested CitationGuanghui Lan and Alexander Shapiro (2024), "Numerical Methods for Convex Multistage Stochastic Optimization", Foundations and Trends® in Optimization: Vol. 6: No. 2, pp 63-144. http://dx.doi.org/10.1561/2400000044
  PubDate: Wed, 22 May 2024 00:00:00 +020
A Tutorial on Hadamard Semidifferentials
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: AbstractThe Hadamard semidifferential is more general than the Fréchet differential now dominant in undergraduate mathematics education. By slightly changing the definition of the forward directional derivative, the Hadamard semidifferential rescues the chain rule, enforces continuity, and permits differentiation across maxima and minima. It also plays well with convex analysis and naturally extends differentiation to smooth embedded submanifolds, topological vector spaces, and metric spaces of shapes and geometries. The current elementary exposition focuses on the more familiar territory of analysis in Euclidean spaces and applies the semidifferential to some representative problems in optimization and statistics. These include algorithms for proximal gradient descent, steepest descent in matrix completion, and variance components models.Suggested CitationKenneth Lange (2024), "A Tutorial on Hadamard Semidifferentials", Foundations and Trends® in Optimization: Vol. 6: No. 1, pp 1-62. http://dx.doi.org/10.1561/2400000041
  PubDate: Mon, 13 May 2024 00:00:00 +020
Massively Parallel Computation: Algorithms and Applications
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: AbstractThe algorithms community has been modeling the underlyingkey features and constraints of massively parallel frameworksand using these models to discover new algorithmictechniques tailored to them. This monograph focuses on theMassively Parallel Model of Computation (MPC) framework,also known as the MapReduce model in the literature. Itdescribes algorithmic tools that have been developed to leveragethe unique features of the MPC framework. These toolswere chosen for their broad applicability, as they can serve asbuilding blocks to design new algorithms. The monograph isnot exhaustive and includes topics such as partitioning andcoresets, sample and prune, dynamic programming, roundcompression, and lower bounds.Suggested CitationSungjin Im, Ravi Kumar, Silvio Lattanzi, Benjamin Moseley and Sergei Vassilvitskii (2023), "Massively Parallel Computation: Algorithms and Applications", Foundations and Trends® in Optimization: Vol. 5: No. 4, pp 340-417. http://dx.doi.org/10.1561/2400000025
  PubDate: Thu, 28 Sep 2023 00:00:00 +020
Information Relaxations and Duality in Stochastic Dynamic Programs: A
Review and Tutorial
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: AbstractIn this monograph, we provide an overview of the information relaxation approach for calculating performance bounds in stochastic dynamic programs (DPs). The technique involves (1) relaxing the temporal feasibility (or nonanticipativity) constraints so the decision-maker (DM) has additional information before making decisions, and (2) incorporating a penalty that punishes the DM for violating the temporal feasibility constraints. The goal of this monograph is to provide a self-contained overview of the key theoretical results of the information relaxation approach as well as a review of research that has successfully used these techniques in a broad range of applications. We illustrate the information relaxation approach on applications in inventory management, assortment planning, and portfolio optimization.Suggested CitationDavid B. Brown and James E. Smith (2022), "Information Relaxations and Duality in Stochastic Dynamic Programs: A Review and Tutorial", Foundations and Trends® in Optimization: Vol. 5: No. 3, pp 246-339. http://dx.doi.org/10.1561/2400000027
  PubDate: Mon, 21 Mar 2022 00:00:00 +010
Acceleration Methods
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: AbstractThis monograph covers some recent advances in a range of acceleration techniques frequently used in convex optimization. We first use quadratic optimization problems to introduce two key families of methods, namely momentum and nested optimization schemes. They coincide in the quadratic case to form the Chebyshev method.We discuss momentum methods in detail, starting with the seminal work of Nesterov [1] and structure convergence proofs using a few master templates, such as that for optimized gradient methods, which provide the key benefit of showing how momentum methods optimize convergence guarantees. We further cover proximal acceleration, at the heart of the Catalyst and Accelerated Hybrid Proximal Extragradient frameworks, using similar algorithmic patterns.Common acceleration techniques rely directly on the knowledge of some of the regularity parameters in the problem at hand. We conclude by discussing restart schemes, a set of simple techniques for reaching nearly optimal convergence rates while adapting to unobserved regularity parameters.Suggested CitationAlexandre d’Aspremont, Damien Scieur and Adrien Taylor (2021), "Acceleration Methods", Foundations and Trends® in Optimization: Vol. 5: No. 1-2, pp 1-245. http://dx.doi.org/10.1561/2400000036
  PubDate: Wed, 15 Dec 2021 00:00:00 +010
Algorithms for Verifying Deep Neural Networks
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: AbstractDeep neural networks are widely used for nonlinear functionapproximation, with applications ranging from computervision to control. Although these networks involve the compositionof simple arithmetic operations, it can be verychallenging to verify whether a particular network satisfiescertain input-output properties. This article surveys methodsthat have emerged recently for soundly verifying suchproperties. These methods borrow insights from reachabilityanalysis, optimization, and search. We discuss fundamentaldifferences and connections between existing algorithms. Inaddition, we provide pedagogical implementations of existingmethods and compare them on a set of benchmarkproblems.Suggested CitationChangliu Liu, Tomer Arnon, Christopher Lazarus, Christopher Strong, Clark Barrett and Mykel J. Kochenderfer (2020), "Algorithms for Verifying Deep Neural Networks", Foundations and Trends® in Optimization: Vol. 4: No. . http://dx.doi.org/10.1561/2400000035
  PubDate: Thu, 31 Dec 2020 00:00:00 +010

HOME > Browse the 73 Subjects covered by JournalTOCs
Subject	Total Journals