A PDE approach for regret bounds under partial monitoring

• URL: http://arxiv.org/abs/2209.01256v1
• Date: Fri, 2 Sep 2022 20:04:30 GMT
• Title: A PDE approach for regret bounds under partial monitoring
• Authors: Erhan Bayraktar, Ibrahim Ekren, Xin Zhang
• Abstract summary: We study a learning problem in which a forecaster observes partial information. We show that the problem of obtaining regret bounds and efficient algorithms can be tackled by finding appropriate smooth sub/supersolutions.
• Score: 8.277466108000203
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we study a learning problem in which a forecaster only observes partial information. By properly rescaling the problem, we heuristically derive a limiting PDE on Wasserstein space which characterizes the asymptotic behavior of the regret of the forecaster. Using a verification type argument, we show that the problem of obtaining regret bounds and efficient algorithms can be tackled by finding appropriate smooth sub/supersolutions of this parabolic PDE.

Related papers

• Beyond Derivative Pathology of PINNs: Variable Splitting Strategy with Convergence Analysis [6.468495781611434]
  Physics-informed neural networks (PINNs) have emerged as effective methods for solving partial differential equations (PDEs) in various problems. In this study, we prove that PINNs encounter a fundamental issue that the premise is invalid. We propose a textitvariable splitting strategy that addresses this issue by parameterizing the gradient of the solution as an auxiliary variable.
  arXiv  Detail & Related papers  (2024-09-30T15:20:10Z)
• Total Uncertainty Quantification in Inverse PDE Solutions Obtained with Reduced-Order Deep Learning Surrogate Models [50.90868087591973]
  We propose an approximate Bayesian method for quantifying the total uncertainty in inverse PDE solutions obtained with machine learning surrogate models. We test the proposed framework by comparing it with the iterative ensemble smoother and deep ensembling methods for a non-linear diffusion equation.
  arXiv  Detail & Related papers  (2024-08-20T19:06:02Z)
• On Convergence Analysis of Policy Iteration Algorithms for Entropy-Regularized Stochastic Control Problems [19.742628365680353]
  We investigate the issues regarding the convergence of the Policy Iteration Algorithm(PIA) for a class of general continuous-time entropy-regularized control problems. We show that our approach can also be extended to the case when diffusion contains control, in the one dimensional setting but without much extra constraints on the coefficients.
  arXiv  Detail & Related papers  (2024-06-16T14:31:26Z)
• Unisolver: PDE-Conditional Transformers Are Universal PDE Solvers [55.0876373185983]
  We present the Universal PDE solver (Unisolver) capable of solving a wide scope of PDEs. Our key finding is that a PDE solution is fundamentally under the control of a series of PDE components. Unisolver achieves consistent state-of-the-art results on three challenging large-scale benchmarks.
  arXiv  Detail & Related papers  (2024-05-27T15:34:35Z)
• Deep Equilibrium Based Neural Operators for Steady-State PDEs [100.88355782126098]
  We study the benefits of weight-tied neural network architectures for steady-state PDEs. We propose FNO-DEQ, a deep equilibrium variant of the FNO architecture that directly solves for the solution of a steady-state PDE.
  arXiv  Detail & Related papers  (2023-11-30T22:34:57Z)
• Weak-PDE-LEARN: A Weak Form Based Approach to Discovering PDEs From Noisy, Limited Data [0.0]
  We introduce Weak-PDE-LEARN, a discovery algorithm that can identify non-linear PDEs from noisy, limited measurements of their solutions. We demonstrate the efficacy of Weak-PDE-LEARN by learning several benchmark PDEs.
  arXiv  Detail & Related papers  (2023-09-09T06:45:15Z)
• Neural Control of Parametric Solutions for High-dimensional Evolution PDEs [6.649496716171139]
  We develop a novel computational framework to approximate solution operators of evolution partial differential equations (PDEs) We propose to approximate the solution operator of the PDE by learning the control vector field in the parameter space. This allows for substantially reduced computational cost to solve the evolution PDE with arbitrary initial conditions.
  arXiv  Detail & Related papers  (2023-01-31T19:26:25Z)
• A Dimensionality Reduction Method for Finding Least Favorable Priors with a Focus on Bregman Divergence [108.28566246421742]
  This paper develops a dimensionality reduction method that allows us to move the optimization to a finite-dimensional setting with an explicit bound on the dimension. In order to make progress on the problem, we restrict ourselves to Bayesian risks induced by a relatively large class of loss functions, namely Bregman divergences.
  arXiv  Detail & Related papers  (2022-02-23T16:22:28Z)
• Lie Point Symmetry Data Augmentation for Neural PDE Solvers [69.72427135610106]
  We present a method, which can partially alleviate this problem, by improving neural PDE solver sample complexity. In the context of PDEs, it turns out that we are able to quantitatively derive an exhaustive list of data transformations. We show how it can easily be deployed to improve neural PDE solver sample complexity by an order of magnitude.
  arXiv  Detail & Related papers  (2022-02-15T18:43:17Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  We derive a novel problem-dependent lower-bound for regret in finite-horizon Markov Decision Processes (MDPs) We show that our lower-bound is considerably smaller than in the general case and it does not scale with the minimum action gap at all. We show that this last result is attainable (up to $poly(H)$ terms, where $H$ is the horizon) by providing a regret upper-bound based on policy gaps for an optimistic algorithm.
  arXiv  Detail & Related papers  (2021-06-24T13:46:09Z)
• Error bounds for PDE-regularized learning [0.6445605125467573]
  We consider the regularization of a supervised learning problem by partial differential equations (PDEs) We derive error bounds for the obtained approximation in terms of a PDE error term and a data error term.
  arXiv  Detail & Related papers  (2020-03-14T00:51:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.