Domain generation algorithms (DGAs) can be categorized into three types:zero-knowledge,partial-knowledge, andfull-knowledge. While prior research merely focused onzero-knowledgeandfull-knowledgetypes, we characterize their anti-detection ability and practicality and find thatzero-knowledgeDGAs present low anti-detection ability againstdetectors, andfull-knowledgeDGAs suffer from low practicality due to the strong assumption that they are fullydetector-aware. Given these observations, we proposePKDGA, a partial knowledge-based domain generation algorithm with high anti-detection ability and high practicality.PKDGAemploys the reinforcement learning architecture, which makes it evolve automatically based only on the easily-observable feedback from detectors. We evaluatePKDGAusing a comprehensive set of real-world datasets, and the results demonstrate that it reduces the detection performance of existingdetectorsfrom 91.7% to 52.5%. We further applyPKDGAto theMiraimalware, and the evaluations show that the proposed method is quite lightweight and time-efficient.