Pseudochromis stellatus resembles Pseudochromis reticulatus, P. pictus, P. jace, and P. tonozukai.  Based on comparative morphology, researchers have grouped the new dottyback under the newly designated “P. reticulatus complex.”  The dottybacks in this complex all exhibit a reticulated darkened stripe that runs the entire length of the body below the dorsal (top) fin. P. stellatus’ stripe is the faintest of the group while P. jace’s is the most pronounced (here is Google’s image search of P. jace for a clear comparison).

The ZooTaxa paper describes its habitat:

Pseudochromis stellatus is known from Batanta and Batu Hitam in the northern Raja Ampat Islands of West Papua Province, Indonesia, where it has been collected in 55–62 m and observed to at least 70 m depth. The new species is found on deep reef slopes with gentle incline but exposed to strong currents, and is generally found in association with small gorgonian sea fans or low-growing barrel sponges.

The authors of the paper mention that they have collected other yellow-spotted dottybacks from nearby localities in southern and eastern Indonesia and in eastern Papua New Guinea that appear to be new species as well, which are currently being studied.