Decision Making in Hybrid Environments: A Model Aggregation Approach

• URL: http://arxiv.org/abs/2502.05974v2
• Date: Wed, 30 Apr 2025 18:53:12 GMT
• Title: Decision Making in Hybrid Environments: A Model Aggregation Approach
• Authors: Haolin Liu, Chen-Yu Wei, Julian Zimmert,
• Abstract summary: Recent work by Foster, Xu, and Zeevi characterizes the complexity of general online decision making problems.<n>We propose a general extension of DEC that characterizes the hybrid regime.<n>Our framework leads to a flexible algorithm design where the learner learns over subsets of the hypothesis set.
• Score: 26.993355411130505
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent work by Foster et al. (2021, 2022, 2023b) and Xu and Zeevi (2023) developed the framework of decision estimation coefficient (DEC) that characterizes the complexity of general online decision making problems and provides a general algorithm design principle. These works, however, either focus on the pure stochastic regime where the world remains fixed over time, or the pure adversarial regime where the world arbitrarily changes over time. For the hybrid regime where the dynamics of the world is fixed while the reward arbitrarily changes, they only give pessimistic bounds on the decision complexity. In this work, we propose a general extension of DEC that more precisely characterizes this case. Besides applications in special cases, our framework leads to a flexible algorithm design where the learner learns over subsets of the hypothesis set, trading estimation complexity with decision complexity, which could be of independent interest. Our work covers model-based learning and model-free learning in the hybrid regime, with a newly proposed extension of the bilinear classes (Du et al., 2021) to the adversarial-reward case. In addition, our method improves the best-known regret bounds for linear Q*/V* MDPs in the pure stochastic regime.

Related papers

• Learning in Hybrid Active Inference Models [0.8749675983608172]
  We present a novel hierarchical hybrid active inference agent in which a high-level discrete active inference planner sits above a low-level continuous active inference controller. We make use of recent work in recurrent switching linear dynamical systems which implement end-to-end learning of meaningful discrete representations. We apply our model to the sparse Continuous Mountain Car task, demonstrating fast system identification via enhanced exploration and successful planning.
  arXiv  Detail & Related papers  (2024-09-02T08:41:45Z)
• Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient [51.37720227675476]
  We introduce a new variant of the Decision-Estimation Coefficient, and use it to derive new lower bounds that improve upon prior work on three fronts. We provide upper bounds on regret that scale with the same quantity, thereby closing all but one of the gaps between upper and lower bounds in Foster et al. Our results apply to both the regret framework and PAC framework, and make use of several new analysis and algorithm design techniques that we anticipate will find broader use.
  arXiv  Detail & Related papers  (2023-01-19T18:24:08Z)
• Model-Free Reinforcement Learning with the Decision-Estimation Coefficient [79.30248422988409]
  We consider the problem of interactive decision making, encompassing structured bandits and reinforcement learning with general function approximation. We use this approach to derive regret bounds for model-free reinforcement learning with value function approximation, and give structural results showing when it can and cannot help more generally.
  arXiv  Detail & Related papers  (2022-11-25T17:29:40Z)
• GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyond [101.5329678997916]
  We study sample efficient reinforcement learning (RL) under the general framework of interactive decision making. We propose a novel complexity measure, generalized eluder coefficient (GEC), which characterizes the fundamental tradeoff between exploration and exploitation. We show that RL problems with low GEC form a remarkably rich class, which subsumes low Bellman eluder dimension problems, bilinear class, low witness rank problems, PO-bilinear class, and generalized regular PSR.
  arXiv  Detail & Related papers  (2022-11-03T16:42:40Z)
• On the Complexity of Adversarial Decision Making [101.14158787665252]
  We show that the Decision-Estimation Coefficient is necessary and sufficient to obtain low regret for adversarial decision making. We provide new structural results that connect the Decision-Estimation Coefficient to variants of other well-known complexity measures.
  arXiv  Detail & Related papers  (2022-06-27T06:20:37Z)
• The Statistical Complexity of Interactive Decision Making [126.04974881555094]
  We provide a complexity measure, the Decision-Estimation Coefficient, that is proven to be both necessary and sufficient for sample-efficient interactive learning. A unified algorithm design principle, Estimation-to-Decisions (E2D), transforms any algorithm for supervised estimation into an online algorithm for decision making.
  arXiv  Detail & Related papers  (2021-12-27T02:53:44Z)
• Regular Decision Processes for Grid Worlds [0.0]
  We describe an experimental investigation of the recently introduced regular decision processes that support both non-Markovian reward functions as well as transition functions. We provide a tool chain for regular decision processes, algorithmic extensions relating to online, incremental learning, an empirical evaluation of model-free and model-based solution algorithms, and applications in regular, but non-Markovian, grid worlds.
  arXiv  Detail & Related papers  (2021-11-05T17:54:43Z)
• Federated Multi-Armed Bandits [18.95281057580889]
  Federated multi-armed bandits (FMAB) is a new bandit paradigm that parallels the federated learning (FL) framework in supervised learning. This paper proposes a general framework of FMAB and then studies two specific federated bandit models. We show that, somewhat surprisingly, the order-optimal regret can be achieved independent of the number of clients with a careful choice of the update periodicity.
  arXiv  Detail & Related papers  (2021-01-28T18:59:19Z)
• Stein Variational Model Predictive Control [130.60527864489168]
  Decision making under uncertainty is critical to real-world, autonomous systems. Model Predictive Control (MPC) methods have demonstrated favorable performance in practice, but remain limited when dealing with complex distributions. We show that this framework leads to successful planning in challenging, non optimal control problems.
  arXiv  Detail & Related papers  (2020-11-15T22:36:59Z)

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.