Using Quantum Interference to Solve Multi-Armed Bandit Problem

Japanese Researchers have devised a system leveraging quantum interference to efficiently solve the Competitive Multi-Armed Bandit problem, a complex decision-making challenge with applications ranging from online advertising to wireless communication.

The team encoded preferences within the Orbital Angular Momentum of photons, optimizing the phases to prevent conflicts between multiple players attempting to maximize rewards; this approach allows for scalability in the number of available options and outperforms existing techniques. This method utilizes purely physical attributes of light to guarantee conflict avoidance in a way impossible for classical systems. “As an example of a system with simple rules for solving complex tasks, our OAM-based method adds to the repertoire of functionality of quantum optics,” the researchers state, demonstrating a new application for quantum optics beyond computation and communication.

Quantum Optics Approach to Reinforcement Learning A new approach to reinforcement learning leverages the inherent properties of light to resolve complex decision-making problems without the need for direct communication between agents. Researchers at institution number 1, including Kohei Konaka and Ryoichi Horisaki, have demonstrated a scalable conflict-free bandit algorithm using a quantum optical setup, published in npj Quantum Information. This work moves beyond traditional computational methods by encoding choices within the physical attributes of photons, specifically their orbital angular momentum (OAM).

The team tackled the Competitive Multi-Armed Bandit (CMAB) problem, a scenario where multiple players independently select options, with potential conflicts arising when they choose the same one. Unlike conventional algorithms that struggle with conflict avoidance without communication, this system utilizes quantum interference to guarantee each player selects a unique option. Each player’s preference is encoded in the OAM amplitudes of photons, while phases are optimized to prevent simultaneous selection of the same arm. This is not the first attempt to apply quantum principles to bandit problems; previous work focused on accelerating classical algorithms or learning quantum states. However, this research distinguishes itself by focusing on physical decision-making, exploiting light’s properties directly for coordination. Building on earlier work, the team redesigned a previous system to eliminate limitations on the initial two-armed MAB problem and improve scalability with a hierarchical architecture. The system has demonstrated improved performance in solving the CMAB problem with a scalable number of options, offering a new functional capability for quantum optics. Competitive Multi-Armed Bandit Problem Formulation The pursuit of efficient decision-making in uncertain environments has led researchers to increasingly complex reinforcement learning models, with the Multi-Armed Bandit (MAB) problem serving as a foundational example. This framework models the core challenge of balancing exploration, gathering information about potentially rewarding options, and exploitation, leveraging existing knowledge to maximize gains. Extending this concept, the Competitive Multi-Armed Bandit (CMAB) problem introduces multiple players vying for limited resources, adding the complication of avoiding simultaneous selection of the same option, known as selection conflict. The researchers explain that “In the CMAB problem, the goal is to maximize the sum of cumulative rewards across all players,” necessitating strategies that account for the actions of others without direct communication. Traditional algorithms often struggle with conflict avoidance in CMAB scenarios, typically requiring players to share information about their choices, which isn’t always feasible. Recent work, however, explores leveraging quantum phenomena to circumvent this limitation, moving beyond purely computational approaches. Researchers at institution number 1 are now focusing on “physical decision making, which exploits physical phenomena directly to solve coordination problems, rather than relying solely on software-based algorithms.” A system utilizing the polarization state of single photons was previously proposed for the two-armed MAB problem, later expanded with a hierarchical architecture to improve scalability. This builds on earlier investigations into quantum solutions for MAB problems, including quantum algorithms for best arm-identification and regret minimization, but distinguishes itself by focusing on physical implementations. The current research utilizes the Orbital Angular Momentum (OAM) of photons, a property with the potential to encode a theoretically infinite number of states, to address the CMAB problem. “Through quantum interference, we can guarantee that players never choose the same options, a property of this simple quantum optical setup that only exists when using individual photons and does not have a classical analog.” This innovative approach aims to resolve the exploration-exploitation dilemma in large-scale CMAB problems while simultaneously preventing selection conflicts. Balancing Exploration and Exploitation in MABs Researchers at Konaka’s team are refining methods to address the fundamental challenge of balancing exploration and exploitation within Multi-Armed Bandit (MAB) problems, a core concept in reinforcement learning. Beyond simply identifying optimal choices, the team is focused on scaling solutions to scenarios involving multiple players, the Competitive Multi-Armed Bandit (CMAB) problem, where coordinating selections without direct communication presents a significant hurdle. Traditional algorithms often falter when attempting to avoid conflicts between players without explicit information sharing, a limitation the researchers aim to overcome. Unlike previous iterations that were initially limited to the two-armed MAB problem and later improved with a hierarchical architecture for scalability, this new system directly encodes player estimations into the OAM states of photons. OAM Encoding for Scalable CMAB Solutions Beyond algorithmic improvements to traditional reinforcement learning, researchers at institution number 1 are increasingly exploring physical systems to directly solve complex decision-making problems; a recent advance leverages the unique properties of light to address the Competitive Multi-Armed Bandit (CMAB) challenge with improved scalability. This approach allows for a theoretically infinite number of states, unlike systems initially limited to the two-armed MAB problem, then improved with a hierarchical architecture for scalability. A key innovation lies in the system’s ability to guarantee conflict avoidance through quantum interference, a feat impossible for classical setups. This redesign addresses limitations of previous work, which exhibited performance dependence on arm index assignment and suffered efficiency degradation as the number of arms increased.

The team demonstrated the system’s effectiveness, achieving enhanced performance in resolving the exploration-exploitation dilemma while simultaneously preventing selection conflicts. Conflict Avoidance via Quantum Interference The pursuit of intelligent algorithms often overlooks a fundamental principle: sometimes, the most effective solutions aren’t computational, but physical. While reinforcement learning excels at optimizing choices, coordinating multiple agents without direct communication presents a persistent challenge; conventional algorithms struggle with conflict avoidance without compromising performance. Researchers at Kohei Konaka, André Röhm, Takatomo Mihana, and Ryoichi Horisaki demonstrate a method that utilizes quantum interference to guarantee conflict avoidance using purely physical attributes of light. This circumvents the need for communication, a significant advantage in scenarios like wireless frequency allocation where direct coordination is inefficient. “We investigate the scaling properties of our proposed method… exhibiting enhanced performance,” the team reports, adding to the growing repertoire of functionality within quantum optics. Prior Work: Polarization-Based Bandit Systems Before harnessing orbital angular momentum, researchers explored using photon polarization to tackle multi-armed bandit problems. Initial investigations focused on a simplified two-armed scenario, where the polarization state of single photons dictated arm selection; vertical polarization represented Arm L, while horizontal polarization signified Arm R. This foundational work, however, faced limitations in scalability, prompting a move towards hierarchical architectures designed to accommodate a greater number of options. Expanding on this, a team proposed a collective decision-making system leveraging quantum interference with polarized photons for the two-player Competitive Multi-Armed Bandit (CMAB) problem. The core innovation lay in ensuring differing detection results for each player through quantum interference, effectively eliminating selection conflicts. The researchers noted that “Crucially, quantum interference ensures that the detection results for the two players are always different, allowing them to make decisions while completely avoiding selection conflicts.” Further development saw the introduction of orbital angular momentum (OAM) as a means of encoding more states, potentially surpassing the limitations of polarization. Efficient measurement of an optical orbital-angular-momentum spectrum comprising more than 50 states. Applications of MABs Beyond Algorithm Optimization The successful demonstration of conflict-free multi-armed bandit (CMAB) algorithms using quantum optics is prompting researchers at institution number 1 to consider applications extending far beyond simply improving computational efficiency. While initial work focused on optimizing algorithms like Softmax, Thompson sampling, and the Upper confidence bound method, the inherent capabilities of this physical approach are now attracting attention in areas demanding decentralized decision-making without direct communication. One particularly relevant area is frequency allocation in wireless communications, where selection conflicts, multiple devices using the same frequency band, degrade performance. “Direct communication between players is often undesirable from the perspective of time and energy efficiency,” the researchers note, highlighting the advantage of a system that avoids conflicts without explicit signaling. Beyond wireless networks, applications could extend to resource allocation in distributed sensor networks, robotic swarms, and even economic modeling where agents must make independent choices in a competitive environment. “We find that our proposed system is effective in addressing the CMAB problem with a greater number of options and exhibits enhanced performance,” the team states, suggesting a pathway toward more robust and adaptable decision-making systems in complex, real-world scenarios. Quantum & Classical Approaches to Bandit Problems Researchers at the forefront of reinforcement learning are increasingly examining how quantum phenomena might offer advantages over classical algorithms, particularly when addressing complex decision-making scenarios. While quantum algorithms have previously been applied to single-player bandit problems to improve efficiency, the application to competitive, multi-player scenarios has remained largely unexplored. Previous attempts at physical implementations of bandit problems initially focused on the two-armed MAB problem, later improved with a hierarchical architecture for scalability. This design guarantees conflict avoidance through quantum interference, a feature impossible to replicate in a classical setup. Source: https://www.nature.com/articles/s41534-026-01201-6 Tags: