A Fast Convergence Theory for Offline Decision Making

• URL: http://arxiv.org/abs/2406.01378v2
• Date: Tue, 03 Dec 2024 18:32:15 GMT
• Title: A Fast Convergence Theory for Offline Decision Making
• Authors: Chenjie Mao, Qiaosheng Zhang,
• Abstract summary: This paper proposes the first generic fast convergence result in general function approximation for offline decision making problems. To unify different settings, we introduce a framework called Decision Making with Offline Feedback (DMOF), which captures a wide range of offline decision making problems. Within this framework, we propose a simple yet powerful algorithm called Empirical Decision with Divergence (EDD), whose upper bound can be termed as a coefficient named Empirical Offline Estimation Coefficient (EOEC)
• Score: 0.1227734309612871
• License:
• Abstract: This paper proposes the first generic fast convergence result in general function approximation for offline decision making problems, which include offline reinforcement learning (RL) and off-policy evaluation (OPE) as special cases. To unify different settings, we introduce a framework called Decision Making with Offline Feedback (DMOF), which captures a wide range of offline decision making problems. Within this framework, we propose a simple yet powerful algorithm called Empirical Decision with Divergence (EDD), whose upper bound can be termed as a coefficient named Empirical Offline Estimation Coefficient (EOEC). We show that EOEC is instance-dependent and actually measures the correlation of the problem. When assuming partial coverage in the dataset, EOEC will reduce in a rate of $1/N$ where $N$ is the size of the dataset, endowing EDD with a fast convergence guarantee. Finally, we complement the above results with a lower bound in the DMOF framework, which further demonstrates the soundness of our theory.

Related papers

• Offline Learning for Combinatorial Multi-armed Bandits [56.96242764723241]
  Off-CMAB is the first offline learning framework for CMAB. Off-CMAB combines pessimistic reward estimations with solvers. Experiments on synthetic and real-world datasets highlight the superior performance of CLCB.
  arXiv  Detail & Related papers  (2025-01-31T16:56:18Z)
• Beyond Non-Degeneracy: Revisiting Certainty Equivalent Heuristic for Online Linear Programming [18.371947752008744]
  We show that Certainty Equivalent achieves uniformly near-optimal regret under mild assumptions on the underlying distribution. Our result implies that, contrary to prior belief, CE effectively beats the curse of degeneracy for a wide range of problem instances. These techniques may find potential applications in broader online decision-making contexts.
  arXiv  Detail & Related papers  (2025-01-03T09:21:27Z)
• Performative Reinforcement Learning with Linear Markov Decision Process [14.75815792682734]
  We study the setting of emphperformative reinforcement learning where the deployed policy affects both the reward and the transition of the underlying Markov decision process. We generalize the results to emphlinear Markov decision processes which is the primary theoretical model of large-scale MDPs.
  arXiv  Detail & Related papers  (2024-11-07T23:04:48Z)
• Offline Behavior Distillation [57.6900189406964]
  Massive reinforcement learning (RL) data are typically collected to train policies offline without the need for interactions. We formulate offline behavior distillation (OBD), which synthesizes limited expert behavioral data from sub-optimal RL data. We propose two naive OBD objectives, DBC and PBC, which measure distillation performance via the decision difference between policies trained on distilled data and either offline data or a near-expert policy.
  arXiv  Detail & Related papers  (2024-10-30T06:28:09Z)
• Understanding, Predicting and Better Resolving Q-Value Divergence in Offline-RL [86.0987896274354]
  We first identify a fundamental pattern, self-excitation, as the primary cause of Q-value estimation divergence in offline RL. We then propose a novel Self-Excite Eigenvalue Measure (SEEM) metric to measure the evolving property of Q-network at training. For the first time, our theory can reliably decide whether the training will diverge at an early stage.
  arXiv  Detail & Related papers  (2023-10-06T17:57:44Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way Partial AUC (OPAUC) and Two-way Partial AUC (TPAUC) measures the average performance of a binary classifier. Most of the existing methods could only optimize PAUC approximately, leading to inevitable biases that are not controllable. We present a simpler reformulation of the PAUC problem via distributional robust optimization AUC.
  arXiv  Detail & Related papers  (2022-10-08T08:26:22Z)
• False Correlation Reduction for Offline Reinforcement Learning [115.11954432080749]
  We propose falSe COrrelation REduction (SCORE) for offline RL, a practically effective and theoretically provable algorithm. We empirically show that SCORE achieves the SoTA performance with 3.1x acceleration on various tasks in a standard benchmark (D4RL)
  arXiv  Detail & Related papers  (2021-10-24T15:34:03Z)
• LSDAT: Low-Rank and Sparse Decomposition for Decision-based Adversarial Attack [74.5144793386864]
  LSDAT crafts perturbations in the low-dimensional subspace formed by the sparse component of the input sample and that of an adversarial sample. LSD works directly in the image pixel domain to guarantee that non-$ell$ constraints, such as sparsity, are satisfied.
  arXiv  Detail & Related papers  (2021-03-19T13:10:47Z)
• Sequential- and Parallel- Constrained Max-value Entropy Search via Information Lower Bound [9.09466320810472]
  We focus on an information-theoretic approach called Max-value Entropy Search (MES) We propose a novel constrained BO method called Constrained Max-value Entropy Search via Information lower BOund (CMES-IBO)
  arXiv  Detail & Related papers  (2021-02-19T08:10:51Z)

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.