[Jairsubscribers] JAIR Update

[JAIRMAIL]

CONTENTS:
  I. New JAIR Articles 
  II. Instructions for Obtaining Articles 
 
Dear JAIR subscriber:
 This message lists papers that have been recently published in JAIR
and describes how to access them. (If you wish to remove yourself from
this mailing list, see section II.)  

Grunwald, P.D. and Halpern, J.Y. 
  "Updating Probabilities" 
Lin, F. 
  "Compiling Causal Theories to Successor State Axioms and STRIPS-Like 
   Systems"
Weiss, G.M. and Provost, F.
  "Learning When Training Data are Costly: The Effect of Class Distribution 
   on Tree Induction"
Wray, R.E. and Laird, J.E. 
  "An Architectural Approach to Ensuring Consistency in Hierarchical Execution"
Guestrin, C., Koller, D., Parr, R. and Venkataraman, S. 
  "Efficient Solution Algorithms for Factored MDPs"
Console, L., Picardi, C. and Theseider Dupre, D. 
  "Temporal Decision Trees: Model-based Diagnosis of Dynamic Systems On-Board"
Walsh, W.E. and Wellman, M.P. 
  "Decentralized Supply Chain Formation: A Market Protocol and Competitive 
   Equilibrium Analysis"
Price, B. and Boutilier, C. 
  "Accelerating Reinforcement Learning through Implicit Imitation"
Sanchez, R. and Kambhampati, S. 
  "AltAltp: Online Parallelization of Plans with Heuristic State Search"

----------------------------------------------------------------
I. New JAIR Articles 

Grunwald, P.D. and Halpern, J.Y. (2003)
  "Updating Probabilities", Volume 19, pages 243-278.
   For quick access go to <http://www.jair.org/abstracts/grunwald03a.html>

Abstract: As examples such as the Monty Hall puzzle show, applying
conditioning to update a probability distribution on a ``naive
space'', which does not take into account the protocol used, can often
lead to counterintuitive results.  Here we examine why.  A criterion
known as CAR (``coarsening at random'') in the statistical literature
characterizes when ``naive'' conditioning in a naive space works.  We
show that the CAR condition holds rather infrequently, and we provide
a procedural characterization of it, by giving a randomized algorithm
that generates all and only distributions for which CAR holds. This
substantially extends previous characterizations of CAR.  We also
consider more generalized notions of update such as Jeffrey
conditioning and minimizing relative entropy (MRE).  We give a
generalization of the CAR condition that characterizes when Jeffrey
conditioning leads to appropriate answers, and show that there exist
some very simple settings in which MRE essentially never gives the
right results.  This generalizes and interconnects previous results
obtained in the literature on CAR and MRE.

Lin, F. (2003)
  "Compiling Causal Theories to Successor State Axioms and STRIPS-Like 
   Systems", Volume 19, pages 279-314.
   An online appendix (Benchmark action domain descriptions) is also a available.
   For quick access go to <http://www.jair.org/abstracts/lin03a.html>

Abstract: We describe a system for specifying the effects of
actions. Unlike those commonly used in AI planning, our system uses an
action description language that allows one to specify the effects of
actions using domain rules, which are state constraints that can
entail new action effects from old ones. Declaratively, an action
domain in our language corresponds to a nonmonotonic causal theory in
the situation calculus. Procedurally, such an action domain is
compiled into a set of logical theories, one for each action in the
domain, from which fully instantiated successor state-like axioms and
STRIPS-like systems are then generated. We expect the system to be a
useful tool for knowledge engineers writing action specifications for
classical AI planning systems, GOLOG systems, and other systems where
formal specifications of actions are needed.


Weiss, G.M. and Provost, F. (2003)
  "Learning When Training Data are Costly: The Effect of Class Distribution 
   on Tree Induction", Volume 19, pages 315-354.
   For quick access go to <http://www.jair.org/abstracts/weiss03a.html>

Abstract: For large, real-world inductive learning problems, the
number of training examples often must be limited due to the costs
associated with procuring, preparing, and storing the training
examples and/or the computational costs associated with learning from
them. In such circumstances, one question of practical importance is:
if only n training examples can be selected, in what proportion should
the classes be represented?  In this article we help to answer this
question by analyzing, for a fixed training-set size, the relationship
between the class distribution of the training data and the
performance of classification trees induced from these data. We study
twenty-six data sets and, for each, determine the best class
distribution for learning.  The naturally occurring class distribution
is shown to generally perform well when classifier performance is
evaluated using undifferentiated error rate (0/1 loss).  However, when
the area under the ROC curve is used to evaluate classifier
performance, a balanced distribution is shown to perform well.  Since
neither of these choices for class distribution always generates the
best-performing classifier, we introduce a budget-sensitive
progressive sampling algorithm for selecting training examples based
on the class associated with each example.  An empirical analysis of
this algorithm shows that the class distribution of the resulting
training set yields classifiers with good (nearly-optimal)
classification performance.


Wray, R.E. and Laird, J.E. (2003)
  "An Architectural Approach to Ensuring Consistency in Hierarchical 
   Execution", Volume 19, pages 355-398.
   For quick access go to <http://www.jair.org/abstracts/wray03a.html>

Abstract: Hierarchical task decomposition is a method used in many
agent systems to organize agent knowledge.  This work shows how the
combination of a hierarchy and persistent assertions of knowledge can
lead to difficulty in maintaining logical consistency in asserted
knowledge. We explore the problematic consequences of persistent
assumptions in the reasoning process and introduce novel potential
solutions.  Having implemented one of the possible solutions, Dynamic
Hierarchical Justification, its effectiveness is demonstrated with an
empirical analysis.


Guestrin, C., Koller, D., Parr, R. and Venkataraman, S. (2003)
  "Efficient Solution Algorithms for Factored MDPs",
   Volume 19, pages 399-468.
   For quick access go to <http://www.jair.org/abstracts/guestrin03a.html>

Abstract: This paper addresses the problem of planning under
uncertainty in large Markov Decision Processes (MDPs). Factored MDPs
represent a complex state space using state variables and the
transition model using a dynamic Bayesian network. This representation
often allows an exponential reduction in the representation size of
structured MDPs, but the complexity of exact solution algorithms for
such MDPs can grow exponentially in the representation size.  In this
paper, we present two approximate solution algorithms that exploit
structure in factored MDPs.  Both use an approximate value function
represented as a linear combination of basis functions, where each
basis function involves only a small subset of the domain variables.
A key contribution of this paper is that it shows how the basic
operations of both algorithms can be performed efficiently in closed
form, by exploiting both additive and context-specific structure in a
factored MDP.  A central element of our algorithms is a novel linear
program decomposition technique, analogous to variable elimination in
Bayesian networks, which reduces an exponentially large LP to a
provably equivalent, polynomial-sized one.  One algorithm uses
approximate linear programming, and the second approximate dynamic
programming.  Our dynamic programming algorithm is novel in that it
uses an approximation based on max-norm, a technique that more
directly minimizes the terms that appear in error bounds for
approximate MDP algorithms.  We provide experimental results on
problems with over 10^40 states, demonstrating a promising indication
of the scalability of our approach, and compare our algorithm to an
existing state-of-the-art approach, showing, in some problems,
exponential gains in computation time.


Console, L., Picardi, C. and Theseider Dupré, D. (2003)
  "Temporal Decision Trees: Model-based Diagnosis of Dynamic Systems On-Board",
   Volume 19, pages 469-512.
   For quick access go to <http://www.jair.org/abstracts/console03a.html>

Abstract: The automatic generation of decision trees based on off-line
reasoning on models of a domain is a reasonable compromise between the
advantages of using a model-based approach in technical domains and
the constraints imposed by embedded applications.  In this paper we
extend the approach to deal with temporal information. We introduce a
notion of temporal decision tree, which is designed to make use of
relevant information as long as it is acquired, and we present an
algorithm for compiling such trees from a model-based reasoning
system.

Walsh, W.E. and Wellman, M.P. (2003)
  "Decentralized Supply Chain Formation: A Market Protocol and Competitive 
   Equilibrium Analysis", Volume 19, pages 513-567.
   For quick access go to <http://www.jair.org/abstracts/walsh03a.html>

Abstract: Supply chain formation is the process of determining the
structure and terms of exchange relationships to enable a multilevel,
multiagent production activity.  We present a simple model of supply
chains, highlighting two characteristic features: hierarchical subtask
decomposition, and resource contention.  To decentralize the formation
process, we introduce a market price system over the resources
produced along the chain.  In a competitive equilibrium for this
system, agents choose locally optimal allocations with respect to
prices, and outcomes are optimal overall.  To determine prices, we
define a market protocol based on distributed, progressive auctions,
and myopic, non-strategic agent bidding policies.  In the presence of
resource contention, this protocol produces better solutions than the
greedy protocols common in the artificial intelligence and multiagent
systems literature.  The protocol often converges to high-value supply
chains, and when competitive equilibria exist, typically to
approximate competitive equilibria.  However, complementarities in
agent production technologies can cause the protocol to wastefully
allocate inputs to agents that do not produce their outputs.  A
subsequent decommitment phase recovers a significant fraction of the
lost surplus.


Price, B. and Boutilier, C. (2003)
  "Accelerating Reinforcement Learning through Implicit Imitation",
   Volume 19, pages 569-629.
   For quick access go to <http://www.jair.org/abstracts/price03a.html>

Abstract: Imitation can be viewed as a means of enhancing learning in
multiagent environments.  It augments an agent's ability to learn
useful behaviors by making intelligent use of the knowledge implicit
in behaviors demonstrated by cooperative teachers or other more
experienced agents.  We propose and study a formal model of implicit
imitation that can accelerate reinforcement learning dramatically in
certain cases.  Roughly, by observing a mentor, a
reinforcement-learning agent can extract information about its own
capabilities in, and the relative value of, unvisited parts of the
state space.  We study two specific instantiations of this model, one
in which the learning agent and the mentor have identical abilities,
and one designed to deal with agents and mentors with different action
sets.  We illustrate the benefits of implicit imitation by integrating
it with prioritized sweeping, and demonstrating improved performance
and convergence through observation of single and multiple mentors.
Though we make some stringent assumptions regarding observability and
possible interactions, we briefly comment on extensions of the model
that relax these restricitions.


Sanchez, R. and Kambhampati, S. (2003)
  "AltAltp: Online Parallelization of Plans with Heuristic State Search",
   Volume 19, pages 631-657.
   For quick access go to <http://www.jair.org/abstracts/sanchez03a.html>

Abstract: Despite their near dominance, heuristic state search
planners still lag behind disjunctive planners in the generation of
parallel plans in classical planning. The reason is that directly
searching for parallel solutions in state space planners would require
the planners to branch on all possible subsets of parallel actions,
thus increasing the branching factor exponentially. We present a
variant of our heuristic state search planner AltAlt, called AltAltp
which generates parallel plans by using greedy online parallelization
of partial plans. The greedy approach is significantly informed by the
use of novel distance heuristics that AltAltp derives from a
graphplan-style planning graph for the problem. While this approach is
not guaranteed to provide optimal parallel plans, empirical results
show that AltAltp is capable of generating good quality parallel plans
at a fraction of the cost incurred by the disjunctive planners.

----------------------------------------------------------------
II. INSTRUCTIONS FOR OBTAINING ARTICLES

When an article is published in JAIR, it is immediately available from
our distribution sites. The article is also immediately announced and
posted on the USENET newsgroups comp.ai.jair.announce and
comp.ai.jair.papers.  Periodically, we send out announcements like
this to our mailing list announcing recent papers, for those of you
who do not read the JAIR newsgroups.  (Note that if you read the JAIR
newsgroups, you have the advantage of immediately being notified about
new papers.)  

To obtain an article, there are a variety of access methods:

-- WWW: You can access our server through the web. The URL is:
      http://www.jair.org/

-- Anonymous FTP from the site below:
      CMU Machine:   ftp.cs.cmu.edu         directory:  project/jair

-- Newsgroups: read comp.ai.jair.announce and comp.ai.jair.papers

	    To Remove Yourself from this Mailing List

To remove yourself from the JAIR subscribers mailing list, visit our
Web site (http://www.jair.org/), follow the link "notify me of new
articles", enter your email address in the form at the bottom of the
page, and follow the directions.  In the event that you've already
deleted yourself from the list and we keep sending you messages like
this one, send mail to jair-ed@isi.edu.