Segment Trees¶

Segment trees are efficient data structures used for range queries and updates, particularly useful in prioritized experience replay. The implementation is based on OpenAI’s baselines repository and provides efficient operations for priority-based sampling in reinforcement learning.

A segment tree is a binary tree where each leaf represents an element in an array, and each internal node represents some operation (like sum or minimum) over a range of elements. This allows for O(log n) query and update operations, making it ideal for efficiently sampling experiences based on priorities in prioritized replay buffers.

The base SegmentTree class provides the foundation, while SumSegmentTree and MinSegmentTree provide specialized implementations for sum and minimum operations respectively.

from agilerl.components.segment_tree import SumSegmentTree, MinSegmentTree

# Create a sum segment tree for priority-based sampling
sum_tree = SumSegmentTree(capacity=1024)

# Create a min segment tree for finding minimum priorities
min_tree = MinSegmentTree(capacity=1024)

Classes¶

class agilerl.components.segment_tree.SegmentTree(capacity: int, operation: Callable, init_value: float)¶

Create SegmentTree.

Taken from OpenAI baselines github repository: https://github.com/openai/baselines/blob/master/baselines/common/segment_tree.py

Parameters:

capacity (int) – Capacity of segment tree
operation (Callable) – Operation to apply
init_value (float) – Initial value

operate(start: int = 0, end: int = 0) → float¶

Return result of applying self.operation.

Parameters:

start (int) – Start index of segment
end (int) – End index of segment

Returns:

Result of applying self.operation

Return type:

float

class agilerl.components.segment_tree.SumSegmentTree(capacity: int)¶

Create SumSegmentTree.

Taken from OpenAI baselines github repository: https://github.com/openai/baselines/blob/master/baselines/common/segment_tree.py

Parameters:: capacity (int) – Capacity of segment tree

operate(start: int = 0, end: int = 0) → float¶

Return result of applying self.operation.

Parameters:

start (int) – Start index of segment
end (int) – End index of segment

Returns:

Result of applying self.operation

Return type:

float

retrieve(upperbound: float) → int¶

Find the highest index i about upperbound in the tree.

Parameters:: upperbound (float) – Upper bound for cumulative sum
Returns:: Index where cumulative sum is <= upperbound
Return type:: int

sum(start: int = 0, end: int = 0) → float¶

Return sum of elements from start to end index.

Parameters:

start (int, optional) – Start index of range, defaults to 0
end (int, optional) – End index of range, defaults to 0 (meaning capacity)

Returns:

Sum of elements in range [start, end)

Return type:

float

class agilerl.components.segment_tree.MinSegmentTree(capacity: int)¶

Create SegmentTree.

Taken from OpenAI baselines github repository: https://github.com/openai/baselines/blob/master/baselines/common/segment_tree.py

Parameters:: capacity (int) – Capacity of segment tree

min(start: int = 0, end: int = 0) → float¶

Return minimum element from start to end index.

Parameters:

start (int, optional) – Start index of range, defaults to 0
end (int, optional) – End index of range, defaults to 0 (meaning capacity)

Returns:

Minimum element in range [start, end)

Return type:

float

operate(start: int = 0, end: int = 0) → float¶

Return result of applying self.operation.

Parameters:

start (int) – Start index of segment
end (int) – End index of segment

Returns:

Result of applying self.operation

Return type:

float