연구팀이 확률적 미니맥스 트리에서 고정 신뢰도 최적 행동 식별(BAI) 문제를 다루는 2단계 정밀도 트리 탐색 알고리즘 2FFS를 제안했다. 이 문제는 심층 미니맥스 탐색과 언어 모델의 장거리 롤아웃을 활용하는 현대 AI 계획 시스템에서 중요성이 커지고 있다. 핵심 딜레마는 휴리스틱 평가는 비용이 싸지만 편향이 있고, 정확한 롤아웃은 신뢰할 수 있지만 비용이 지나치게 많이 든다는 트레이드오프다.
2FFS는 다중 정밀도 평탄 밴딧(multi-fidelity flat bandit) 아이디어를 트리 구조로 확장하는 방식을 채택했다. 미니맥스 방식의 빠른 확장과 몬테카를로 트리 탐색(MCTS) 방식의 확률적 샘플링을 결합하며, 저비용의 편향된 평가를 활용할 시점과 고비용의 정확한 평가로 국소 인증을 수행할 시점을 적응적으로 결정한다. 연구팀은 고정 신뢰도 정확성에 대한 증명, 정확한 식별에 대한 유한 종료 조건, 일반 깊이 트리에 대한 다항식 깊이 비용 상한을 이론적으로 확립했다.
수치 확률 트리 실험 전반에 걸쳐 2FFS는 기존 BAI-MCTS 기준선에 비해 샘플 수와 연산량을 크게 줄이는 것으로 나타났다. 언어 모델 기반 장거리 롤아웃의 비용이 AI 계획 시스템에서 실질적인 병목이 되는 상황에서, 저비용과 고비용 평가를 상황에 맞게 혼합하는 이 접근은 실용적인 효율화 방향을 제시한다. 깊은 미니맥스 탐색이나 언어 모델 롤아웃을 활용하는 트리 탐색은 정확한 평가를 매번 수행하기엔 비용이 너무 크고, 값싼 휴리스틱에만 의존하면 편향 탓에 최적 행동을 놓치기 쉽다. 2FFS는 이 두 가지 평가 수단을 한 알고리즘 안에 묶어, 어느 시점에 싼 평가를 믿고 어느 시점에 비싼 평가로 결과를 확인할지를 적응적으로 조율한다. 이론적 보장과 실험적 효율을 함께 제시했다는 점에서, 비용 제약이 큰 AI 계획·탐색 문제에 적용될 여지가 있다는 평가다.
