Decision Theory:The Language of Adaptive Agent Software

Peter Norvig

Chief Designer, Adaptive Systems

Harlequin Inc.

Outline

• Where Is Software Headed?

• The Challenge of Complex Environments

• What Is Adaptive Software?

• What Are Software Agents?

• Why Is Decision Theory The Language?

Where Is Software Today?

• Past: Structured Programming
  • Build complex system to meet static spec.

• Present: Object-Oriented Programming
  • Easier to reorganize when spec. changes
  • Amortize development over several projects

• Problems: Software is still costly and unreliable
  • Hard to respond fast enough to change in spec.
  • Change in environment leads to change in spec.

Where Is Software Headed?

• Object-Oriented ProgrammingReliable, reusable, extensible classes

• Rapid Application DevelopmentContinual feedback helps co-evolve spec.

• Very High Level Programming LanguagesWrite less code; increase productivity

• Dynamic Programming LanguagesDelay decisions; change at run-time; flexibility

• Adaptive ProgrammingAdapt to change; separate function and performance

The Challenge of Complex Environments

• Software is expected to do more in more situations

• Variety of users
  • Power/Naive, Techie/Financial/Clerical, ...

• Variety of systems
  • Win/NT/Mac/Unix, C/S, Portable, DOM, Web,...

• Variety of interactions
  • Real-time, Data Bases, Other Players, ...

• Variety of resources and goals
  • Time, Space, Bandwidth, $, Security, Quality, ...

The Challenge ofComplex Environments

Standard Environment

• Certain

• All inputs accessible

• Deterministic

• Repeatable

• No other players

• Static

• Discrete, digital

• Virtual world

Complex Environment

• Uncertain

• Some inputs hidden

• Nondeterministic

• Unique (consequences)

• Other players (pro, con)

• Dynamic (changes)

• Continuous, analog

• Virtual and Real world

What Is Adaptive Software?

• Adaptive Software: “Software that adapts, with little or no intervention by a programmer, to changes in the environment in which it runs.”

• Common Myths:
  • The Myth of the Specification
  • The Myth of the Black Box
  • The Myth of Design Choices
  • The Myth of the Expert Programmer

The Myth of theSpecification

• Myth: There is a constant that you want to achieve

• Reality:
  • Different users have different preferences
  • The environment is constantly changing
  • The target is really a cloud of related products

• Solution: Expect continual change
  • Design a flexible, evolvable system
  • Make it easy for end-users to make changes(Hard: Stop them from making bad changes)

The Myth of theBlack Box

• Myth: Software specified by functional abstraction

• Reality: Performance characteristics matter!
  • Often need to break abstraction

• Open Implementation solution: Two interfaces:
  • Functional: describes Input/Output
  • Performance tweaking: alters the implementation

• Adaptive solution:
  • Adds feedback for performance characteristics
  • Allows program to make choices autonomously

The Myth of the Black Box

I

• Black Box:
  • Input/Output spec.
  • Can’t talk about performance

• Open Implementation:
  • Performance tweaking, T
  • Designer picks good tweaks

• Adaptive Software:
  • Performance feedback, F
  • Feedback informs tweaks

I

O

The Myth of Design Choices

• Myth: Designers choose best choices to meet spec.

• Reality: Much information is lost during design
  • Making goals Boolean is an arbitrary process
  • Specification is warped to match the achievable
  • Design rationale is left informal or is lost
  • Need to start all over in a new environment

• Solution: Capture how much criteria are worth
  • Let the program make best choices,given a particular environment, criteria

The Myth of the Expert Programmer

• Myth: Programmers are smart enough to solve any problem you throw at them

• Reality: Programmers are only one resource
  • Often it is too expensive (in time or money) to have a programmer in the loop

• Solution: reuse past data and decisions
  • Help to generate new solutions
  • These generated solutions may be better than the programmer’s solutions

Lessons of Object-Oriented Programming

• Abstraction: data (objects), procedural (interfaces)
  • What, not how, it computes

• Reuse: through inherit/delegate and modify

• Composition: through standard techniques:
  • Conditional, sequential, loop/recursion
  • P is closed under composition(But that doesn’t help much)

• No global variables; no top level
  • Any computation might be embedded

Lessons of Adaptive Programming

• Abstraction: plans, preferences, resources
  • What, not how, it acts
  • Resource allocation optimized separately

• Reuse: through parameter-setting optimization

• Composition: accounts for resources explicitly
  • Economic (Market-Oriented) Programming
  • Keep performance profiles; optimize

• No top level goals
  • Any agent might be retargetted to new goal

What Are Software Agents?

• Software Agent: “Software that acts, in accord with a user’s preferences, in an environment.”

• Oxford English Dictionary:
  • From Latin agere, to do:
  • 1 “One who acts or exerts power”
  • 2 “He ... who produces an effect”
  • 3 “Any natural force” (chemistry)
  • 4 “One who does the actual work ...
    • a deputy, substitute, representative”

Features of Agent-ness

• Adaptability: Preferences, Planning, Learning, ...

• Autonomy: Does it act on its own, or for someone?
  • Related issues: security, authority, money

• Lifetime: How does the agent persist?
  • Related issues: adaptability, reliability, learning

• Mobility: Where does the program run?
  • Client/Server, DOM, Web, Java, Telescript, ...

• Communication: HCI and CCI

What Makes Agents Different

• Based on Three Simple Realizations
  • You can't always get what you want
  • You never know what's going to happen
  • You're not the only one in the world
  • (True for my 2-year old and for modern software)

• Leads to three key frameworks:
  • Utility (for “economic” optimization)
  • Probability (for uncertain environment)
  • Distributed multi-agent systems (for other players)

You can't always get what you want

• Traditional

• Choose specifications

• Tradeoffs during design phase

• Set level of aspiration

• Performance poor in different environments

• No theory for failure

• Adaptive

• Choose preferences

• Tradeoffs during run-time as well

• Changing aspirations

• Adapts to different environments

• Graceful degradation

You never know what's going to happen

• Traditional

• Boolean logic:event happened or not

• Hard to recover from incorrect assumption

• Deal with selected contingencies based on static design analysis

• Adaptive

• Probability theory:degree of belief

• Continually track evidence for/against

• Deal with wide range of contingencies based on dynamic computation

You’re not the only one in the world

• Other agents change the environment
  • Predict what they will do; agent models

• Other agents know things you don't
  • Need to communicate
  • “Most of the smart people in the world work for someone else” - Bill Joy

• Other agents can work with or against you
  • Cooperation and competition
  • Authority and delegation

The Adaptive Model of Programming

• Traditional

• Function / class

• Input / output

• Logic-based

• Goal-based

• Sequential, single-

• Hand Programmed

• Fidelity to designer

• Pass test suite

• Adaptive

• Agent / module

• Percept / action

• Probability-based

• Utility-based

• Parallel, multi-

• Trained (Learning)

• Perform well in env.

• Scientific method

Decision Theory Is The Language For

• Describing adaptive software
  • The language for designers, theoreticians

• Building adaptive software
  • The language for implementors

• Communicating with agents
  • The language for run-time messages

• See Also Economics, OR, Medicine, Genetics, ...
  • The language for modern science

Core Technology forAdaptive Software

• Mathematics

• Decision Theory

• Control Theory

• Statistical Optimization

• Economic Theory

• Dynamic Programming

• Markov Decision Processes

• Artificial Intelligence

• Bayesian Networks

• Neural Networks

• Machine Learning

• Anytime Programming

• Reinforcement Learning

• Reflective, Dynamic Languages

The Three Laws of Robotics(and Agents?)

• (1) Don’t harm humans, through action or inaction

• (2) Obey humans, except when conflict with (1)

• (3) Protect self, except when conflict with (1, 2)

• Why Asimov was wrong
  • Too Boolean: need notions of utility, probability
  • Problems with “cause,” “protect,” “harm,” etc.

• Laws can be seen as defining utility function only
  • Still too absolute

• Actually, Asimov probably knew it (Roundabout)

Design for a Rational Decision-Theoretic Agent

• Calculate P(current state)
  • Based on evidence, percept, last action

• Calculate P(Result(Act)) ,U(Result(Act))
  • Nondeterministic: many states, results

• Calculate expected utility EU for each action
  • EU(Act) = ?i P(Resulti (Act))·U(Resulti (Act))

• Choose the Action with highest expected utility
  • Best Act = argmaxA EU(ActA )

• Approximate if not enough time to compute

Real-Time Resource Allocation

• Rationally trade-off Computation vs. Actions
  • Sensing and Computing as information sources
  • Manage based on value of information
  • Value depends on quality, time, ease of use

• Trade-off Value of Information vs. Resources
  • Modularize construction vs. optimization
  • Maintain conditional performance profiles
  • Optimize allocation of resources

Resource Allocation Example

• Path planning problem (robot or internet)
  • I = Interpret(Data)
  • P = PlanPath(A, B, I)

• Path planning algorithm
  • procedure F is PlanPath(A, B, Interpret(Data))

• Find optimal allocation of resources
  • How much time for Interpret vs. PlanPath
  • Based on resources, goals; adapt at run-time

Resource Allocation Computation

• Keep performance profiles, Q, on each component
  • Interpret(Data); Q(Interpret, t) = ...
  • PlanPath(A, B, I); Q(PlanPath, Qi, t) = ...

• Compute performance profile on larger units
  • procedure F is PlanPath(A, B, Interpret(Data))
  • Q(F,t) = max Q(PlanPath, Q(Interpret, t1), t2) where t = t1 + t2

• Allows us to scale up
  • And still allocate resources well

Technology for Multi-Agent Systems

• Market-Oriented Programming
  • Bid in a competitive market of resources
  • The market optimizes the value of resources

• Protocol Engineering
  • Make the market communication efficient

• Incentive Engineering
  • Achieve good for community

• Communication Technology
  • Speech acts; Logic of knowledge; ...

Summary ofAdaptive Software

• Software specified in terms of preferences, values

• Resources are explicitly represented

• Software monitors environment, recognizes change

• Software adapts without programmer intervention

• Automatically reconfigures on preference change

• Historical data informs change; less programming

• Other players explicitly represented

Conclusions

• What Is Adaptive Software?
  • Software that adapts to change with no programmer

• What Are Software Agents?
  • Software that respects user’s preferencesOften mobile, autonomous, long-lived, multi-

• Why Is Decision Theory The Language?
  • It is the only sound foundation for talking about uncertainty in the environment and trade-offs among multiple resources and preferences