PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Reinforcement Learning for Dynamic Multichannel Access in Wireless Networks

Shangxing Wang, Hanpeng Liu, Pedro Henrique Gomes, Bhaskar Krishnamachari

arXiv:1802.06958v1cs.NI

TL;DR

The paper addresses dynamic access to correlated channels with unknown statistics under partial observation and computationally difficult optimization. It formulates the problem as a POMDP and applies DQN for online, model-free policy learning. DQN matches the known optimum in fixed-pattern switching, performs near-optimally in complex scenarios, and adapts to time-varying environments.

  • Problem

    Dynamic multichannel access must maximize successful transmissions when correlated channels have unknown statistics and only partial observations are available, while exact POMDP solutions require exponential computation.

  • Method

    The paper uses an end-to-end DQN that learns channel-access policies online from historical observations and actions without prior system dynamics.

  • Results

    DQN achieves the same optimal performance as the known-system policy in fixed-pattern switching, near-optimal performance in complex scenarios, and good performance after detecting and relearning under non-stationarity.

  • Takeaways & Limitations

    DQN provides a model-free approach for correlated-channel access and can adapt its learned policy when the environment changes.

Abstract

from arXiv · show

We consider a dynamic multichannel access problem, where multiple correlated channels follow an unknown joint Markov model. A user at each time slot selects a channel to transmit data and receives a reward based on the success or failure of the transmission. The objective is to find a policy that maximizes the expected long-term reward. The problem is formulated as a partially observable Markov decision process (POMDP) with unknown system dynamics. To overcome the challenges of unknown system dynamics as well as prohibitive computation, we apply the concept of reinforcement learning and implement a Deep Q-Network (DQN) that can deal with large state space without any prior knowledge of the system dynamics. We provide an analytical study on the optimal policy for fixed-pattern channel switching with known system dynamics and show through simulations that DQN can achieve the same optimal performance without knowing the system statistics. We compare the performance of DQN with a Myopic policy and a Whittle Index-based heuristic through both simulations as well as real-data trace and show that DQN achieves near-optimal performance in more complex situations. Finally, we propose an adaptive DQN approach with the capability to adapt its learning in time-varying, dynamic scenarios.

I. INTRODUCTION

The paper studies dynamic access to correlated wireless channels when observations and system statistics are incomplete, making exact optimization computationally difficult. It applies DQN to learn access policies online, matching known optimal performance in fixed-pattern settings and achieving near-optimal results in more complex and time-varying scenarios.

  • Motivation: External interference can correlate IEEE 802.15.4 channels, motivating dynamic multichannel access algorithms for wireless sensor networks.The channels share spectrum with Wi-Fi, Bluetooth, RFID, industrial equipment, and appliances.
  • Problem formulation: A user selects one of N good-or-bad channels per slot, observes only the selected channel, and seeks to maximize successful transmissions over time.The joint channel distribution follows a 2^N-state Markovian model.
  • Problem formulation: The POMDP formulation is PSPACE-hard, requires exponential computation for exact solutions, and may have unknown joint-model parameters.Partial observation and unavailable system statistics make finding a good policy more difficult.
  • Approach: DQN uses deep Q learning and online historical observations to learn policies for large state spaces without prior system-dynamics knowledge.The network takes states as input and produces estimated Q values for policy learning.
  • Evaluation: DQN matches the optimal performance analytically identified for fixed-pattern channel switching, even without system statistics.The known-system optimum is achieved by a genie with full observation ability.
  • Evaluation: Simulations and real-data traces show near-optimal DQN policies in complex scenarios, while adaptive DQN detects environmental changes and relearns policies in dynamic settings.The paper also compares DQN with Myopic and Whittle Index-based approaches and studies correlated channels where Whittle Index cannot be applied.

III. PROBLEM FORMULATION

The paper formulates dynamic multichannel access as a POMDP in which a user senses one channel, infers hidden system states, and seeks a policy maximizing discounted long-term reward. Exact solution becomes computationally prohibitive as correlated channels enlarge the state and belief spaces.

  • POMDP formulation: Because only the sensed channel is observed, the joint states of all channels are hidden and must be represented through a belief vector.The belief gives conditional probabilities over the 2^N possible system states and is updated using observations and the transition matrix.
  • POMDP formulation: A sensing policy maps the current belief to a channel-selection action, with the optimal policy maximizing expected discounted reward.The formulation uses the belief-space augmented MDP and its Bellman optimality equation.
  • Computational challenge: When the number of channels exceeds 5, the POMDP solver fails to converge before the runtime limit in the reported experiment.The experiment uses known system dynamics and measures running time as the number of channels increases.

IV. MYOPIC POLICY AND WHITTLE INDEX

The section reviews Myopic and Whittle Index policies as computationally efficient approaches for dynamic multichannel access. Their strongest guarantees apply under restricted channel assumptions and known system statistics.

  • Policy background: Myopic and Whittle Index policies are effective, easy-to-implement approaches when channels are independent and the transition matrix is known.Both policies have polynomial runtime.

A. Myopic Policy

The Myopic policy chooses the channel with the greatest expected immediate reward, while related optimality results depend on channel correlation and independence assumptions. A Whittle-based heuristic extends the comparison to correlated channels but requires known transition statistics and offers no general guarantee.

  • Myopic policy: The Myopic policy selects the channel with the maximized expected immediate reward and ignores effects of state transitions on future rewards.Its decision rule focuses only on immediate payoff.
  • Myopic policy: The Myopic policy is optimal for any number of identical independent channels with positively correlated state transitions.For negatively correlated transitions, the same optimal result holds for two or three channels.
  • Policy structure: The Myopic policy has a robust round-robin structure, and the Whittle Index policy shares it when channels have identical distributions.These policies are therefore particularly simple under their respective assumptions.
  • Whittle Index heuristic: When channels are correlated, the Whittle Index is undefined, so the policy cannot be directly applied to the original problem.The proposed heuristic ignores cross-channel correlations, derives an individual two-state model using Bayes’ Rule and the joint transition matrix, then applies Whittle Index selection.
  • Motivation for learning: Existing policies require prior transition-matrix knowledge and lack general performance guarantees, motivating a model-free approach that learns directly from observations.Limited sensing can also make model estimation unreliable, while large-state dynamic programming has exponential time complexity.

A. Q-Learning

Q-learning converts the access problem into sequential value estimation, but history-based states grow exponentially with the observation window. DQN replaces the impractical lookup table with a neural-network approximation of Q-values.

  • Q-learning: Q-learning seeks state-action Q-values whose maximizing actions produce a policy with the greatest long-term discounted reward.The method can learn online without prior knowledge of system dynamics.
  • Deep Q-Network: Direct belief-space Q-learning is impractical because belief updates require the transition matrix a priori, so the paper instead uses historical observations and actions.This model-free representation avoids explicit system-model estimation.
  • State representation: The history-based Q-learning state combines selected channels and observations from the previous M time slots.Increasing M supplies more historical information for learning but enlarges the state representation.
  • State-space growth: The Q-learning state space has size (2N)^M, growing exponentially with the history length M.This growth prevents a traditional lookup table from maintaining Q-values effectively.
  • Deep Q-Network: DQN approximates the Q-function with a deep neural network that maps state-action inputs to Q-values and updates network weights by minimizing temporal-difference loss.The target uses the previous network weights and the next state’s maximum Q-value.

VI. OPTIMAL POLICY FOR KNOWN FIXED-PATTERN CHANNEL SWITCHING

For fixed-pattern switching with known activation order, switching probability, and initial subset, the paper derives an optimal policy based on whether p is above or below 0.5. The policy is round-robin over activated subsets and requires only this threshold information about p.

  • Analytical optimal policy: Theorem 1 states that Algorithms 1 or 2 are optimal when the activation order, p, and initial activation subset are known.The choice between algorithms depends on the value of p.
  • Policy structure: When the previous chosen channel is good, the policy stays or moves according to the activation-order rule; otherwise, it selects a channel in the next activated subset.The two algorithmic cases differ in how they respond to the observed channel state.
  • System model: The fixed-pattern system consists of independent channel subsets activated in a circular order, with one subset active at each time slot.The active subset advances with probability p and remains active with probability 1 − p.
  • State observability: Observing whether the selected channel is good or bad reveals the current activated subset, making the MDP state fully observable.The initial activated subset is known, and subsequent states are inferred from the selected channel's observation.
  • Policy properties: The optimal policy has a round-robin structure and needs only whether p is above or below 0.5, making it robust to mismatched dynamics.The paper describes this as a semi-universal property that simplifies implementation.

VII. EXPERIMENT AND EVALUATION OF LEARNING FOR UNKNOWN FIXED-PATTERN CHANNEL SWITCHING

The paper implements a DQN using recent action-observation histories and experience replay to learn channel-selection values without prior system statistics. It evaluates the approach in a 16-channel setting across three experiments.

  • Approach: The DQN is trained without prior knowledge of system statistics and is evaluated through three experiments in fixed-pattern channel switching.The implementation follows Deep Q-learning with Experience Replay.
  • DQN architecture: The finalized network uses two hidden layers of 200 neurons, ReLU activations, and Adam-based weight updates.The authors report that a 200-neuron structure provided good performance with small training time.
  • State representation: The DQN input combines previous actions and observations over M time slots, with M set equal to the number of channels N.For the experiments, N = 16 and M = N.
  • State and action encoding: Each observation vector records channel quality as 1 or −1 for the selected channel and 0 for unselected channels, implicitly encoding the action.The DQN output has one Q value for each of the N possible selected channels.

B. Single Good Channel, Round Robin Switching Situation

The paper first studies one good channel that switches sequentially in a round-robin pattern, then tests arbitrary switching orders. DQN matches the known-dynamics optimum and outperforms the Whittle Index heuristic.

  • Round-robin model: The single good channel advances from k to k + 1 with probability p and remains at k with probability 1 − p.This creates strong dependence and correlation among channels under sequential switching.
  • Round-robin evaluation: In the round-robin experiment, DQN achieves the same optimal performance as the known-dynamics optimal policy in all five switching-probability cases.DQN also performs significantly better than the Whittle Index heuristic.
  • Policy comparison: DQN can learn channel correlation and system dynamics, whereas the Whittle Index heuristic assumes independent channels.The comparison highlights the effect of modeling correlated channel behavior.
  • Reward trend: As p increases, DQN's accumulated reward increases because greater switching certainty increases the optimal reward.The paper reports this trend for the round-robin setting.
  • Arbitrary switching: With p fixed at 0.9 and eight arbitrary switching orders, DQN achieves optimal performance and significantly outperforms the Whittle Index heuristic in every case.This tests single-good-channel switching beyond the sequential order.

D. Multiple Good Channels Situation

The paper extends evaluation to multiple good channels, correlated-channel scenarios, and real-data traces. DQN reaches optimal performance in fixed-pattern cases and remains close to the full-information Myopic benchmark in more complex settings.

  • Training behavior: DQN training time decreases as the number of simultaneously good channels increases.The paper attributes this to more opportunities to find a good channel and faster policy discovery.
  • Policy comparison: In all multiple-good-channel cases, DQN significantly outperforms the Whittle Index heuristic.The advantage is reported across the evaluated numbers of good channels.
  • Correlated channels: For correlated-channel simulations, the full-information Myopic policy is best, DQN performs very close to it without system knowledge, and Whittle performs worse in every case.The six cases include positively and negatively perfectly correlated channels.
  • Benchmark scope: The Myopic policy is optimal in the first three correlated cases and conjectured near-optimal in the last three.The latter cases involve correlation coefficient ρ = −1.
  • Learning dynamics: DQN's average maximum Q-value rises during training and then stabilizes, indicating learning and convergence to a good policy.Different environments require different numbers of training iterations before stabilization.

B. Real data trace

The real-data evaluation uses an indoor Wi-Fi testbed trace and an intentionally adverse subset of channels. In this complicated scenario, DQN performs best and benefits from using channels beyond those favored by the Whittle Index heuristic.

  • Trace and setup: The evaluation uses approximately 17 hours of indoor testbed data from a dynamic environment with 8 channels selected for analysis.The testbed contains 8 Wi-Fi access points, multipath fading, and many people working nearby.
  • Trace and setup: The experiment ignores the better channels to create a more adverse scenario for testing DQN learning.The trace from the remaining 8 channels is used after excluding channels with significantly better conditions.
  • Compared policies: The trace trains DQN and supplies maximum-likelihood transition matrices for the Whittle Index heuristic.The same data trace is used for both training and transition-matrix estimation.
  • Results: DQN performs best in the complicated real scenario among the evaluated policies.The average accumulated discounted reward is reported for each policy in Table II.
  • Results: DQN uses other channels when the two channels favored continuously by the Whittle Index heuristic are in poor states.Channel utilization is used to illustrate the difference between the policies.

C. Practical Issues

Practical deployment requires sender–receiver synchronization so both sides select the same channel and share channel observations. The paper addresses training mismatch with synchronized randomness and proposes recovery when ACK or NAK losses desynchronize the devices.

  • Sender–receiver coordination: ACKs and NAKs let the sender infer the selected channel condition, so sender and receiver must select the same channel each time slot.This synchronization is needed both for communication and for consistent channel-condition information.
  • Sender–receiver coordination: Independent exploration and replay sampling can make separately trained sender and receiver DQNs choose different channels or learn different parameters.The mismatch can arise from random channel selection during exploration or different minibatches during backpropagation.
  • Training synchronization: Using the same random seed makes both DQNs select the same exploratory channels, use the same replay samples, and learn the same final policy.This approach synchronizes pseudorandom choices during training.
  • Mismatch recovery: Lost ACK or NAK messages can desynchronize observations, impair communication, and produce different learned DQN policies.The paper identifies noise or interference as causes of acknowledgement loss.
  • Mismatch recovery: After detecting a mismatch, the sender can stop updating and transmit on a known good channel while sending a mismatch timestamp for receiver recovery.The receiver restores its model and dataset to the state before the mismatch, allowing both devices to resume synchronized operation.
  • Mismatch recovery: The expected re-synchronization time is N / (ϵ p_good (1−p_ack)) time slots under the stated assumptions.The derivation assumes exploration probability ϵ, good-channel probability p_good, ACK/NAK loss probability p_ack, and N channels.

IX. ADAPTIVE DQN FOR UNKNOWN, TIME-VARYING ENVIRONMENTS

The adaptive DQN addresses environments whose channel-switching patterns change over time. It monitors reward, retrains after degradation, and in experiments finds optimal policies for new environments while the Whittle Index heuristic remains unsatisfactory.

  • Motivation: Real systems can change over time, so a DQN policy learned for a stationary environment may need to relearn.The adaptive framework is designed for unknown, time-varying environments.
  • Adaptive procedure: Adaptive DQN periodically evaluates accumulated reward and retrains when performance falls by a user-defined threshold.The algorithm otherwise keeps using the current policy; the paper manually checks evaluation performance in its experiment.
  • Adaptive procedure: DQN can detect environmental changes through reward degradation, whereas the Whittle Index heuristic may not reveal changes through reward alone.The paper attributes this limitation to the heuristic's low performance in both old and new environments.
  • Experimental results: When the switching pattern changes, DQN finds an optimal policy for the new environment as the genie-optimal policy does, while the Whittle Index heuristic does not.This result is reported across experiments varying the pattern changes.
  • Experimental results: In a representative change from 8 good channels to 1, DQN detects the reward drop, starts relearning, and reaches optimal performance at iteration 70.Both methods quickly find a good policy initially, but DQN achieves the optimal performance after the change.
  • Experimental results: After re-estimation, the Whittle Index heuristic remains unsatisfactory because it cannot use correlations among channels.The paper contrasts this with DQN's ability to relearn for the changed environment.

X. CONCLUSION AND FUTURE WORK

The paper applies DQN to dynamic multichannel access with unknown statistics, analytically characterizes fixed-pattern optimal access, and evaluates adaptive learning in changing environments. It reports optimal or near-optimal performance while identifying scalability and distributed-learning directions for future work.

  • The problem is a general dynamic multichannel access setting with correlated channels and unknown system statistics.
  • Contributions: Analytical results identify the optimal fixed-pattern access policy achieved by a genie with known statistics and full observation.
  • Contributions: DQN achieves the same optimal performance in fixed-pattern switching without knowing system statistics, and performs near-optimally in more complex scenarios.
  • Contributions: Adaptive DQN detects system changes and re-learns in non-stationary dynamic environments to provide good performance.
  • Future work: Future work includes extending DQN to multi-user, multi-hop, and simultaneous-transmission scenarios, including centralized multi-user channel assignment.
  • Future work: Selecting multiple channels enlarges the action space, requiring careful DQN redesign and potentially very long training; centralized control also becomes expensive with many users.
Loading 1802.06958v1…