Convex duality for stochastic shortest path problems in known and unknown environments

2022-07-31 · Kelli Francis-Staite

This paper studies Stochastic Shortest Path (SSP) problems in known and unknown environments from the perspective of convex optimisation. It first recalls results in the known parameter case, and develops understanding through different proofs. It then focuses on the unknown parameter case, where it studies extended value iteration (EVI) operators. This includes the existing operators used in Rosenberg et al. [26] and Tarbouriech et al. [31] based on the l-1 norm and supremum norm, as well as defining EVI operators corresponding to other norms and divergences, such as the KL-divergence. This paper shows in general how the EVI operators relate to convex programs, and the form of their dual, where strong duality is exhibited. This paper then focuses on whether the bounds from finite horizon research of Neu and Pike-Burke [21] can be applied to these extended value iteration operators in the SSP setting. It shows that similar bounds to [21] for these operators exist, however they lead to operators that are not in general monotone and have more complex convergence properties. In a special case we observe oscillating behaviour. This paper generates open questions on how research may progress, with several examples that require further examination.

📄 PDF Abstract BibTeX arXiv:2208.00330

Code (0)

등록된 구현이 없습니다.

Opinion shaping in social networks using reinforcement learning

2019-10-19 · Vivek Borkar, Alexandre Reiffers-Masson

In this paper, we study how to shape opinions in social networks when the matrix of interactions is unknown. We consider classical opinion dynamics with some stubborn agents and the possibility of continuously influencin…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Solving Constrained Stochastic Shortest Path Problems with Scalarisation

2025-08-24 · Johannes Schmalz, Felipe Trevizan arxiv

Constrained Stochastic Shortest Path Problems (CSSPs) model problems with probabilistic effects, where a primary cost is minimised subject to constraints over secondary costs, e.g., minimise time subject to monetary budg…

Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization

2020-02-13 · NeurIPS 2020 12 · Yan Yan, Yi Xu, Qihang Lin, Wei Liu 외

Epoch gradient descent method (a.k.a. Epoch-GD) proposed by Hazan and Kale (2011) was deemed a breakthrough for stochastic strongly convex minimization, which achieves the optimal convergence rate of $O(1/T)$ with $T$ it…

LEMMA

Convex duality with transaction costs

2015-10-17

Convex duality for two two different super--replication problems in a continuous time financial market with proportional transaction cost is proved. In this market, static hedging in a finite number of options, in additi…

Duality-free Methods for Stochastic Composition Optimization

2017-10-26 · Liu Liu, Ji Liu, DaCheng Tao

We consider the composition optimization with two expected-value functions in the form of $\frac{1}{n}\sum\nolimits_{i = 1}^n F_i(\frac{1}{m}\sum\nolimits_{j = 1}^m G_j(x))+R(x)$, { which formulates many important proble…

Reinforcement Learning