nils-herrmann/clean_scirepeval huggingface dataset:
On the Complexity of Policy Iteration

Decision-making problems in uncertain or stochastic domains are often formulated as Markov decision processes (MDPs). Policy iteration (PI) is a popular algorithm for searching over policy-space, the size of which is exponential in the number of states. We are interested in bounds on the complexity of PI that do not depend on the value of the discount factor. In this paper we prove the first such non-trivial, worst-case, upper bounds on the number of iterations required by PI to converge to the optimal policy. Our analysis also sheds new light on the manner in which PI progresses through the space of policies.
Using Eligibility Traces to Find the Best Memoryless Policy in Partially Observable Markov Decision Processes

Recent research on hidden-state reinforcement learning (RL) problems has concentrated on overcoming partial observability by using memory to estimate state. However, such methods are computationally extremely expensive and thus have very limited applicability. This emphasis on state estimation has come about because it has been widely observed that the presence of hidden state or partial observability renders popular RL methods such as Q-learning and Sarsa useless. However, this observation is misleading in two ways: first, the theoretical results supporting it only apply to RL algorithms that do not use eligibility traces, and second these results are worst-case results, which leaves open the possibility that there may be large classes of hidden-state problems in which RL algorithms work well without any state estimation. In this paper we show empirically that Sarsa(λ), a well known family of RL algorithms that use eligibility traces, can work very well on hidden state problems that have good memoryless policies, i.e., on RL problems in which there may well be very poor observability but there also exists a mapping from immediate observations to actions that yields near-optimal return. We apply conventional Sarsa(λ) to four test problems taken from the recent work of Littman, Littman Cassandra and Kaelbling, Parr and Russell, and Chrisman, and in each case we show that it is able to find the best, or a very good, memoryless policy without any of the computational expense of state estimation.
Finite-Sample Convergence Rates for Q-Learning and Indirect Algorithms

In this paper, we address two issues of long-standing interest in the reinforcement learning literature. First, what kinds of performance guarantees can be made for Q-learning after only a finite number of actions? Second, what quantitative comparisons can be made between Q-learning and model-based (indirect) approaches, which use experience to estimate next-state distributions for off-line value iteration? 
 
We first show that both Q-learning and the indirect approach enjoy rather rapid convergence to the optimal policy as a function of the number of state transitions observed. In particular, on the order of only (N log(1/e)/e2)(log(N) + loglog(l/e)) transitions are sufficient for both algorithms to come within e of the optimal policy, in an idealized model that assumes the observed transitions are "well-mixed" throughout an N-state MDP. Thus, the two approaches have roughly the same sample complexity. Perhaps surprisingly, this sample complexity is far less than what is required for the model-based approach to actually construct a good approximation to the next-state distribution. The result also shows that the amount of memory required by the model-based approach is closer to N than to N2. 
 
For either approach, to remove the assumption that the observed transitions are well-mixed, we consider a model in which the transitions are determined by a fixed, arbitrary exploration policy. Bounds on the number of transitions required in order to achieve a desired level of performance are then related to the stationary distribution and mixing time of this policy.
Experimental Results on Learning Stochastic Memoryless Policies for Partially Observable Markov Decision Processes

Partially Observable Markov Decision Processes (POMOPs) constitute an important class of reinforcement learning problems which present unique theoretical and computational difficulties. In the absence of the Markov property, popular reinforcement learning algorithms such as Q-Iearning may no longer be effective, and memory-based methods which remove partial observability via state-estimation are notoriously expensive. An alternative approach is to seek a stochastic memoryless policy which for each observation of the environment prescribes a probability distribution over available actions that maximizes the average reward per timestep. A reinforcement learning algorithm which learns a locally optimal stochastic memoryless policy has been proposed by Jaakkola, Singh and Jordan, but not empirically verified. We present a variation of this algorithm, discuss its implementation, and demonstrate its viability using four test problems.
How to Dynamically Merge Markov Decision Processes

We are frequently called upon to perform multiple tasks that compete for our attention and resource. Often we know the optimal solution to each task in isolation; in this paper, we describe how this knowledge can be exploited to efficiently find good solutions for doing the tasks in parallel. We formulate this problem as that of dynamically merging multiple Markov decision processes (MDPs) into a composite MDP, and present a new theoretically-sound dynamic programming algorithm for finding an optimal policy for the composite MDP. We analyze various aspects of our algorithm and illustrate its use on a simple merging problem.
Predicting Lifetimes in Dynamically Allocated Memory

Predictions of lifetimes of dynamically allocated objects can be used to improve time and space efficiency of dynamic memory management in computer programs. Barrett and Zorn [1993] used a simple lifetime predictor and demonstrated this improvement on a variety of computer programs. In this paper, we use decision trees to do lifetime prediction on the same programs and show significantly better prediction. Our method also has the advantage that during training we can use a large number of features and let the decision tree automatically choose the relevant subset.
Learning curve bounds for a Markov decision process with undiscounted rewards

The goal of learning in Markov decision processes is to find a policy that yields the maximum expected return over time. In problems with large state spaces, computing these averages directly is not feasible; instead, the agent must estimate them by stochastic exploration of the state space. Using methods from statistical mechanics, we study how the agent’s performance depends on the allowed exploration time. In particular, for a simple control problem with undiscounted rewards, we compute a lower bound on the return of policies that appear optimal based on imperfect statistics. This is done in the thermodynamic limit: T ~ co, N 4 cO, o = T/A’ (finite), where T is the number of time steps allotted per policy evaluation and N is the size of the state space.
Reinforcement Learning with Replacing Eligibility Traces Figure 1. Accumulating and Replacing Eligibility Traces. Reinforcement Learning with Replacing Eligibility Traces 2. Td() and Monte Carlo Prediction Methods 2.2. Monte Carlo Algorithms Reinforcement Learning with Replacing Eligibility Traces 5

The eligibility trace is one of the basic mechanisms used in reinforcement learning to handle delayed reward. In this paper we introduce a new kind of eligibility trace, the replacing trace, analyze it theoretically, and show that it results in faster, more reliable learning than the conventional trace. Both kinds of trace assign credit to prior events according to how recently they occurred, but only the conventional trace gives greater credit to repeated events. Our analysis is for conventional and replace-trace versions of the ooine TD(1) algorithm applied to undiscounted absorbing Markov chains. First, we show that these methods converge under repeated presentations of the training set to the same predictions as two well known Monte Carlo methods. We then analyze the relative eeciency of the two Monte Carlo methods. We show that the method corresponding to conventional TD is biased, whereas the method corresponding to replace-trace TD is unbiased. In addition, we show that the method corresponding to replacing traces is closely related to the maximum likelihood solution for these tasks, and that its mean squared error is always lower in the long run. Computational results connrm these analyses and show that they are applicable more generally. In particular, we show that replacing traces sig-niicantly improve performance and reduce parameter sensitivity on the \Mountain-Car" task, a full reinforcement-learning problem with a continuous state space, when using a feature-based function approximator. Two fundamental mechanisms have been used in reinforcement learning to handle delayed reward. One is temporal-diierence (TD) learning, as in the TD() algorithm (Sutton, 1988) and in Q-learning (Watkins, 1989). TD learning in eeect constructs an internal reward signal that is less delayed than the original, external one. However, TD methods can eliminate the delay completely only on fully Markov problems, which are rare in practice. In most problems some delay always remains between an action and its eeective reward, and on all problems some delay is always present during the time before TD learning is complete. Thus, there is 2 a general need for a second mechanism to handle whatever delay is not eliminated by TD learning. The second mechanism that has been widely used for this is the eligibility trace. 1 Introduced by Klopf (1972), eligibility traces have been used in a variety of reinforcement learning systems (e. Systematic empirical studies of eligibility traces in conjunction with TD methods were made by Sutton (1984), and theoretical results …
Reinforcement Learning for Dynamic Channel Allocation in Cellular Telephone Systems

In cellular telephone systems, an important problem is to dynamically allocate the communication resource (channels) so as to maximize service in a stochastic caller environment. This problem is naturally formulated as a dynamic programming problem and we use a reinforcement learning (RL) method to find dynamic channel allocation policies that are better than previous heuristic solutions. The policies obtained perform well for a broad variety of call traffic patterns. We present results on a large cellular system with approximately 4949 states.
Improving Policies without Measuring Merits

Performing policy iteration in dynamic programming should only require knowledge of relative rather than absolute measures of the utility of actions (Werbos, 1991) - what Baird (1993) calls the advantages of actions at states. Nevertheless, most existing methods in dynamic programming (including Baird's) compute some form of absolute utility function. For smooth problems, advantages satisfy two differential consistency conditions (including the requirement that they be free of curl), and we show that enforcing these can lead to appropriate policy improvement solely in terms of advantages.
Markov decision processes in large state spaces

Inthis paperwe propose anew framework for studying Markov decision processes (MDPs), based onideas fromstatistical mechanics. The goal of learning in MDPs is to find a policy that yields the maximum expected return over time. In choosing policies, agents must therefore weigh the prospects of short-term versus long-term gains. We study a simple MDP in which the agent must constantly decide between exploratory jumps and local reward mining in state space. The number of policies to choose from grows exponentially with the size of the state space, N. We view the expected returns as defining an energy landscape over policy space. Methods from statistical mechanics are used to analyze this landscape in the thermodynamic limit N ~ co. We calculate the overall distribution of expected returns, as well as the distribution of returns for policies at a fixed Hamming distance from the optimal one. We briefly discuss the problem of learning optimal policies from empirical estimates of the expected return. As a first step, we relate our findings for the entropy to the limit of hightemperature learning. Numerical simulations support the theoretical results.
Using core beliefs for point-based value iteration

Recent research on point-based approximation algorithms for POMDPs demonstrated that good solutions to POMDP problems can be obtained without considering the entire belief simplex. For instance, the Point Based Value Iteration (PBVI) algorithm [Pineau et al., 2003] computes the value function only for a small set of belief states and iteratively adds more points to the set as needed. A key component of the algorithm is the strategy for selecting belief points, such that the space of reachable beliefs is well covered. This paper presents a new method for selecting an initial set of representative belief points, which relies on finding first the basis for the reachable belief simplex. Our approach has better worst-case performance than the original PBVI heuristic, and performs well in several standard POMDP tasks.
Using Rewards for Belief State Updates in Partially Observable Markov Decision Processes

Partially Observable Markov Decision Processes (POMDP) provide a standard framework for sequential decision making in stochastic environments. In this setting, an agent takes actions and receives observations and rewards from the environment. Many POMDP solution methods are based on computing a belief state, which is a probability distribution over possible states in which the agent could be. The action choice of the agent is then based on the belief state. The belief state is computed based on a model of the environment, and the history of actions and observations seen by the agent. However, reward information is not taken into account in updating the belief state. In this paper, we argue that rewards can carry useful information that can help disambiguate the hidden state. We present a method for updating the belief state which takes rewards into account. We present experiments with exact and approximate planning methods on several standard POMDP domains, using this belief update method, and show that it can provide advantages, both in terms of speed and in terms of the quality of the solution obtained.
Active Learning in Partially Observable Markov Decision Processes

This paper examines the problem of finding an optimal policy for a Partially Observable Markov Decision Process (POMDP) when the model is not known or is only poorly specified. We propose two approaches to this problem. The first relies on a model of the uncertainty that is added directly into the POMDP planning problem. This has theoretical guarantees, but is impractical when many of the parameters are uncertain. The second, called MEDUSA, incrementally improves the POMDP model using selected queries, while still optimizing reward. Results show good performance of the algorithm even in large problems: the most useful parameters of the model are learned quickly and the agent still accumulates high reward throughout the process.
Fetal Heart Rate Deceleration Detection from the Discrete Cosine Transform Spectrum

Automated detection of decelerations in fetal heart rate (FHR) signals can be posed as a problem of signal detection in the presence of noise. We present an algorithm that adaptively selects the resolution of analysis and uses the discrete cosine transform (DCT) to describe the spectrum at short-term and longer-term scales. In so doing we generate near-orthogonal and scale-invariant features that are presented to a feedforward neural network for classification
The Workshop Program at the Nineteenth National Conference on Artificial Intelligence

AAAI presented the AAAI-04 workshop program on July 25-26, 2004 in San Jose, California. This program included twelve workshops covering a wide range of topics in artificial intelligence. The titles of the workshops were as follows: (1) Adaptive Text Extraction and Mining; (2) Agent Organizations: Theory and Practice; (3) Anchoring Symbols to Sensor Data; (4) Challenges in Game AI; (5) Fielding Applications of Artificial Intelligence; (6) Forming and Maintaining Coalitions in Adaptive Multiagent Systems; (7) Intelligent Agent Architectures: Combining the Strengths of Software Engineering and Cognitive Systems; (8) Learning and Planning in Markov Processes--Advances and Challenges; (9) Semantic Web Personalization; (10) Sensor Networks; (11) Spatial and Temporal Reasoning; and (12) Supervisory Control of Learning and Adaptive Systems.
Metrics for Markov Decision Processes with Infinite State Spaces

We present metrics for measuring state similarity in Markov decision processes (MDPs) with infinitely many states, including MDPs with continuous state spaces. Such metrics provide a stable quantitative analogue of the notion of bisimulation for MDPs, and are suitable for use in MDP approximation. We show that the optimal value function associated with a discounted infinite horizon planning task varies continuously with respect to our metric distances.
Learning in non-stationary Partially Observable Markov Decision Processes

We study the problem of finding an optimal policy for a Partially Observable Markov Decision Process (POMDP) when the model is not perfectly known and may change over time. We present the algorithm MEDUSA+, which incrementally improves a POMDP model using selected queries, while still optimizing the reward. Empirical results show the response of the algorithm to changes in the parameters of a model: the changes are learned quickly and the agent still accumulates high reward throughout the process.
Probabilistic robot planning under model uncertainty : an active learning approach

While recent POMDP techniques have been successfully applied to the problem of robot control under uncertainty, they typically assume a known (and stationary) model of the environment. In this paper, we study the problem of finding an optimal policy for controlling a robot in a partially observable domain, where the model is not perfectly known, and may change over time. We present an algorithm called MEDUSA which incrementally learns a POMDP model using oracle queries, while still optimizing a reward function. We demonstrate effectiveness of the approach for realistic robot planning scenarios, with minimal a priori knowledge of the model.
An approximation algorithm for labelled Markov processes: towards realistic approximation

Approximation techniques for labelled Markov processes on continuous state spaces were developed by Desharnais, Gupta, Jagadeesan and Panangaden. However, it has not been clear whether this scheme could be used in practice since it involves inverting a stochastic kernel. We describe a Monte Carlo based implementation scheme for this approximation algorithm. This is, to the best of our knowledge, the first implementation of this approximation scheme. The implementation involves some novel ideas about how to estimate infs using sampling and also replacing the explicit description of subsets of the state space by tests for membership. It is hoped that this work enables more applications of continuous probabilistic LMP theory to emerge.
Metrics for Finite Markov Decision Processes

We present metrics for measuring the similarity of states in a finite Markov decision process (MDP). The formulation of our metrics is based on the notion of bisimulation for MDPs, with an aim towards solving discounted infinite horizon reinforcement learning tasks. Such metrics can be used to aggregate states, as well as to better structure other value function approximators (e.g., memory-based or nearest-neighbor approximators). We provide bounds that relate our metric distances to the optimal values of states in the given MDP.
RedAgent-2003: an autonomous, market-based supply-chain management agent

The Supply Chain Management track of the international Trading Agents Competition (TAC SCM) was introduced in 2003 as a test-bed for researchers interested in building autonomous agents that act in dynamic supply chains. TAC SCM provides a challenging scenario for existing AI decision-making algorithms, due to the high dimensionality and the non-determinism of the environment, as well as the combinatorial nature of the problem. In this paper we present RedAgent, the winner of the first TAC SCM competition. RedAgent is based on a multi-agent design, in which many simple, heuristic agents manage tasks such as fulfilling customer orders or procuring particular resources. The key idea is to use internal markets as the main decision mechanism, in order to determine what products to focus on and how to allocate the existing resources. The internal markets ensure the coordination of the individual agents, but at the same time provide price estimates for the goods that RedAgent has to sell and purchase, a key feature in this domain. We describe RedAgentýs architecture and analyze its behavior based on data from the competition.
Redagent: winner of TAC SCM 2003

The Supply Chain Management track of the international trading Agents Competition (TAC ACM) provides a challenging scenario for existing AI decision-making algorithms, due to the high dimensionality and the non-determinism of the environment. Our entry in this competition, RedAgent, is centered around the idea of using an internal market in order to determine what products to focus on and how to allocate the existing resources. This simple design provided a very efficient search mechanism, while at the same time producing price estimates for components, as well as bidding estimates on customer orders.
Classification Using Φ-Machines and Constructive Function Approximation

This article presents a new classification algorithm, called CLEF, which induces a Φ-machine by constructing its own features based on the training data. The features can be viewed as defining subsets of the instance space, and they allow CLEF to create useful non-linear functions over the input variables. The algorithm is guaranteed to find a classifier that separates the training instances, if such a separation is possible. We compare CLEF empirically to several other classification algorithms, including a well-known decision tree inducer, an artificial neural network inducer, and a support vector machine inducer. Our results show that the CLEF-induced Φ-machines and support vector machines have similar accuracy on the suite tested, and that both are significantly more accurate than the other classifiers produced. We argue that the classifiers produced by CLEF are easy to interpret, and hence may be preferred over support vector machines in certain circumstances.
Sparse Distributed Memories for On-Line Value-Based Reinforcement Learning

In this paper, we advocate the use of Sparse Distributed Memories (SDMs) for on-line, value-based reinforcement learning (RL). SDMs provide a linear, local function approximation scheme, designed to work when a very large/ high-dimensional input (address) space has to be mapped into a much smaller physical memory. We present an implementation of the SDM architecture for on-line, value-based RL in continuous state spaces. An important contribution of this paper is an algorithm for dynamic on-line allocation and adjustment of memory resources for SDMs, which eliminates the need for choosing the memory size and structure a priori. In our experiments, this algorithm provides very good performance while efficiently managing the memory resources.