Complexity of finite-horizon Markov decision process problems

No abstract is available for this paper.

• Publication year

  2000

• Venue

  JACM

• Publication date

  2000-07-01

• Fields of study

  Mathematics, Computer Science, Engineering

• Identifiers
  DOI 10.1145/347476.347480
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Complexity of Optimal Small Policies

  2000cited by this paper
• A survey of computational complexity results in systems and control

  2000cited by this paper
• Solving POMDPs by Searching the Space of Finite Policies

  1999cited by this paper
• The Decision-Theoretic Interactive Video Advisor

  1999cited by this paper
• Artificial Decision Making Under Uncertainty in Intelligent Buildings

  1999cited by this paper
• On the Undecidability of Probabilistic Planning and Infinite-Horizon Partially Observable Markov Decision Problems

  1999cited by this paper
• Learning Policies with External Memory

  1999cited by this paper
• Bayes Nets in Educational Assessment: Where the Numbers Come From

  1999cited by this paper
• An Application of Uncertain Reasoning to Requirements Engineering

  1999cited by this paper
• Continuous Value Function Approximation for Sequential Bidding Policies

  1999cited by this paper
• Decision-Theoretic Planning

  1999cited by this paper
• My Brain is Full: When More Memory Helps

  1999cited by this paper
• SPUDD: Stochastic Planning using Decision Diagrams

  1999cited by this paper
• How to Elicit Many Probabilities

  1999cited by this paper
• Attention-Sensitive Alerting

  1999cited by this paper
• A Temporal Bayesian Network for Diagnosis and Prediction

  1999cited by this paper
• Integration of Partially Observable Markov Decision Processes and Reinforcement Learning for Simulat

  1999cited by this paper
• Learning Finite-State Controllers for Partially Observable Environments

  1999cited by this paper
• A Method for Speeding Up Value Iteration in Partially Observable Markov Decision Processes

  1999cited by this paper
• Bayesian Poker

  1999cited by this paper
• Learning Hidden Markov Models with Geometrical Constraints

  1999cited by this paper
• Bayesian Networks for Dependability Analysis: an Application to Digital Control Reliability

  1999cited by this paper
• Decision-Theoretic Planning: Structural Assumptions and Computational Leverage

  1999influential reference
• Initial Experiments in Stochastic Satisfiability

  1999cited by this paper
• Finite-memory control of partially observable systems

  1998cited by this paper
• Exact and approximate algorithms for partially observable markov decision processes

  1998cited by this paper
• Complexity issues in Markov decision processes

  1998cited by this paper
• Solving POMDPs by Searching in Policy Space

  1998cited by this paper
• Reinforcement Learning: An Introduction

  1998cited by this paper
• MAXPLAN: A New Approach to Probabilistic Planning

  1998cited by this paper
• The Computational Complexity of Probabilistic Planning

  1998cited by this paper
• Using Caching to Solve Larger Probabilistic Planning Problems

  1998cited by this paper
• Approximation Algorithms for NP-Hard Problems

  1997cited by this paper
• Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes

  1997cited by this paper
• A Model Approximation Scheme for Planning in Partially Observable Stochastic Domains

  1997cited by this paper
• Planning and control in stochastic domains with imperfect information

  1997cited by this paper
• The Complexity of Policy Evaluation for Finite-Horizon Partially-Observable Markov Decision Processes

  1997cited by this paper
• The Complexity of Plan Existence and Evaluation in Probabilistic Domains

  1997cited by this paper
• Probabilistic Propositional Planning: Representations and Complexity

  1997influential reference
• Complexity results for hierarchical task-network planning

  1996cited by this paper
• Planning under uncertainty: structural assumptions and computational leverage

  1996influential reference
• On the Complexity of Partially Observed Markov Decision Processes

  1996cited by this paper
• Algorithms for Sequential Decision Making

  1996cited by this paper
• On the Complexity of Solving Markov Decision Problems

  1995cited by this paper
• Exploiting Structure in Policy Construction

  1995cited by this paper
• Approximating Optimal Policies for Partially Observable Stochastic Domains

  1995cited by this paper
• An Algorithm for Probabilistic Planning

  1995cited by this paper
• Probabilistic Robot Navigation in Partially Observable Environments

  1995cited by this paper
• On the Complexity of Finite Memory Policies for Markov Decision Processes

  1995cited by this paper
• Efficient dynamic-programming updates in partially observable Markov decision processes

  1995cited by this paper
• Expressive Equivalence of Planning Formalisms

  1995cited by this paper
• Decidability and undecidability results for domain-independent planning

  1995cited by this paper
• Markov Decision Processes: Discrete Stochastic Dynamic Programming

  1994cited by this paper
• Acting Optimally in Partially Observable Stochastic Domains

  1994cited by this paper
• Relationships among PL, #L, and the determinant

  1994cited by this paper
• The Computational Complexity of Propositional STRIPS Planning

  1994cited by this paper
• Dynamic Programming

  1993cited by this paper
• The complexity of algorithmic problems on succinct instances

  1992cited by this paper
• A survey of algorithmic methods for partially observed Markov decision processes

  1991influential reference
• PP is closed under intersection

  1991cited by this paper
• Gap-deenable Counting Classes

  1991cited by this paper
• Complexity classes defined by counting quantifiers

  1991cited by this paper
• Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits

  1991cited by this paper
• On the Complexity of VLSI Implementations and Graph Representations of Boolean Functions with Application to Integer Multiplication

  1991cited by this paper
• Gap-De nable Counting Classes

  1991cited by this paper
• Complexity classesde ned by counting quanti ers *

  1991cited by this paper
• A survey of solution techniques for the partially observed Markov decision process

  1991cited by this paper
• Gap-definable counting classes

  1991cited by this paper
• PP is as Hard as the Polynomial-Time Hierarchy

  1991cited by this paper
• Solving H-horizon, stationary Markov decision problems in time proportional to log(H)

  1990cited by this paper
• A very hard log space counting class

  1990cited by this paper
• Polynomial Space Counting Problems

  1989influential reference
• The Complexity of Markov Decision Processes

  1987cited by this paper
• Planning for Conjunctive Goals

  1987cited by this paper
• A Note on Succinct Representations of Graphs

  1986cited by this paper
• On Probabilistic Time and Space

  1985cited by this paper
• Intractable problems in control theory

  1985cited by this paper
• On the succinct representation of graphs

  1984cited by this paper
• On Probabilistic Tape Complexity and Fast Circuits for Matrix Inversion Problems (Extended Abstract)

  1984cited by this paper
• Succinct Representations of Graphs

  1984cited by this paper
• A Statewide Pavement Management System

  1982cited by this paper
• State of the Art—A Survey of Partially Observable Markov Decision Processes: Theory, Models, and Algorithms

  1982cited by this paper
• Finite memory estimation and control of finite probabilistic systems

  1977cited by this paper
• The Optimal Control of Partially Observable Markov Processes over a Finite Horizon

  1973influential reference
• The optimal control of par-tially observable Markov processes

  1971cited by this paper
• Optimal control of partially observable Markovian systems

  1965cited by this paper
• Optimal control of Markov processes with incomplete state information

  1965cited by this paper
• Controlled Random Sequences

  1965cited by this paper
• Sufficient statistics in the optimum control of stochastic systems

  1965cited by this paper
• Dynamic Programming and Markov Processes

  1960cited by this paper
• Complexity Classes Deened by Counting Quantiiers*

  year unknowncited by this paper

• Latent Perspective-Taking via a Schr\"odinger Bridge in Influence-Augmented Local Models

  2026cites this paper
• Formal Analysis of AGI Decision-Theoretic Models and the Confrontation Question

  2026influential citation
• f-Divergence Policy Optimization in Fully Decentralized Cooperative MARL

  2025cites this paper
• Stabilization of industrial processes with time series machine learning

  2025cites this paper
• Partially Observable RL: Benign Structures and Simple Generic Algorithms

  2025cites this paper
• To Distill or Decide? Understanding the Algorithmic Trade-off in Partially Observable Reinforcement Learning

  2025cites this paper
• An Intelligent Path Planning System for Urban Airspace Monitoring: From Infrastructure Assessment to Strategic Optimization

  2025cites this paper
• Optical flow-based markov decision process control strategies for autonomous mobile robots in dynamic environments

  2025cites this paper
• Adaptive and Robust DBSCAN With Multi-Agent Reinforcement Learning

  2025cites this paper
• Belief Re-Use in Partially Observable Monte Carlo Tree Search

  2025cites this paper
• Overcoming the Price of Anarchy by Steering with Recommendations

  2025cites this paper
• Robust Offline Reinforcement Learning for Non-Markovian Decision Processes

  2024cites this paper
• Multi-agent reinforcement learning based optimal energy sensing threshold control in distributed cognitive radio networks with directional antenna

  2024cites this paper
• How to Explore with Belief: State Entropy Maximization in POMDPs

  2024cites this paper
• Fully Decentralized Cooperative Multi-Agent Reinforcement Learning: A Survey

  2024cites this paper
• Combinatorial Games with Incomplete Information

  2024cites this paper
• Efficient Learning of POMDPs with Known Observation Model in Average-Reward Setting

  2024cites this paper
• Solving Truly Massive Budgeted Monotonic POMDPs with Oracle-Guided Meta-Reinforcement Learning

  2024cites this paper
• SHIRE: Enhancing Sample Efficiency using Human Intuition in REinforcement Learning

  2024cites this paper
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations

  2023cites this paper
• Theoretical Hardness and Tractability of POMDPs in RL with Partial Hindsight State Information

  2023cites this paper
• Optimistic MLE: A Generic Model-Based Algorithm for Partially Observable Sequential Decision Making

  2023cites this paper
• On the computational complexity of ethics: moral tractability for minds and machines

  2023cites this paper
• Game Interactive Learning: A New Paradigm towards Intelligent Decision-Making

  2023cites this paper
• Controlling weighted voting games by deleting or adding players with or without changing the quota

  2023cites this paper
• Play it safe or leave the comfort zone? Optimal content strategies for social media influencers on streaming video platforms

  2023cites this paper
• Assume-Guarantee Reinforcement Learning

  2023cites this paper
• Near-Optimal Partially Observable Reinforcement Learning with Partial Online State Information

  2023cites this paper
• Exploiting Causal Graph Priors with Posterior Sampling for Reinforcement Learning

  2023cites this paper
• Convex Reinforcement Learning in Finite Trials

  2023influential citation
• Approximability and efficient algorithms for constrained fixed-horizon POMDPs with durative actions

  2023cites this paper
• Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP

  2023cites this paper
• Artificial virtuous agents in a multi-agent tragedy of the commons

  2022cites this paper
• Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedback

  2022cites this paper
• Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes

  2022cites this paper
• Controller-Based Interactive Proof to Ensure Trust in Multiagent Systems

  2022cites this paper
• Efficient Algorithms for Planning with Participation Constraints

  2022influential citation
• When Is Partially Observable Reinforcement Learning Not Scary?

  2022cites this paper
• The Importance of Non-Markovianity in Maximum State Entropy Exploration

  2022influential citation
• Pre-proof Where to from here ? On the future development of autonomous vehicles from a cognitive systems perspective

  2022cites this paper
• Sample-Efficient Reinforcement Learning of Partially Observable Markov Games

  2022cites this paper
• Automating DBSCAN via Deep Reinforcement Learning

  2022cites this paper
• A new parallelized of hierarchical value iteration algorithm for discounted Markov decision processes

  2022cites this paper
• Partially Observable Markov Decision Processes (POMDPs) and Robotics

  2021cites this paper
• Automated Dynamic Mechanism Design

  2021cites this paper
• AI-Driven Collaborative Resource Allocation for Task Execution in 6G-Enabled Massive IoT

  2021cites this paper
• Polynomial Time Reinforcement Learning in Correlated FMDPs with Linear Value Functions

  2021cites this paper
• Optimal Policies for Quantum Markov Decision Processes

  2021cites this paper
• Probabilistic Planning with Preferences over Temporal Goals

  2021cites this paper
• Online Partial Conditional Plan Synthesis for POMDPs With Safe-Reachability Objectives: Methods and Experiments

  2021cites this paper
• Learning in online MDPs: is there a price for handling the communicating case?

  2021influential citation
• Polynomial Time Reinforcement Learning in Factored State MDPs with Linear Value Functions

  2021cites this paper
• Recurrent Neural Network Controllers Synthesis with Stability Guarantees for Partially Observed Systems

  2021cites this paper
• Agent-Aware State Estimation in Autonomous Vehicles

  2021cites this paper
• Dynamic Programming and Linear Programming for Odds Problem

  2021cites this paper
• Landscape of Machine Implemented Ethics

  2020cites this paper
• Safe Motion Planning under Partial Observability with an Optimal Deterministic Planner

  2020cites this paper
• A comparative study of reinforcement learning techniques to repair models

  2020cites this paper
• Sample-Efficient Reinforcement Learning of Undercomplete POMDPs

  2020cites this paper
• Temporal concatenation for Markov decision processes

  2020cites this paper
• Toward Formalization of Comprehensive Bilingual Dictionaries Creation Planning as Constraint Optimization Problem

  2020cites this paper
• Decidability and Complexity of Action-Based Temporal Planning over Dense Time

  2020cites this paper
• Autonomous Penetration Testing using Reinforcement Learning

  2019cites this paper
• Timeline-based planning: Expressiveness and Complexity

  2019cites this paper
• Point-Based Policy Synthesis for POMDPs With Boolean and Quantitative Objectives

  2019cites this paper
• Artificial intelligence planners for multi-head path planning of SwarmItFIX agents

  2019cites this paper
• Data-Driven Percentile Optimization for Multiclass Queueing Systems with Model Ambiguity: Theory and Application

  2019cites this paper
• Stochastic Dynamic Programming in DASH

  2019cites this paper
• Optimizing over a Restricted Policy Class in MDPs

  2019cites this paper
• Planning for Partial Observability by SAT and Graph Constraints

  2018cites this paper
• From verification to synthesis under cost-utility constraints

  2018cites this paper
• On the Complexity of Value Iteration

  2018cites this paper
• Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches

  2018influential citation
• Online Partial Conditional Plan Synthesis for POMDPs with Safe-Reachability Objectives

  2018cites this paper
• Optimizing over a Restricted Policy Class in Markov Decision Processes

  2018cites this paper
• Model-Based Reinforcement Learning in Contextual Decision Processes

  2018cites this paper
• Resource allocation and loadshedding policies based on Markov decision processes for renewable energy generation and storage 2015

  2018cites this paper
• Query Answering in Probabilistic Data and Knowledge Bases

  2018cites this paper
• Surprising Strategies Obtained by Stochastic Optimization in Partially Observable Games

  2018cites this paper
• Pragmatic-Pedagogic Value Alignment

  2017cites this paper
• Computational Social Choice and Computational Complexity: BFFs?

  2017cites this paper
• On the computability of Solomonoff induction and AIXI

  2017cites this paper
• Multi-Agent Planning by Plan Set Intersection

  2017cites this paper
• Nonparametric General Reinforcement Learning

  2016cites this paper
• Reinforcement Learning as a Framework for Ethical Decision Making

  2016cites this paper
• Stochastic Control via Entropy Compression

  2016cites this paper
• On the Computability of AIXI

  2015cites this paper
• Optimal Threshold Policy for In-Home Smart Grid with Renewable Generation Integration

  2015cites this paper
• Probabilistic Inference Techniques for Scalable Multiagent Decision Making

  2015cites this paper
• Resource allocation and load-shedding policies based on Markov decision processes for renewable energy generation and storage

  2015cites this paper
• Concurrent Markov decision processes for robot team learning

  2015cites this paper
• Probabilistic Knowledge-Based Programs

  2015cites this paper
• RESOURCE ALLOCATION AND LOAD-SHEDDING POLICIES BASED ON MARKOV DECISION PROCESSES FOR RENEWABLE ENERGY GENERATION AND STORAGE by EDWARDS JIMENEZ

  2015cites this paper
• Indemics

  2014cites this paper
• The Odds of Staying on Budget

  2014cites this paper
• Hybrid Answer Set Programming

  2014cites this paper
• Concurrent Markov Decision Processes for Robust Robot Team Learning under Uncertainty

  2014cites this paper
• Scheduling with Contingent Resources and Tasks

  2013cites this paper
• False-Name Manipulation in Weighted Voting Games Is Hard for Probabilistic Polynomial Time

  2013cites this paper
• Adaptive Estimation of Time-Varying Sparse Signals

  2013cites this paper