Complex Decision Environments

Introduction and Context

Many reinforcement-learning (RL) problems are more difficult than the standard Markov decision process (MDP) suggests. In a conventional MDP, the agent observes the complete state, the environment is stationary, and one agent’s actions determine the outcome. Real systems commonly violate all three assumptions. A robot may not know its exact location, a medical decision system may observe only noisy patient measurements, several agents may act simultaneously, and the consequences of an action may be delayed across a hierarchy of subtasks.

This chapter develops methods for such environments. It examines partial observability and belief states, partially observable MDPs (POMDPs), hierarchical RL and options, and multi-agent RL (MARL), including cooperation, competition, non-stationarity, and credit assignment. These ideas are important in autonomous vehicles, logistics, games, cybersecurity, recommendation systems, industrial control, and healthcare.

Learning Objectives

By the end of this chapter, a student should be able to:

1. Explain why partial observability violates the ordinary Markov assumption.

2. Represent uncertainty about hidden states using belief states and update beliefs mathematically.

3. Formulate a POMDP and distinguish it from an MDP.

4. Describe hierarchical RL and the options framework.

5. Analyse cooperative and competitive multi-agent environments.

6. Explain non-stationarity, centralized training with decentralized execution, and the credit-assignment problem.

7. Select suitable algorithms and evaluate their limitations in practical applications.

1. Partial Observability

An environment is Markov with respect to state $s_t$ if the conditional distribution of the next state and reward depends on the history only through the current state and action:

\[

P(s_{t+1},r_{t+1}\mid s_0,a_0,\ldots,s_t,a_t)=P(s_{t+1},r_{t+1}\mid s_t,a_t).

\]

The state may contain information that is physically present but unavailable to the agent. Instead of $s_t$, the agent receives an observation $o_t$ generated according to an observation model $Z(o_t\mid s_t)$. The agent therefore acts on incomplete evidence.

Examples include:

• A warehouse robot receives camera images but not its exact pose.
• A trading agent observes prices but not the intentions of other market participants.
• A patient-monitoring system observes intermittent measurements rather than the patient’s complete physiological condition.
• An autonomous vehicle’s sensors may be occluded by weather, traffic, or other objects.

A policy based only on the current observation, $\pi(a_t\mid o_t)$, may be inadequate. Two identical observations can require different actions if the preceding histories differ. For example, an identical corridor image may indicate either that a robot has just entered a building or that it is returning after completing a task.

Memory and recurrent policies

One response is to use a finite history:

\[

h_t=(o_0,a_0,o_1,a_1,\ldots,o_t),

\]

and select actions according to $\pi(a_t\mid h_t)$. Recurrent neural networks, including LSTMs and gated recurrent units, compress history into an internal memory state. This can be effective, but the learned memory is not necessarily interpretable or sufficient. Long histories can also increase learning difficulty.

A more principled representation is a belief state: a probability distribution over possible physical states. Beliefs provide a sufficient statistic for history under the usual POMDP assumptions.

2. Belief States and Bayesian Filtering

Let $b_t(s)$ denote the agent’s belief that the hidden state at time $t$ is $s$:

\[

b_t(s)=P(s_t=s\mid h_t).

\]

A belief is a probability distribution, so $b_t(s)\geq 0$ and $\sum_s b_t(s)=1$ for a discrete state space. After selecting action $a_t$ and receiving observation $o_{t+1}$, the belief is updated in two stages.

First, prediction uses the transition model $T(s'\mid s,a)$:

\[

\bar b_{t+1}(s')=\sum_s T(s'\mid s,a_t)b_t(s).

\]

Second, the observation is incorporated using Bayes’ rule:

\[

b_{t+1}(s')=\frac{Z(o_{t+1}\mid s')\bar b_{t+1}(s')}{\sum_{x}Z(o_{t+1}\mid x)\bar b_{t+1}(x)}.

\]

Here the denominator is the probability of the observed signal and normalizes the distribution. The equations assume a known transition model, a known observation model, and a discrete state space; analogous integrals are used for continuous states.

Worked example: a hidden machine condition

A machine is either Healthy ($H$) or Faulty ($F$). Initially, $P(H)=0.8$ and $P(F)=0.2$. After one operating period, if the machine is healthy it remains healthy with probability $0.9$; if faulty it becomes healthy with probability $0.2$. Thus, before inspection,

\[

\bar b(H)=0.9(0.8)+0.2(0.2)=0.76,

\]

and $\bar b(F)=0.24$. An inspection signal “warning” occurs with probability $0.7$ in state $F$ and $0.1$ in state $H$. Therefore,

\[

P(\text{warning})=0.1(0.76)+0.7(0.24)=0.244.

\]

After a warning,

\[

P(F\mid\text{warning})=\frac{0.7(0.24)}{0.244}\approx0.689.

\]

The warning substantially increases the estimated fault probability, but does not establish certainty. A rational policy can use this updated risk to decide whether to continue operation, inspect further, or perform maintenance.

3. Partially Observable Markov Decision Processes

A POMDP can be specified by the tuple

\[

(\mathcal S,\mathcal A,\mathcal O,T,Z,R,\gamma),

\]

where $\mathcal S$ is the hidden state space, $\mathcal A$ the action space, $\mathcal O$ the observation space, $T$ the transition model, $Z$ the observation model, $R$ the reward function, and $\gamma\in[0,1)$ the discount factor. A finite-horizon formulation may omit discounting or use a horizon-dependent objective.

Although the physical state is hidden, the belief state is itself Markov. The agent can therefore regard the POMDP as an MDP over the continuous belief space. The expected immediate reward for belief $b$ and action $a$ is

\[

R(b,a)=\sum_s b(s)R(s,a).

\]

A belief-space Bellman equation is

\[

V(b)=\max_a\left[R(b,a)+\gamma\sum_o P(o\mid b,a)V(\tau(b,a,o))\right],

\]

where $\tau$ is the Bayesian belief-update function and

\[

P(o\mid b,a)=\sum_{s'}Z(o\mid s')\sum_sT(s'\mid s,a)b(s).

\]

The equation shows why information has value: an action can produce observations that improve later decisions. An information-gathering action may have low immediate reward but high long-term value.

Planning and learning in POMDPs

Exact dynamic programming is often practical only for small finite POMDPs. Common alternatives include:

• Belief-state planning: construct a tree of likely observations and actions.
• Point-based value iteration: update values at a selected set of reachable beliefs rather than all beliefs.
• Online tree search: plan only when a decision is required, as in partially observable variants of Monte Carlo tree search.
• Recurrent model-free RL: learn a policy from observation histories without explicitly estimating beliefs.
• World-model methods: learn transition and observation models and plan in a learned latent state.

Explicit beliefs offer interpretability and calibrated uncertainty when models are reliable. Recurrent policies can scale better in high-dimensional perception problems but may suffer from memory failure, partial observability during training, and poor uncertainty calibration.

4. Hierarchical Reinforcement Learning

Long-horizon tasks often contain reusable subtasks. A delivery robot, for example, may repeatedly navigate to a doorway, avoid obstacles, and dock at a station. Learning every primitive action directly can create a long credit-assignment path and inefficient exploration.

Hierarchical RL decomposes decision-making into levels. A high-level policy selects goals or skills; a lower-level policy executes actions to achieve them. The decomposition can be temporal, spatial, or semantic. It may be designed by experts, discovered from data, or learned jointly.

A useful distinction is:

• Task decomposition: divide a problem into subtasks with identifiable objectives.
• Skill learning: learn policies that accomplish reusable behaviours.
• Goal-conditioned control: condition a policy on a desired goal, such as a target position.
• Planning over skills: treat skills as macro-actions in a higher-level decision process.

Hierarchical structure can improve exploration and transfer, but an inappropriate hierarchy can restrict behaviour or propagate errors from the upper level.

5. The Options Framework

The options framework formalizes temporally extended actions. An option $o$ is defined by

\[

o=(\mathcal I_o,\pi_o,\beta_o),

\]

where $\mathcal I_o$ is the initiation set, $\pi_o(a\mid s)$ is the option’s internal policy, and $\beta_o(s)$ is the probability that the option terminates upon reaching state $s$.

For example, an option “navigate to charging station” may be initiated when the robot is in a known building region, use a navigation policy while active, and terminate on arrival, failure, or timeout.

Options are semi-Markov because one option may last several primitive time steps. If an option produces cumulative discounted reward $R_o$ over $k$ steps and terminates in state $s'$, a high-level action-value backup has the form

\[

Q(s,o)=\mathbb E\left[R_o+\gamma^k\max_{o'}Q(s',o')\right].

\]

The factor $\gamma^k$, rather than $\gamma$, is required because the next decision occurs after $k$ primitive steps. The expectation accounts for stochastic transitions and option policies.

Related approaches include the options framework, feudal RL, hierarchical actor–critic methods, and the MAXQ value-function decomposition. Modern implementations often learn latent skills using mutual-information objectives, contrastive representations, demonstrations, or goal-conditioned experience replay.

Benefits and risks

Hierarchical methods can reduce effective planning depth, support reuse, improve exploration, and make behaviour easier to explain. Their risks include:

• poor subtasks that do not align with the true task;
• an upper-level policy selecting an impossible or unsafe goal;
• termination rules that are too early or too late;
• non-stationary lower-level policies during joint training;
• reduced optimality if the hierarchy excludes necessary behaviours.

A practical design should permit fallback actions, monitor option success rates, and compare hierarchical performance with a strong flat baseline.

6. Multi-Agent Reinforcement Learning

In MARL, multiple agents select actions and receive rewards in a shared environment. A multi-agent stochastic game can be represented by states $s$, individual action sets $\mathcal A_i$, a transition model $T(s'\mid s,a_1,\ldots,a_n)$, and reward functions $R_i(s,a_1,\ldots,a_n)$.

The joint action is $\mathbf a=(a_1,\ldots,a_n)$. An agent’s best action depends on the policies of the other agents. This creates strategic interaction absent from a single-agent MDP.

Cooperation

Agents cooperate when their objectives are aligned or partially aligned. They may share a team reward,

\[

R_1=R_2=\cdots=R_n=R_{team},

\]

or receive individual rewards that encourage a common outcome. Team rewards simplify objective alignment but create a severe credit-assignment problem: if a team succeeds, which agent or action caused the success?

Cooperative methods commonly use centralized training with decentralized execution (CTDE). During training, a centralized critic may observe the joint state and actions, while each actor uses only information available at execution. Value decomposition methods, such as VDN and QMIX, learn individual contributions whose combination estimates a team value. These methods are useful when communication or central coordination is available during training but not deployment.

Competition and mixed motives

In competitive settings, one agent’s gain may be another’s loss. In a two-player zero-sum game, $R_1=-R_2$. Self-play can produce strong strategies, but learning may cycle rather than converge. In mixed-motive settings, agents may cooperate temporarily and compete later, making trust, negotiation, and reputation important.

Game-theoretic concepts such as Nash equilibrium help describe strategic stability. A policy profile is a Nash equilibrium if no agent can improve its expected return by unilaterally changing policy. Finding equilibria in large stochastic games is computationally difficult, and practical deep-RL systems often seek robust performance rather than exact equilibrium computation.

7. Non-Stationarity and Partial Observability in MARL

From one agent’s perspective, other agents’ learning changes the environment. Even if the physical transition function is fixed, the effective transition distribution changes as other policies change. Consequently, experience collected earlier may no longer represent the current data-generating process.

This non-stationarity undermines ordinary replay buffers and independent Q-learning. An agent may attribute a performance change to its own action when the real cause was another agent’s policy update. Partial observability further prevents an agent from knowing the full joint state or other agents’ intentions.

Important responses include:

• centralized critics using joint information during training;
• opponent or teammate modelling;
• recurrent policies that infer hidden intentions;
• fingerprints or policy-version information in replay data;
• self-play with a population of past policies;
• parameter sharing when agents are homogeneous;
• communication protocols, either designed or learned;
• curriculum learning that gradually increases strategic difficulty.

CTDE does not remove the execution constraint; it uses extra information only while learning. If the deployment environment differs from training, the centralized critic can create overfitting and poor generalization.

8. Credit Assignment

Credit assignment asks which decisions deserve responsibility for an outcome. It appears at two levels:

1. Temporal credit assignment: which earlier action caused a delayed reward?

2. Structural or multi-agent credit assignment: which agent or component caused a team outcome?

A single sparse team reward can produce weak learning signals. Difference rewards attempt to measure an agent’s marginal contribution by comparing the team outcome with and without that agent’s contribution. In abstract form,

\[

D_i=G(z)-G(z_{-i},c),

\]

where $G$ is the global outcome, $z$ is the joint decision, $z_{-i}$ excludes agent $i$’s contribution, and $c$ is a counterfactual replacement. The counterfactual must be defined carefully; it may be a default action, an expected action, or a marginalization over alternatives.

Counterfactual multi-agent policy gradients use a centralized critic to estimate how an individual action changes expected team return while holding other agents’ actions fixed or integrating over them. Shaped rewards, event-based rewards, and curriculum tasks can also improve learning, but reward shaping may change the optimal policy unless it satisfies suitable policy-invariance conditions.

Credit assignment should not be confused with blame in a governance sense. A learning signal can be useful for optimization while being inappropriate for assigning legal or moral responsibility.

9. Illustrative Case: Cooperative Warehouse Robots

Background

Consider an illustrative case involving six mobile robots that transport inventory between storage locations and packing stations. Robots share narrow aisles, recharge at limited stations, and must avoid collisions. They receive local camera and lidar observations; a robot cannot directly observe every robot’s position or battery state.

Problem

A flat independent learner receives a team reward based mainly on completed deliveries and penalties for collisions and late orders. Learning is slow because rewards are delayed. The environment is partially observable, and each robot’s policy changes while the others are learning. A robot may also occupy a charging station, preventing another robot with lower battery from charging.

Analysis

The physical location, battery levels, outstanding orders, and traffic conditions form a hidden joint state. Local sensors generate observations. The task is therefore both a POMDP for an individual robot and a multi-agent stochastic game for the fleet. Team rewards create structural credit-assignment difficulties: a delayed delivery may result from congestion caused by several robots.

Approach

A practical CTDE design can use:

1. recurrent actor policies that receive local observations and maintain memory;

2. a centralized training critic that receives fleet-level state information;

3. learned options such as “go to pickup,” “deliver,” “yield,” and “recharge”;

4. a high-level scheduler that assigns delivery or charging goals;

5. difference-style or decomposed rewards for delivery progress, collision avoidance, and congestion reduction;

6. randomized traffic patterns and policies from earlier training checkpoints to improve robustness;

7. safety constraints that override learned actions when collision risk exceeds a threshold.

Outcome

The expected benefit is not merely a higher average delivery rate. Evaluation should compare collision rate, late-delivery rate, energy consumption, fairness of charging access, robustness to sensor failure, and performance when additional robots or changed layouts are introduced. A system that achieves high throughput by repeatedly starving one robot of charging access is not operationally acceptable.

Learning points

The case demonstrates that partial observability, hierarchy, multi-agent non-stationarity, and credit assignment interact. Solving only one issue—for example, adding a recurrent network—does not guarantee reliable fleet behaviour. Training objectives, architecture, evaluation, and safety mechanisms must be designed together.

10. Practical Design and Evaluation Guidance

A professional workflow begins by identifying what is hidden, who controls each action, and whether the objective is shared. Engineers should then decide whether uncertainty requires an explicit belief model, a recurrent representation, or both.

Useful evaluation practices include:

• report multiple random seeds and confidence intervals where feasible;
• compare against flat, independent, and rule-based baselines;
• test unseen layouts, opponents, teammates, and sensor conditions;
• measure individual and team welfare rather than team reward alone;
• inspect failure trajectories, not only average return;
• test sensitivity to communication loss and delayed observations;
• evaluate safety constraints independently of reward performance;
• maintain reproducible environment versions and policy checkpoints.

For deployment, monitoring should detect distribution shift, coordinated failures, reward hacking, and unsafe emergent conventions. Human override, audit logs, access controls, and rollback mechanisms are particularly important in healthcare, transport, finance, and critical infrastructure.

11. Ethical and Governance Considerations

Complex decision environments create governance issues beyond technical performance. A multi-agent system may learn collusive behaviour, discriminate in resource allocation, or exploit weaknesses in an opponent or market. A cooperative policy may maximize aggregate reward while imposing unequal costs on particular users or agents.

Designers should specify who is authorized to set rewards, whose interests are represented, and what constraints cannot be traded for performance. Privacy is relevant when centralized training uses detailed trajectories. Communication policies may reveal sensitive information or create security vulnerabilities. In competitive applications, training against simulated opponents does not justify deployment against real people without risk assessment.

Safety specifications should be treated as constraints or supervisory rules where appropriate, rather than hoping that a penalty in a scalar reward will reliably express every unacceptable outcome. Documentation should describe observation limits, known failure modes, training populations, and conditions under which the policy should not be used.

12. Contemporary Directions and Limitations

Current research explores scalable belief representations, world models, offline MARL, communication learning, population-based training, emergent language, and foundation-model-assisted planning. These developments may improve generalization, but they also introduce new risks: latent-state hallucination, strategic deception, data leakage, and opaque coordination protocols.

No single method dominates. Explicit Bayesian filtering is attractive when models and state spaces are manageable. Recurrent deep policies are flexible but can conceal uncertainty. Hierarchical methods help with long horizons but depend on meaningful abstractions. CTDE improves learning signals but may fail under deployment mismatch. Self-play creates strong adversaries but can produce narrow, non-human strategies.

The appropriate objective is therefore not maximum benchmark score alone. It is reliable decision-making under uncertainty, changing partners and opponents, limited information, and clearly governed operational constraints.

Chapter Summary

Complex decision environments depart from the assumptions of fully observed, single-agent, stationary MDPs. In a partially observable environment, observations do not uniquely identify the physical state, so action selection may require history or a belief state. Bayesian filtering predicts hidden-state distributions through the transition model and updates them using observations. A POMDP formalizes hidden states, observations, rewards, and actions; its belief-state formulation enables planning but may be computationally expensive.

Hierarchical RL addresses long horizons by selecting goals or temporally extended skills. The options framework represents each skill through an initiation set, internal policy, and termination rule. In MARL, agents may cooperate, compete, or combine both motives. Other agents’ changing policies create non-stationarity, while shared rewards create temporal and structural credit-assignment problems. CTDE, recurrent policies, opponent modelling, value decomposition, counterfactual signals, and self-play are important tools, but each has limitations.

Reliable applications require evaluation beyond average reward, including safety, robustness, fairness, communication dependence, and performance under distribution shift. Ethical governance must define acceptable objectives, constraints, accountability, privacy protections, and human oversight.

Key Terms

Partial observability: A condition in which the agent cannot directly access the complete environment state.

Belief state: A probability distribution representing uncertainty over hidden states.

Bayesian filtering: Sequential prediction and observation updating of a belief distribution.

POMDP: A partially observable Markov decision process with hidden states and observations.

Observation model: The probability of receiving an observation given a state.

History: The sequence of observations and actions available to an agent.

Recurrent policy: A policy that uses an internal memory representation of previous events.

Hierarchical reinforcement learning: RL using multiple decision levels or temporally extended skills.

Option: A temporally extended action defined by initiation, internal policy, and termination components.

Semi-Markov decision process: A decision process in which actions may last variable numbers of primitive time steps.

Multi-agent reinforcement learning: RL involving multiple interacting learning agents.

Cooperative game: A multi-agent setting in which agents share or align objectives.

Competitive game: A setting in which agents’ objectives conflict, often represented by opposing rewards.

Non-stationarity: Change in the effective environment dynamics over learning time.

Centralized training with decentralized execution: Training with joint information while execution uses local information.

Credit assignment: Determining which actions, agents, or events caused an outcome.

Difference reward: A reward measuring an agent’s marginal contribution to a global outcome.

Self-play: Training agents against versions of themselves or a population of policies.

Counterfactual: A hypothetical alternative used to estimate an agent’s contribution.

Reward shaping: Modifying rewards to provide more informative learning signals.

Review Questions

Short Answer Questions

1. Why can an identical observation require different actions in a partially observable environment?

2. What are the three components of an option?

3. Define centralized training with decentralized execution.

4. Why does learning by other agents create non-stationarity?

5. Distinguish temporal credit assignment from structural credit assignment.

Long Answer Questions

1. Explain belief-state construction and derive the prediction and observation-update steps for a discrete POMDP.

2. Compare recurrent policies with explicit belief-state planning, including their advantages and limitations.

3. Explain how hierarchical RL and options can improve learning in long-horizon tasks.

4. Analyse cooperation, competition, and mixed motives in multi-agent reinforcement learning.

5. Discuss why centralized critics can help MARL while still producing deployment risks.

Analytical / Application Questions

1. Design a belief update for a two-state equipment-monitoring system with specified transition and sensor probabilities. Explain how the result would affect maintenance decisions.

2. Propose an options-based architecture for an autonomous delivery robot. Specify initiation conditions, internal policies, termination conditions, and possible failure modes.

3. Design an evaluation plan for a team of warehouse robots that measures throughput, safety, fairness, robustness, and credit-assignment quality rather than reward alone.

Multiple Choice Questions with Answers

Question 1

What is the main purpose of a belief state in a POMDP?

A. To store only the most recent observation

B. To represent a probability distribution over hidden states

C. To guarantee that the environment is fully observable

D. To eliminate the need for a transition model

Correct Answer: B. To represent a probability distribution over hidden states

Question 2

Which expression correctly represents the prediction step for a discrete belief state?

A. bar b(s') = sum_s T(s'|s,a)b(s)

B. bar b(s') = sum_s Z(s'|s)b(s)

C. bar b(s') = R(s,a)b(s)

D. bar b(s') = max_a T(s'|s,a)

Correct Answer: A. bar b(s') = sum_s T(s'|s,a)b(s)

Question 3

Which component of an option specifies when it may be selected?

A. Termination function

B. Observation model

C. Initiation set

D. Discount factor

Correct Answer: C. Initiation set

Question 4

Why is gamma raised to k in an option-level backup when an option lasts k steps?

A. The option has k different policies

B. The next decision occurs after k primitive time steps

C. The reward is always multiplied by k

D. The state space contains k states

Correct Answer: B. The next decision occurs after k primitive time steps

Question 5

What characterizes centralized training with decentralized execution?

A. Agents use global information during deployment

B. Training may use joint information, but execution uses permitted local information

C. Agents are trained independently without shared data

D. Only one agent is allowed to act

Correct Answer: B. Training may use joint information, but execution uses permitted local information

Question 6

What is a major cause of non-stationarity in multi-agent reinforcement learning?

A. The reward discount factor is fixed

B. Other agents change their policies during learning

C. The state space is finite

D. Observations are always accurate

Correct Answer: B. Other agents change their policies during learning

Question 7

In a two-player zero-sum game, how are the players’ rewards related?

A. They are always identical

B. Each player receives no reward

C. One player’s reward is the negative of the other’s

D. Rewards are independent of actions

Correct Answer: C. One player’s reward is the negative of the other’s

Question 8

What problem do shared team rewards commonly create?

A. The environment becomes fully observable

B. It becomes difficult to identify each agent’s contribution

C. Agents cannot receive observations

D. The transition model becomes deterministic

Correct Answer: B. It becomes difficult to identify each agent’s contribution

Question 9

Which method is specifically intended to estimate an agent’s marginal contribution to a global outcome?

A. Difference reward

B. Random initialization

C. Observation masking

D. Greedy action selection

Correct Answer: A. Difference reward

Question 10

Why might an information-gathering action be valuable in a POMDP?

A. It always gives an immediate positive reward

B. It can improve later decisions by reducing uncertainty

C. It removes all stochastic transitions

D. It converts every action into an option

Correct Answer: B. It can improve later decisions by reducing uncertainty