Describing a Decision in a Graph: Notation and Context 2026-09-16 01:48 UTC

Overview

A decision in a graph can be described in different ways depending on the structure and semantics of the graph. Below, we present several notational schemes across various contexts.

Decision in a Decision Tree

In a decision tree, a decision corresponds to a non-terminal node with outgoing edges for each possible action or outcome.

• Let be a directed graph.

• denotes a decision node.

• denotes an action taken at node .

• is an edge representing the outcome of action , leading to state .

A decision function is:

Decision in Game or Search Trees

In game theory or AI, a decision node represents a player’s move.

• is a game state.

• is the set of successor states.

• A decision is to select .

A policy can be defined as:

Markov Decision Processes (MDPs)

A Markov Decision Process (MDP) is a mathematical framework used to model decision-making in environments that involve both stochasticity and control. It is commonly applied in fields such as reinforcement learning, operations research, control theory, economics, and robotics.

Formally, an MDP is defined as a 5-tuple:

where:

• is a finite set of states;

• is a finite set of actions;

• is the transition probability function, representing the probability of transitioning to state after taking action in state ;

• is the reward function, giving the expected immediate reward received after taking action in state ;

• is the discount factor, representing the present value of future rewards.

The goal in an MDP is to find a policy , which specifies the action to take in each state, in order to maximise the expected cumulative reward over time.

The value function under a policy is defined as:

An optimal policy maximises this expected return for all states. The associated Bellman optimality equation for the state-action value function is:

MDPs assume the Markov property, where the next state depends only on the current state and action, not on the sequence of events that preceded it. This property, together with a well-defined reward and transition structure, enables tractable analysis and computation of optimal policies in sequential decision-making tasks.

\flushleft{Key Properties:}

• Markov property: Next state depends only on the current state and action.

• Stochastic transitions: State transitions are probabilistic.

• Control: The agent selects actions to influence outcomes.

Generic Graph Decision Points

In a general graph context:

• Let be a decision node.

• Outgoing edges represent options.

Decision set:

Edge Weights and Decision Criteria

Decisions can also be modelled through edge weights, where a choice is made to minimise or maximise a criterion.

• assigns weights to edges.

• From node , choose:

where is the set of outgoing edges from .

Conclusion

Describing a decision in a graph involves not just identifying nodes and edges but encoding the logic of choice. The notation depends on the domain decision trees, games, MDPs, or general graphs and each uses structured mappings from states to actions to define rational or optimal transitions.