Exploring Viable Algorithmic Options for Learning from Demonstration (LfD): A Parameterized Complexity Approach

• URL: http://arxiv.org/abs/2205.04989v1
• Date: Tue, 10 May 2022 15:54:06 GMT
• Title: Exploring Viable Algorithmic Options for Learning from Demonstration (LfD): A Parameterized Complexity Approach
• Authors: Todd Wareham
• Abstract summary: In this paper, we show how such a systematic exploration of algorithmic options can be done using parameterized complexity analysis. We show that none of our problems can be solved efficiently either in general or relative to a number of (often simultaneous) restrictions on environments, demonstrations, and policies.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The key to reconciling the polynomial-time intractability of many machine learning tasks in the worst case with the surprising solvability of these tasks by heuristic algorithms in practice seems to be exploiting restrictions on real-world data sets. One approach to investigating such restrictions is to analyze why heuristics perform well under restrictions. A complementary approach would be to systematically determine under which sets of restrictions efficient and reliable machine learning algorithms do and do not exist. In this paper, we show how such a systematic exploration of algorithmic options can be done using parameterized complexity analysis, As an illustrative example, we give the first parameterized complexity analysis of batch and incremental policy inference under Learning from Demonstration (LfD). Relative to a basic model of LfD, we show that none of our problems can be solved efficiently either in general or relative to a number of (often simultaneous) restrictions on environments, demonstrations, and policies. We also give the first known restrictions under which efficient solvability is possible and discuss the implications of our solvability and unsolvability results for both our basic model of LfD and more complex models of LfD used in practice.

Related papers

• EVOLvE: Evaluating and Optimizing LLMs For Exploration [76.66831821738927]
  Large language models (LLMs) remain under-studied in scenarios requiring optimal decision-making under uncertainty. We measure LLMs' (in)ability to make optimal decisions in bandits, a state-less reinforcement learning setting relevant to many applications. Motivated by the existence of optimal exploration algorithms, we propose efficient ways to integrate this algorithmic knowledge into LLMs.
  arXiv  Detail & Related papers  (2024-10-08T17:54:03Z)
• Limits and Powers of Koopman Learning [0.0]
  Dynamical systems provide a comprehensive way to study complex and changing behaviors across various sciences. Koopman operators have emerged as a dominant approach because they allow the study of nonlinear dynamics using linear techniques. This paper addresses a fundamental open question: textitWhen can we robustly learn the spectral properties of Koopman operators from trajectory data of dynamical systems, and when can we not?
  arXiv  Detail & Related papers  (2024-07-08T18:24:48Z)
• A General Framework for Learning from Weak Supervision [93.89870459388185]
  This paper introduces a general framework for learning from weak supervision (GLWS) with a novel algorithm. Central to GLWS is an Expectation-Maximization (EM) formulation, adeptly accommodating various weak supervision sources. We also present an advanced algorithm that significantly simplifies the EM computational demands.
  arXiv  Detail & Related papers  (2024-02-02T21:48:50Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation. Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions. We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
  arXiv  Detail & Related papers  (2023-07-08T15:41:48Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  Existing reinforcement learning algorithms suffer from computational intractability, strong statistical assumptions, and suboptimal sample complexity. We provide the first computationally efficient algorithm that attains rate-optimal sample complexity with respect to the desired accuracy level. Our algorithm, MusIK, combines systematic exploration with representation learning based on multi-step inverse kinematics.
  arXiv  Detail & Related papers  (2023-04-12T14:51:47Z)
• Interpretable Anomaly Detection via Discrete Optimization [1.7150329136228712]
  We propose a framework for learning inherently interpretable anomaly detectors from sequential data. We show that this problem is computationally hard and develop two learning algorithms based on constraint optimization. Using a prototype implementation, we demonstrate that our approach shows promising results in terms of accuracy and F1 score.
  arXiv  Detail & Related papers  (2023-03-24T16:19:15Z)
• Task-Guided IRL in POMDPs that Scales [22.594913269327353]
  In inverse linear reinforcement learning (IRL), a learning agent infers a reward function encoding the underlying task using demonstrations from experts. Most IRL techniques require the computationally forward problem -- computing an optimal policy given a reward function -- in POMDPs. We develop an algorithm that reduces the information while increasing the data efficiency.
  arXiv  Detail & Related papers  (2022-12-30T21:08:57Z)
• Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning [53.17258888552998]
  This work proposes an exploration variant of the basic $Q$-learning protocol with linear function approximation. We show that the performance of the algorithm degrades very gracefully under a novel and more permissive notion of approximation error.
  arXiv  Detail & Related papers  (2022-06-01T23:26:51Z)
• Efficient lifting of symmetry breaking constraints for complex combinatorial problems [9.156939957189502]
  This work extends the learning framework and implementation of a model-based approach for Answer Set Programming. In particular, we incorporate a new conflict analysis algorithm in the Inductive Logic Programming system ILASP.
  arXiv  Detail & Related papers  (2022-05-14T20:42:13Z)
• Adaptive Discretization in Online Reinforcement Learning [9.560980936110234]
  Two major questions in designing discretization-based algorithms are how to create the discretization and when to refine it. We provide a unified theoretical analysis of tree-based hierarchical partitioning methods for online reinforcement learning. Our algorithms are easily adapted to operating constraints, and our theory provides explicit bounds across each of the three facets.
  arXiv  Detail & Related papers  (2021-10-29T15:06:15Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

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.