The capability of polyelectrolyte brushes to spontaneously clean oil fouling via water is determined by factors including water wettability and the self-assembled structures of hydrated polyelectrolytes. Although the charged groups of polyelectrolytes provide the original source of water wettability, the self-assembled structures play a significant role in the self-cleaning performances. Here, we employ coarse-grained molecular dynamics simulations to study the general self-cleaning characteristics of two types of surface-grafted polyelectrolyte brushes (i.e., zwitterionic and anionic poly-electrolytes). It has been found that the high grafting density is favorable to fouling reduction for both polyzwitterions and polyanions. To be specific, the hydrated polyzwitterions form an intermolecular cross-linked network via zwitterionic complexes, resulting in better self-cleaning capabilities than the polyanions at lower grafting densities. However, polyanions form bundles with each consisting of several chains via hydrophobic interactions and electrostatic repulsions presenting better self-cleaning performances than the polyzwitterions at higher grafting densities.