Ray: [RLlib] PrioritizedReplayBuffer raises "IndexError: list index out of range" from SegmentTree

[ymd-h]

What is the problem?

Ray version and other system information (Python version, TensorFlow version, OS):

Docker image python:3.7

• Python 3.7.5
• Linux (Debian Buster)
• Ray 0.8.1

docker run -it python:3.7 bash
pip install ray[rllib] pandas

(Another issue: Pandas is missing from install_requires, needed manual installation.)

Reproduction (REQUIRED)

Please provide a script that can be run to reproduce the issue. The script should have no external library dependencies (i.e., use fake or mock data / environments):

from ray.rllib.optimizers.replay_buffer import PrioritizedReplayBuffer as PRB

buffer_size = 4096
prb = PRB(buffer_size,alpha=0.4)

for _ in range(buffer_size):
    prb.add(obs_t=0,
            action=0,
            reward=0,
            obs_tp1=0,
            done=0,
            weight=0.5)

prb.sample(1,beta=0.5)

Output

WARNING: Not monitoring node memory since `psutil` is not installed. Install this with `pip install psutil` (or ray[debug]) to enable debugging of memory-related crashes.
Couldn't import `requests` library. Be sure to install it on the client side.
Couldn't import `requests` library. Be sure to install it on the client side.
Traceback (most recent call last):
  File "/usr/local/lib/python3.7/site-packages/ray/tune/web_server.py", line 16, in <module>
    import requests  # `requests` is not part of stdlib.
ModuleNotFoundError: No module named 'requests'
Traceback (most recent call last):
  File "bug_report.py", line 13, in <module>
    done=0)
TypeError: add() missing 1 required positional argument: 'weight'
root@0ca9d90c8145:/test# python bug_report.py
WARNING: Not monitoring node memory since `psutil` is not installed. Install this with `pip install psutil` (or ray[debug]) to enable debugging of memory-related crashes.
Couldn't import `requests` library. Be sure to install it on the client side.
Couldn't import `requests` library. Be sure to install it on the client side.
Traceback (most recent call last):
  File "/usr/local/lib/python3.7/site-packages/ray/tune/web_server.py", line 16, in <module>
    import requests  # `requests` is not part of stdlib.
ModuleNotFoundError: No module named 'requests'
Traceback (most recent call last):
  File "bug_report.py", line 16, in <module>
    prb.sample(1,beta=0.5)
  File "/usr/local/lib/python3.7/site-packages/ray/rllib/optimizers/replay_buffer.py", line 233, in sample
    idxes = self._sample_proportional(batch_size)
  File "/usr/local/lib/python3.7/site-packages/ray/rllib/optimizers/replay_buffer.py", line 167, in _sample_proportional
    mass = random.random() * self._it_sum.sum(0, len(self._storage))
  File "/usr/local/lib/python3.7/site-packages/ray/rllib/optimizers/segment_tree.py", line 103, in sum
    return super(SumSegmentTree, self).reduce(start, end)
  File "/usr/local/lib/python3.7/site-packages/ray/rllib/optimizers/segment_tree.py", line 79, in reduce
    return self._reduce_helper(start, end, 1, 0, self._capacity - 1)
  File "/usr/local/lib/python3.7/site-packages/ray/rllib/optimizers/segment_tree.py", line 53, in _reduce_helper
    node_end))
  File "/usr/local/lib/python3.7/site-packages/ray/rllib/optimizers/segment_tree.py", line 53, in _reduce_helper
    node_end))
  File "/usr/local/lib/python3.7/site-packages/ray/rllib/optimizers/segment_tree.py", line 53, in _reduce_helper
    node_end))
  [Previous line repeated 9 more times]
  File "/usr/local/lib/python3.7/site-packages/ray/rllib/optimizers/segment_tree.py", line 51, in _reduce_helper
    self._reduce_helper(start, mid, 2 * node, node_start, mid),
  File "/usr/local/lib/python3.7/site-packages/ray/rllib/optimizers/segment_tree.py", line 41, in _reduce_helper
    return self._value[node]
IndexError: list index out of range

If we cannot run your script, we cannot fix your issue.

• [x] I have verified my script runs in a clean environment and reproduces the issue.
• [x] I have verified the issue also occurs with the latest wheels.

Reason

end (upper bound) of SegmentTree.reduce is "inclusive", but ReplayBuffer._sample_proportional calls with "exclusive" upper bound style (through SumSegmentTree.sum), resulting out of index error.

---

SegmentTree.reduce
https://github.com/ray-project/ray/blob/b6233dff3cec42696f2ea0eea286ded48f02e79b/rllib/optimizers/segment_tree.py#L75-L76

---

PrioritizedReplayBuffer._sample_proportional
https://github.com/ray-project/ray/blob/b6233dff3cec42696f2ea0eea286ded48f02e79b/rllib/optimizers/replay_buffer.py#L167

---

SumSegmentTree.sum
https://github.com/ray-project/ray/blob/b6233dff3cec42696f2ea0eea286ded48f02e79b/rllib/optimizers/segment_tree.py#L103

[sven1977]

Thanks for filing this! Will take a look.

[sven1977]

@yamada-github-account
This bug has been fixed along with other issues related to our SegmentTree implementation in this PR here: https://github.com/ray-project/ray/pull/7555
We also added detailed sampling test cases for our PR-buffer to make sure prioritized sampling works as expected.

Again, thanks for bringing this to our attention!
Closing the issue.