본 논문은 강화학습에서 복잡한 환경을 효율적으로 탐색하는 학습 에이전트 설계의 어려움을 다룹니다. 단일 에이전트에서 무작위 값 함수 기반 기법의 효과가 여러 연구에서 입증되었지만, 이러한 무작위성이 다수 에이전트의 동시 탐색에 도움이 되는지에 대한 이론적 이해는 부족했습니다. 본 논문은 이 질문에 긍정적인 답을 제시하는 이론적 결과를 제시합니다. 집계된 상태 표현을 사용하는 무작위 최소제곱 값 반복(RLSVI)에 동시 학습 프레임워크를 적용하여 유한 및 무한 지평 환경 모두에서 다항식 최악의 후회 경계를 증명합니다. 두 설정 모두에서 에이전트당 후회는 $\Theta\left(\frac{1}{\sqrt{N}}\right)$의 최적 속도로 감소하여 동시 학습의 이점을 강조합니다. 또한, 기존 연구 (russo2019worst, agrawal2021improved)에 비해 공간 복잡도를 크게 줄이고(K배 감소), 최악의 후회 경계는 $\sqrt{K}$만 증가함을 보입니다. 마지막으로, 이론적 결과를 뒷받침하는 수치 실험 결과도 제시합니다.
